Currently displaying 1 – 5 of 5

Showing per page

Order by Relevance | Title | Year of publication

Histories in path graphs

Ludovít Niepel — 2007

Discussiones Mathematicae Graph Theory

For a given graph G and a positive integer r the r-path graph, P r ( G ) , has for vertices the set of all paths of length r in G. Two vertices are adjacent when the intersection of the corresponding paths forms a path of length r-1, and their union forms either a cycle or a path of length k+1 in G. Let P r k ( G ) be the k-iteration of r-path graph operator on a connected graph G. Let H be a subgraph of P r k ( G ) . The k-history P r - k ( H ) is a subgraph of G that is induced by all edges that take part in the recursive definition of...

Graphs isomorphic to their path graphs

Martin Knor;  Ľudovít Niepel — 2002

Mathematica Bohemica

We prove that for every number n ≥ 1 , the n -iterated P 3 -path graph of G is isomorphic to G if and only if G is a collection of cycles, each of length at least 4. Hence, G is isomorphic to P 3 ( G ) if and only if G is a collection of cycles, each of length at least 4. Moreover, for k ≥ 4 we reduce the problem of characterizing graphs G such that P k ( G ) ≅ G to graphs without cycles of length exceeding k .

Page 1

Download Results (CSV)