Geodesic
Histories in path graphs
Discussiones Mathematicae. Graph Theory, Tome 27 (2007) no. 2, pp. 345-357.

Voir la notice de l'article provenant de la source Library of Science

For a given graph G and a positive integer r the r-path graph, P_r(G), has for vertices the set of all paths of length r in G. Two vertices are adjacent when the intersection of the corresponding paths forms a path of length r-1, and their union forms either a cycle or a path of length k+1 in G. Let P^k_r(G) be the k-iteration of r-path graph operator on a connected graph G. Let H be a subgraph of P^k_r(G). The k-history P^-k_r(H) is a subgraph of G that is induced by all edges that take part in the recursive definition of H. We present some general properties of k-histories and give a complete characterization of graphs that are k-histories of vertices of 2-path graph operator.
Keywords: path-graph, graph dynamics, history 
@article{DMGT_2007_27_2_a10,
     author = {Niepel, Ludov{\'\i}t},
     title = {Histories in path graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {345--357},
     publisher = {mathdoc},
     volume = {27},
     number = {2},
     year = {2007},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2007_27_2_a10/}
}
TY  - JOUR
AU  - Niepel, Ludovít
TI  - Histories in path graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2007
SP  - 345
EP  - 357
VL  - 27
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2007_27_2_a10/
LA  - en
ID  - DMGT_2007_27_2_a10
ER  - 
%0 Journal Article
%A Niepel, Ludovít
%T Histories in path graphs
%J Discussiones Mathematicae. Graph Theory
%D 2007
%P 345-357
%V 27
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2007_27_2_a10/
%G en
%F DMGT_2007_27_2_a10
Niepel, Ludovít. Histories in path graphs. Discussiones Mathematicae. Graph Theory, Tome 27 (2007) no. 2, pp. 345-357. http://geodesic.mathdoc.fr/item/DMGT_2007_27_2_a10/

[1] R.E.L. Aldred, M.N. Ellingham, R. Hemminger and P. Jipsen, P₃-isomorphism for graphs, J. Graph Theory 26 (1997) 35-51, doi: 10.1002/(SICI)1097-0118(199709)26:135::AID-JGT5>3.0.CO;2-I

[2] C. Balbuena and D. Ferrero, Edge-connectivity and super edge-connectivity of P₂-path graphs, Discrete Math. 269 (2003) 13-20, doi: 10.1016/S0012-365X(02)00828-2.

[3] C. Balbuena and P. García-Vázquez, Edge-connectivity in Pₖ-path graphs, Discrete Math. 286 (2004) 213-218, doi: 10.1016/j.disc.2004.05.007.

[4] H.J. Broersma and C. Hoede, Path graphs, J. Graph Theory 13 (1989) 427-444, doi: 10.1002/jgt.3190130406.

[5] D. Ferrero, Edge connectivity of iterated P₃-path graphs, Congr. Numer. 155 (2002) 33-47.

[6] D. Ferrero, Connectivity of path graphs, Acta Mathematica Universitatis Comenianae LXXII (1) (2003) 59-66.

[7] M. Knor and L. Niepel, Diameter in iterated path graphs, Discrete Math. 233 (2001) 151-161, doi: 10.1016/S0012-365X(00)00234-X.

[8] M. Knor and L. Niepel, Centers in path graphs, JCISS 24 (1999) 79-86.

[9] M. Knor and L. Niepel, Independence number in path graphs, Computing and Informatics 23 (2004) 179-187.

[10] H. Li and Y. Lin, On the characterization of path graphs, J. Graph Theory 17 (1993) 463-466, doi: 10.1002/jgt.3190170403.

[11] X. Li, Isomorphism of P₃-graphs, J. Graph Theory 21 (1996) 81-85, doi: 10.1002/(SICI)1097-0118(199601)21:181::AID-JGT11>3.0.CO;2-V

[12] L. Niepel, M. Knor and L. Soltés, Distances in iterated line graphs, Ars Combin. 43 (1996) 193-202.

[13] E. Prisner, Graph dynamics, Pitman Research Notes in Mathematics Series Vol 338 (Longman, Essex, 1995).

[14] E. Prisner, Recognizing k-path graphs, Discrete Appl. Math. 99 (2000) 169-181, doi: 10.1016/S0166-218X(99)00132-8.

[15] E. Prisner, The dynamics of the line and path graph operators, Discrete Math. 103 (1992) 199-207, doi: 10.1016/0012-365X(92)90270-P.

[16] X. Yu, Trees and unicyclic graphs with hamiltonian path graphs, J. Graph Theory 14 (1990) 705-708, doi: 10.1002/jgt.3190140610.