The structure and existence of 2-factors in iterated line graphs
Michael Ferrara; Ronald J. Gould; Stephen G. Hartke
Discussiones Mathematicae Graph Theory (2007)
- Volume: 27, Issue: 3, page 507-526
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topMichael Ferrara, Ronald J. Gould, and Stephen G. Hartke. "The structure and existence of 2-factors in iterated line graphs." Discussiones Mathematicae Graph Theory 27.3 (2007): 507-526. <http://eudml.org/doc/270635>.
@article{MichaelFerrara2007,
abstract = {We prove several results about the structure of 2-factors in iterated line graphs. Specifically, we give degree conditions on G that ensure L²(G) contains a 2-factor with every possible number of cycles, and we give a sufficient condition for the existence of a 2-factor in L²(G) with all cycle lengths specified. We also give a characterization of the graphs G where $L^k(G)$ contains a 2-factor.},
author = {Michael Ferrara, Ronald J. Gould, Stephen G. Hartke},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {line graph; 2-factor; iterated line graph; cycle},
language = {eng},
number = {3},
pages = {507-526},
title = {The structure and existence of 2-factors in iterated line graphs},
url = {http://eudml.org/doc/270635},
volume = {27},
year = {2007},
}
TY - JOUR
AU - Michael Ferrara
AU - Ronald J. Gould
AU - Stephen G. Hartke
TI - The structure and existence of 2-factors in iterated line graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2007
VL - 27
IS - 3
SP - 507
EP - 526
AB - We prove several results about the structure of 2-factors in iterated line graphs. Specifically, we give degree conditions on G that ensure L²(G) contains a 2-factor with every possible number of cycles, and we give a sufficient condition for the existence of a 2-factor in L²(G) with all cycle lengths specified. We also give a characterization of the graphs G where $L^k(G)$ contains a 2-factor.
LA - eng
KW - line graph; 2-factor; iterated line graph; cycle
UR - http://eudml.org/doc/270635
ER -
References
top- [1] J.A. Bondy, Pancyclic graphs, I, J. Combin. Theory (B) 11 (1971) 80-84, doi: 10.1016/0095-8956(71)90016-5.
- [2] G. Chartrand, The existence of complete cycles in repeated line-graphs, Bull. Amer. Math. Society 71 (1965) 668-670, doi: 10.1090/S0002-9904-1965-11389-1. Zbl0133.16801
- [3] M.H. El-Zahar, On circuits in graphs, Discrete Math. 50 (1984) 227-230, doi: 10.1016/0012-365X(84)90050-5.
- [4] R.J. Gould, Advances on the hamiltonian problem-a survey, Graphs Combin. 19 (2003) 7-52, doi: 10.1007/s00373-002-0492-x. Zbl1024.05057
- [5] R.J. Gould and E.A. Hynds, A note on cycles in 2-factors of line graphs, Bull. of the ICA 26 (1999) 46-48. Zbl0922.05046
- [6] F. Harary and C.St.J.A. Nash-Williams, On eulerian and hamiltonian graphs and line graphs, Canad. Math. Bull. 8 (1965) 701-709, doi: 10.4153/CMB-1965-051-3. Zbl0136.44704
- [7] S.G. Hartke and A.W. Higgins, Minimum degree growth of the iterated line graph, Ars Combin. 69 (2003) 275-283. Zbl1072.05566
- [8] S.G. Hartke and K. Ponto, k-Ordered hamiltonicity of iterated line graphs, preprint.
- [9] M. Knor and L'. Niepel, Distance independent domination in iterated line graphs, Ars Combin. 79 (2006) 161-170.
- [10] M. Knor and L'. Niepel, Iterated Line Graphs are Maximally Ordered, J. Graph Theory 52 (2006) 171-180, doi: 10.1002/jgt.20152. Zbl1090.05039
- [11] Z. Liu and L. Xiong, Hamiltonian iterated line graphs, Discrete Math 256 (2002) 407-422, doi: 10.1016/S0012-365X(01)00442-3. Zbl1027.05055
- [12] V.D. Samodivkin, P-indices of graphs, Godishnik Vissh. Uchebn. Zaved. Prilozhna Mat. 23 (1987) 165-172.
- [13] D.B. West, Introduction to Graph Theory, 2nd ed. (Prentice Hall, Upper Saddle River, NJ, 2001).
NotesEmbed ?
topYou 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.