ACTA MATHEMATICA UNIVERSITATIS COMENIANAE

ACTA MATHEMATICA UNIVERSITATIS COMENIANAE

Vol. 68, 2 (1999)
pp. 253-256

PATH, TRAIL AND WALK GRAPHS
M. KNOR and \mL. NIEPEL

Abstract. 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. 05C38
Keywords. Iterated line graph, line graph, path graph, trail graph, walk graph

Download: Adobe PDF

Compressed Postscript

Acta Mathematica Universitatis Comenianae
Institute of Applied Mathematics
Faculty of Mathematics, Physics and Informatics
Comenius University
842 48 Bratislava, Slovak Republic
Telephone: + 421-2-60295111 Fax: + 421-2-65425882
e-Mail: amuc@fmph.uniba.sk Internet: www.iam.fmph.uniba.sk/amuc