Histories in path graphs

Ludovít Niepel

Discussiones Mathematicae Graph Theory (2007)

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

Abstract

top
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 r k ( G ) be the k-iteration of r-path graph operator on a connected graph G. Let H be a subgraph of P r k ( G ) . The k-history P r - k ( 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.

How to cite

top

Ludoví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. [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. [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. [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. [4] H.J. Broersma and C. Hoede, Path graphs, J. Graph Theory 13 (1989) 427-444, doi: 10.1002/jgt.3190130406. Zbl0677.05068
  5. [5] D. Ferrero, Edge connectivity of iterated P₃-path graphs, Congr. Numer. 155 (2002) 33-47. Zbl1018.05053
  6. [6] D. Ferrero, Connectivity of path graphs, Acta Mathematica Universitatis Comenianae LXXII (1) (2003) 59-66. Zbl1100.05056
  7. [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. [8] M. Knor and L. Niepel, Centers in path graphs, JCISS 24 (1999) 79-86. 
  9. [9] M. Knor and L. Niepel, Independence number in path graphs, Computing and Informatics 23 (2004) 179-187. 
  10. [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. [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. [12] L. Niepel, M. Knor and L. Soltés, Distances in iterated line graphs, Ars Combin. 43 (1996) 193-202. Zbl0881.05059
  13. [13] E. Prisner, Graph dynamics, Pitman Research Notes in Mathematics Series Vol 338 (Longman, Essex, 1995). Zbl0848.05001
  14. [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. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.