# Article

Full entry | PDF   (0.3 MB)
Keywords:
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

Partner of