**
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
© Copyright 2001, ACTA MATHEMATICA
UNIVERSITATIS COMENIANAE