Geodesic
Graphs isomorphic to their path graphs
Mathematica Bohemica, Tome 127 (2002) no. 3, pp. 473-480

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

MR Zbl
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$.
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$.
DOI : 10.21136/MB.2002.134066
Classification : 05C38
Keywords: line graph; path graph; cycles 
Knor, Martin; Niepel, Ľudovít. Graphs isomorphic to their path graphs. Mathematica Bohemica, Tome 127 (2002) no. 3, pp. 473-480. doi: 10.21136/MB.2002.134066
@article{10_21136_MB_2002_134066,
     author = {Knor, Martin and Niepel, \v{L}udov{\'\i}t},
     title = {Graphs isomorphic to their path graphs},
     journal = {Mathematica Bohemica},
     pages = {473--480},
     year = {2002},
     volume = {127},
     number = {3},
     doi = {10.21136/MB.2002.134066},
     mrnumber = {1931331},
     zbl = {1074.05507},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2002.134066/}
}
TY  - JOUR
AU  - Knor, Martin
AU  - Niepel, Ľudovít
TI  - Graphs isomorphic to their path graphs
JO  - Mathematica Bohemica
PY  - 2002
SP  - 473
EP  - 480
VL  - 127
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2002.134066/
DO  - 10.21136/MB.2002.134066
LA  - en
ID  - 10_21136_MB_2002_134066
ER  - 
%0 Journal Article
%A Knor, Martin
%A Niepel, Ľudovít
%T Graphs isomorphic to their path graphs
%J Mathematica Bohemica
%D 2002
%P 473-480
%V 127
%N 3
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2002.134066/
%R 10.21136/MB.2002.134066
%G en
%F 10_21136_MB_2002_134066

[1] Belan A., Jurica P.: Diameter in path graphs. Acta Math. Univ. Comenian. New Ser. 68 (1999), 111–126. | MR

[2] Broersma H. J., Hoede C.: Path graphs. J. Graph Theory 13 (1989), 427–444. | DOI | MR

[3] Knor M., Niepel Ľ.: Centers in path graphs. J. Comb. Inf. Syst. Sci. 24 (1999), 79–86. | MR

[4] Knor M., Niepel Ľ.: Connectivity of path graphs. Discuss. Math., Graph Theory 20 (2000), 181–195. | DOI | MR

[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

[7] Li H., Lin Y.: On the characterization of path graphs. J. Graph Theory 17 (1993), 463–466. | DOI | MR | Zbl

[8] Li X., Zhao B.: Isomorphisms of $P_4$-graphs. Australas. J. Comb. 15 (1997), 135–143. | MR

[9] Yu X.: Trees and unicyclic graphs with Hamiltonian path graphs. J. Graph Theory 14 (1990), 705–708. | DOI | MR | Zbl

Cité par Sources :