Displaying similar documents to “Graphs isomorphic to their path graphs”

A Fan-Type Heavy Pair Of Subgraphs For Pancyclicity Of 2-Connected Graphs

Wojciech Wideł (2016)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a graph on n vertices and let H be a given graph. We say that G is pancyclic, if it contains cycles of all lengths from 3 up to n, and that it is H-f1-heavy, if for every induced subgraph K of G isomorphic to H and every two vertices u, v ∈ V (K), dK(u, v) = 2 implies [...] min⁡dG(u),dG(v)≥n+12 min { d G ( u ) , d G ( v ) } ≥ n + 1 2 . In this paper we prove that every 2-connected K1,3, P5-f1-heavy graph is pancyclic. This result completes the answer to the problem of finding f1-heavy pairs of subgraphs implying...

The structure and existence of 2-factors in iterated line graphs

Michael Ferrara, Ronald J. Gould, Stephen G. Hartke (2007)

Discussiones Mathematicae Graph Theory

Similarity:

We prove several results about the structure of 2-factors in iterated line graphs. Specifically, we give degree conditions on G that ensure L²(G) contains a 2-factor with every possible number of cycles, and we give a sufficient condition for the existence of a 2-factor in L²(G) with all cycle lengths specified. We also give a characterization of the graphs G where L k ( G ) contains a 2-factor.

The 3-path-step operator on trees and unicyclic graphs

Bohdan Zelinka (2002)

Mathematica Bohemica

Similarity:

E. Prisner in his book Graph Dynamics defines the k -path-step operator on the class of finite graphs. The k -path-step operator (for a positive integer k ) is the operator S k ' which to every finite graph G assigns the graph S k ' ( G ) which has the same vertex set as G and in which two vertices are adjacent if and only if there exists a path of length k in G connecting them. In the paper the trees and the unicyclic graphs fixed in the operator S 3 ' are studied.

Cycle and path embedding on 5-ary N-cubes

Tsong-Jie Lin, Sun-Yuan Hsieh, Hui-Ling Huang (2009)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We study two topological properties of the 5-ary n -cube Q n 5 . Given two arbitrary distinct nodes x and y in Q n 5 , we prove that there exists an x - y path of every length ranging from 2 n to 5 n - 1 , where n ≥ 2 . Based on this result, we prove that Q n 5 is 5-edge-pancyclic by showing that every edge in Q n 5 lies on a cycle of every length ranging from 5 to 5 n .

Histories in path graphs

Ludovít Niepel (2007)

Discussiones Mathematicae Graph Theory

Similarity:

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...

Containers and wide diameters of P 3 ( G )

Daniela Ferrero, Manju K. Menon, A. Vijayakumar (2012)

Mathematica Bohemica

Similarity:

The P 3 intersection graph of a graph G has for vertices all the induced paths of order 3 in G . Two vertices in P 3 ( G ) are adjacent if the corresponding paths in G are not disjoint. A w -container between two different vertices u and v in a graph G is a set of w internally vertex disjoint paths between u and v . The length of a container is the length of the longest path in it. The w -wide diameter of G is the minimum number l such that there is a w -container of length at most l between any pair...