Geodesic
The structure and existence of 2-factors in iterated line graphs
Discussiones Mathematicae. Graph Theory, Tome 27 (2007) no. 3, pp. 507-526.

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

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.
Keywords: line graph, 2-factor, iterated line graph, cycle 
@article{DMGT_2007_27_3_a7,
     author = {Ferrara, Michael and Gould, Ronald and Hartke, Stephen},
     title = {The structure and existence of 2-factors in iterated line graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {507--526},
     publisher = {mathdoc},
     volume = {27},
     number = {3},
     year = {2007},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2007_27_3_a7/}
}
TY  - JOUR
AU  - Ferrara, Michael
AU  - Gould, Ronald
AU  - Hartke, Stephen
TI  - The structure and existence of 2-factors in iterated line graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2007
SP  - 507
EP  - 526
VL  - 27
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2007_27_3_a7/
LA  - en
ID  - DMGT_2007_27_3_a7
ER  - 
%0 Journal Article
%A Ferrara, Michael
%A Gould, Ronald
%A Hartke, Stephen
%T The structure and existence of 2-factors in iterated line graphs
%J Discussiones Mathematicae. Graph Theory
%D 2007
%P 507-526
%V 27
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2007_27_3_a7/
%G en
%F DMGT_2007_27_3_a7
Ferrara, Michael; Gould, Ronald; Hartke, Stephen. The structure and existence of 2-factors in iterated line graphs. Discussiones Mathematicae. Graph Theory, Tome 27 (2007) no. 3, pp. 507-526. http://geodesic.mathdoc.fr/item/DMGT_2007_27_3_a7/

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

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

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

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

[7] S.G. Hartke and A.W. Higgins, Minimum degree growth of the iterated line graph, Ars Combin. 69 (2003) 275-283.

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

[11] Z. Liu and L. Xiong, Hamiltonian iterated line graphs, Discrete Math 256 (2002) 407-422, doi: 10.1016/S0012-365X(01)00442-3.

[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).