Displaying similar documents to “Universality of directed graphs of a given height”

Asteroidal Quadruples in non Rooted Path Graphs

Marisa Gutierrez, Benjamin Lévêque, Silvia B. Tondato (2015)

Discussiones Mathematicae Graph Theory

Similarity:

A directed path graph is the intersection graph of a family of directed subpaths of a directed tree. A rooted path graph is the intersection graph of a family of directed subpaths of a rooted tree. Rooted path graphs are directed path graphs. Several characterizations are known for directed path graphs: one by forbidden induced subgraphs and one by forbidden asteroids. It is an open problem to find such characterizations for rooted path graphs. For this purpose, we are studying in this...

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.

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.

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.

Superstable graphs

Heinrich Herre, Allan Mekler, Kenneth Smith (1983)

Fundamenta Mathematicae

Similarity: