| Title:
|
Graphs isomorphic to their path graphs (English) |
| Author:
|
Knor, Martin |
| Author:
|
Niepel, Ľudovít |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
127 |
| Issue:
|
3 |
| Year:
|
2002 |
| Pages:
|
473-480 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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$. (English) |
| Keyword:
|
line graph |
| Keyword:
|
path graph |
| Keyword:
|
cycles |
| MSC:
|
05C38 |
| idZBL:
|
Zbl 1074.05507 |
| idMR:
|
MR1931331 |
| DOI:
|
10.21136/MB.2002.134066 |
| . |
| Date available:
|
2009-09-24T22:03:54Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/134066 |
| . |
| Reference:
|
[1] Belan A., Jurica P.: Diameter in path graphs.Acta Math. Univ. Comenian. New Ser. 68 (1999), 111–126. MR 1711079 |
| Reference:
|
[2] Broersma H. J., Hoede C.: Path graphs.J. Graph Theory 13 (1989), 427–444. MR 1010578, 10.1002/jgt.3190130406 |
| Reference:
|
[3] Knor M., Niepel Ľ.: Centers in path graphs.J. Comb. Inf. Syst. Sci. 24 (1999), 79–86. MR 1871774 |
| Reference:
|
[4] Knor M., Niepel Ľ.: Connectivity of path graphs.Discuss. Math., Graph Theory 20 (2000), 181–195. MR 1817490, 10.7151/dmgt.1118 |
| Reference:
|
[5] Knor M., Niepel Ľ.: Distances in iterated path graphs.(to appear). |
| Reference:
|
[6] Knor M., Niepel Ľ.: Path, trail and walk graphs.Acta Math. Univ. Comenian. New Ser. 68 (1999), 253–256. MR 1757793 |
| Reference:
|
[7] Li H., Lin Y.: On the characterization of path graphs.J. Graph Theory 17 (1993), 463–466. Zbl 0780.05048, MR 1231009, 10.1002/jgt.3190170403 |
| Reference:
|
[8] Li X., Zhao B.: Isomorphisms of $P_4$-graphs.Australas. J. Comb. 15 (1997), 135–143. MR 1448237 |
| Reference:
|
[9] Yu X.: Trees and unicyclic graphs with Hamiltonian path graphs.J. Graph Theory 14 (1990), 705–708. Zbl 0743.05018, MR 1079219, 10.1002/jgt.3190140610 |
| . |
