The structure and existence of 2-factors in iterated line graphs

Michael Ferrara; Ronald Gould; Stephen Hartke

ArticleOriginal scientific text

Title

The structure and existence of 2-factors in iterated line graphs

Authors ¹, ², ³

Affiliations

Department of Theoretical and Applied Mathematics, The University of Akron, Akron, OH 44325, USA
Department of Mathematics and Computer Science, Emory University, Atlanta, GA 30322, USA
Department of Mathematics, University of Nebraska-Lincoln, Lincoln, NE 68588-0130, USA

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.

Keywords

ENG

line graph, 2-factor, iterated line graph, cycle

J.A. Bondy, Pancyclic graphs, I, J. Combin. Theory (B) 11 (1971) 80-84, doi: 10.1016/0095-8956(71)90016-5.
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.
M.H. El-Zahar, On circuits in graphs, Discrete Math. 50 (1984) 227-230, doi: 10.1016/0012-365X(84)90050-5.
R.J. Gould, Advances on the hamiltonian problem-a survey, Graphs Combin. 19 (2003) 7-52, doi: 10.1007/s00373-002-0492-x.
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.
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.
S.G. Hartke and A.W. Higgins, Minimum degree growth of the iterated line graph, Ars Combin. 69 (2003) 275-283.
S.G. Hartke and K. Ponto, k-Ordered hamiltonicity of iterated line graphs, preprint.
M. Knor and L'. Niepel, Distance independent domination in iterated line graphs, Ars Combin. 79 (2006) 161-170.
M. Knor and L'. Niepel, Iterated Line Graphs are Maximally Ordered, J. Graph Theory 52 (2006) 171-180, doi: 10.1002/jgt.20152.
Z. Liu and L. Xiong, Hamiltonian iterated line graphs, Discrete Math 256 (2002) 407-422, doi: 10.1016/S0012-365X(01)00442-3.
V.D. Samodivkin, P-indices of graphs, Godishnik Vissh. Uchebn. Zaved. Prilozhna Mat. 23 (1987) 165-172.
D.B. West, Introduction to Graph Theory, 2nd ed. (Prentice Hall, Upper Saddle River, NJ, 2001).

Title

The structure and existence of 2-factors in iterated line graphs

Affiliations

Abstract

Keywords

Bibliography