ACTA MATHEMATICA UNIVERSITATIS COMENIANAE
Vol. 68,   2   (1999)
PATH, TRAIL AND WALK GRAPHS
M. KNOR and \mL. NIEPEL
We introduce trail graphs and walk graphs as a generalization of line graphs. The path graph $P_k(G)$ is an induced subgraph of the trail graph $T_k(G)$, which is an induced subgraph of the walk graph $W_k(G)$. We prove that the walk graph $W_k(G)$ is an induced subgraph of the $k$-iterated line graph $L^k(G)$, using a special embedding preserving histories. Hence, trail graphs and walk graphs are in a sense more close to line graphs than the path graphs, and some problems that are complicated in path graphs become easier for walk graphs.
AMS subject classification.
Iterated line graph, line graph, path graph, trail graph, walk graph
Download:     Adobe PDF     Compressed Postscript
Acta Mathematica Universitatis Comenianae
Institute of Applied
Faculty of Mathematics,
Physics and Informatics
842 48 Bratislava, Slovak Republic
Telephone: + 421-2-60295111 Fax: + 421-2-65425882
© Copyright 2001, ACTA MATHEMATICA