Displaying similar documents to “Asteroidal Quadruples in non Rooted Path Graphs”

On Path-Pairability in the Cartesian Product of Graphs

Gábor Mészáros (2016)

Discussiones Mathematicae Graph Theory

Similarity:

We study the inheritance of path-pairability in the Cartesian product of graphs and prove additive and multiplicative inheritance patterns of path-pairability, depending on the number of vertices in the Cartesian product. We present path-pairable graph families that improve the known upper bound on the minimal maximum degree of a path-pairable graph. Further results and open questions about path-pairability are also presented.

A Note on Path Domination

Liliana Alcón (2016)

Discussiones Mathematicae Graph Theory

Similarity:

We study domination between different types of walks connecting two non-adjacent vertices u and v of a graph (shortest paths, induced paths, paths, tolled walks). We succeeded in characterizing those graphs in which every uv-walk of one particular kind dominates every uv-walk of other specific kind. We thereby obtained new characterizations of standard graph classes like chordal, interval and superfragile graphs.

The crossing numbers of join products of paths with graphs of order four

Marián Klešč, Stefan Schrötter (2011)

Discussiones Mathematicae Graph Theory

Similarity:

Kulli and Muddebihal [V.R. Kulli, M.H. Muddebihal, Characterization of join graphs with crossing number zero, Far East J. Appl. Math. 5 (2001) 87-97] gave the characterization of all pairs of graphs which join product is planar graph. The crossing number cr(G) of a graph G is the minimal number of crossings over all drawings of G in the plane. There are only few results concerning crossing numbers of graphs obtained as join product of two graphs. In the paper, the exact values of crossing...

Orientation distance graphs revisited

Wayne Goddard, Kiran Kanakadandi (2007)

Discussiones Mathematicae Graph Theory

Similarity:

The orientation distance graph 𝓓ₒ(G) of a graph G is defined as the graph whose vertex set is the pair-wise non-isomorphic orientations of G, and two orientations are adjacent iff the reversal of one edge in one orientation produces the other. Orientation distance graphs was introduced by Chartrand et al. in 2001. We provide new results about orientation distance graphs and simpler proofs to existing results, especially with regards to the bipartiteness of orientation distance graphs...

Inductive computations on graphs defined by clique-width expressions

Frédérique Carrère (2009)

RAIRO - Theoretical Informatics and Applications

Similarity:

Labelling problems for graphs consist in building distributed data structures, making it possible to check a given graph property or to compute a given function, the arguments of which are vertices. For an inductively computable function , if is a graph with vertices and of clique-width at most , where is fixed, we can associate with each vertex of a piece of information (bit sequence) lab(x) of length (log()) such that we can compute in constant time, using only the labels...

Graphs of low chordality.

Chandran, L.Sunil, Lozin, Vadim V., Subramanian, C.R. (2005)

Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]

Similarity:

Path-Neighborhood Graphs

R.C. Laskar, Henry Martyn Mulder (2013)

Discussiones Mathematicae Graph Theory

Similarity:

A path-neighborhood graph is a connected graph in which every neighborhood induces a path. In the main results the 3-sun-free path-neighborhood graphs are characterized. The 3-sun is obtained from a 6-cycle by adding three chords between the three pairs of vertices at distance 2. A Pk-graph is a path-neighborhood graph in which every neighborhood is a Pk, where Pk is the path on k vertices. The Pk-graphs are characterized for k ≤ 4.

Gamma Graphs Of Some Special Classes Of Trees

Anna Bień (2015)

Annales Mathematicae Silesianae

Similarity:

A set S ⊂ V is a dominating set of a graph G = (V, E) if every vertex υ ∈ V which does not belong to S has a neighbour in S. The domination number γ(G) of the graph G is the minimum cardinality of a dominating set in G. A dominating set S is a γ-set in G if |S| = γ(G). Some graphs have exponentially many γ-sets, hence it is worth to ask a question if a γ-set can be obtained by some transformations from another γ-set. The study of gamma graphs is an answer to this reconfiguration problem....