# Histories in path graphs

Discussiones Mathematicae Graph Theory (2007)

- Volume: 27, Issue: 2, page 345-357
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topLudovít Niepel. "Histories in path graphs." Discussiones Mathematicae Graph Theory 27.2 (2007): 345-357. <http://eudml.org/doc/270721>.

@article{LudovítNiepel2007,

abstract = {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.},

author = {Ludovít Niepel},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {path-graph; graph dynamics; history; graph operator; even caterpillar; convergent graphs; 1-2-bipartite graphs},

language = {eng},

number = {2},

pages = {345-357},

title = {Histories in path graphs},

url = {http://eudml.org/doc/270721},

volume = {27},

year = {2007},

}

TY - JOUR

AU - Ludovít Niepel

TI - Histories in path graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2007

VL - 27

IS - 2

SP - 345

EP - 357

AB - 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.

LA - eng

KW - path-graph; graph dynamics; history; graph operator; even caterpillar; convergent graphs; 1-2-bipartite graphs

UR - http://eudml.org/doc/270721

ER -

## References

top- [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:1<35::AID-JGT5>3.0.CO;2-I Zbl0884.05065
- [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. Zbl1021.05061
- [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. Zbl1057.05047
- [4] H.J. Broersma and C. Hoede, Path graphs, J. Graph Theory 13 (1989) 427-444, doi: 10.1002/jgt.3190130406. Zbl0677.05068
- [5] D. Ferrero, Edge connectivity of iterated P₃-path graphs, Congr. Numer. 155 (2002) 33-47. Zbl1018.05053
- [6] D. Ferrero, Connectivity of path graphs, Acta Mathematica Universitatis Comenianae LXXII (1) (2003) 59-66. Zbl1100.05056
- [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. Zbl0989.05036
- [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. Zbl0780.05048
- [11] X. Li, Isomorphism of P₃-graphs, J. Graph Theory 21 (1996) 81-85, doi: 10.1002/(SICI)1097-0118(199601)21:1<81::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. Zbl0881.05059
- [13] E. Prisner, Graph dynamics, Pitman Research Notes in Mathematics Series Vol 338 (Longman, Essex, 1995). Zbl0848.05001
- [14] E. Prisner, Recognizing k-path graphs, Discrete Appl. Math. 99 (2000) 169-181, doi: 10.1016/S0166-218X(99)00132-8. Zbl0941.05042
- [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. Zbl0766.05096
- [16] X. Yu, Trees and unicyclic graphs with hamiltonian path graphs, J. Graph Theory 14 (1990) 705-708, doi: 10.1002/jgt.3190140610. Zbl0743.05018

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.