Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
line graph; path graph; cycles
line graph; path graph; cycles
Summary:
We prove that for every number $n\ge 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\ge 4$ we reduce the problem of characterizing graphs $G$ such that $P_k(G)\cong G$ to graphs without cycles of length exceeding $k$.
References:
[1] Belan A., Jurica P.: Diameter in path graphs. Acta Math. Univ. Comenian. New Ser. 68 (1999), 111–126. MR 1711079
[2] Broersma H. J., Hoede C.: Path graphs. J. Graph Theory 13 (1989), 427–444. DOI 10.1002/jgt.3190130406 | MR 1010578
[3] Knor M., Niepel Ľ.: Centers in path graphs. J. Comb. Inf. Syst. Sci. 24 (1999), 79–86. MR 1871774
[4] Knor M., Niepel Ľ.: Connectivity of path graphs. Discuss. Math., Graph Theory 20 (2000), 181–195. DOI 10.7151/dmgt.1118 | MR 1817490
[5] Knor M., Niepel Ľ.: Distances in iterated path graphs. (to appear).
[6] Knor M., Niepel Ľ.: Path, trail and walk graphs. Acta Math. Univ. Comenian. New Ser. 68 (1999), 253–256. MR 1757793
[7] Li H., Lin Y.: On the characterization of path graphs. J. Graph Theory 17 (1993), 463–466. DOI 10.1002/jgt.3190170403 | MR 1231009 | Zbl 0780.05048
[8] Li X., Zhao B.: Isomorphisms of $P_4$-graphs. Australas. J. Comb. 15 (1997), 135–143. MR 1448237
[9] Yu X.: Trees and unicyclic graphs with Hamiltonian path graphs. J. Graph Theory 14 (1990), 705–708. DOI 10.1002/jgt.3190140610 | MR 1079219 | Zbl 0743.05018
Search
Partner of
