MATHEMATICA BOHEMICA, Vol. 127, No. 3, pp. 473-480 (2002)

Graphs isomorphic to their path graphs

Martin Knor, Ludovit Niepel

Martin Knor, Slovak University of Technology, Faculty of Civil Engineering, Department of Mathematics, Radlinského 11, 813 68 Bratislava, Slovakia, e-mail: knor@vox.svf.stuba.sk
Ludovit Niepel, Kuwait University, Faculty of Science, Department of Mathematics & Computer Science, P.O. Box 5969, Safat 13060, Kuwait, e-mail: niepel@math-1.sci.kuniv.edu.kw

Abstract: 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$.

Keywords: line graph, path graph, cycles

Classification (MSC2000): 05C38

Full text of the article:

Compressed PostScript file (140 kilobytes)
PDF file (140 kilobytes)

[Previous Article] [Next Article] [Contents of this Number]