ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory


Discussiones Mathematicae Graph Theory 27(3) (2007) 507-526
DOI: 10.7151/dmgt.1376


Michael Ferrara

Department of Theoretical and Applied Mathematics
The University of Akron
Akron, OH 44325, USA

Ronald J. Gould

Department of Mathematics and Computer Science
Emory University, Atlanta, GA 30322, USA

Stephen G. Hartke

Department of Mathematics
University of Nebraska-Lincoln
Lincoln, NE 68588-0130, USA


We prove several results about the structure of 2-factors in iterated line graphs. Specifically, we give degree conditions on G that ensure L2(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 L2(G) with all cycle lengths specified. We also give a characterization of the graphs G where Lk(G) contains a 2-factor.

Keywords: line graph, 2-factor, iterated line graph, cycle.

2000 Mathematics Subject Classification: 05C38, 05C70.


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

Received 27 July 2006
Revised 2 March 2007
Accepted 2 March 2007