Geodesic
PATH, TRAIL AND WALK GRAPHS
Acta mathematica Universitatis Comenianae, Tome 68 (1999) no. 2 
M. Knor; \mL. Niepel. PATH, TRAIL AND WALK GRAPHS. Acta mathematica Universitatis Comenianae, Tome 68 (1999) no. 2. http://geodesic.mathdoc.fr/item/AMUC_1999_68_2_a5/
@article{AMUC_1999_68_2_a5,
     author = {M. Knor and \mL. Niepel},
     title = {PATH, {TRAIL} {AND} {WALK} {GRAPHS}},
     journal = {Acta mathematica Universitatis Comenianae},
     year = {1999},
     volume = {68},
     number = {2},
     url = {http://geodesic.mathdoc.fr/item/AMUC_1999_68_2_a5/}
}
TY  - JOUR
AU  - M. Knor
AU  - \mL. Niepel
TI  - PATH, TRAIL AND WALK GRAPHS
JO  - Acta mathematica Universitatis Comenianae
PY  - 1999
VL  - 68
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/AMUC_1999_68_2_a5/
ID  - AMUC_1999_68_2_a5
ER  - 
%0 Journal Article
%A M. Knor
%A \mL. Niepel
%T PATH, TRAIL AND WALK GRAPHS
%J Acta mathematica Universitatis Comenianae
%D 1999
%V 68
%N 2
%U http://geodesic.mathdoc.fr/item/AMUC_1999_68_2_a5/
%F AMUC_1999_68_2_a5

Voir la notice de l'article provenant de la source Comenius University

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.