Article ID Journal Published Year Pages File Type
418476 Discrete Applied Mathematics 2016 9 Pages PDF
Abstract

Let GG be a graph and e=uve=uv an edge in GG (also a vertex in the line graph L(G)L(G) of GG). Then ee is in two cliques EG(u)EG(u) and EG(v)EG(v) with EG(u)∩EG(v)={e}EG(u)∩EG(v)={e} of L(G)L(G), that correspond to all edges incident with uu and vv in GG respectively. Let SL(G)SL(G) be any spanning subgraph of L(G)L(G) such that every vertex e=uve=uv is adjacent to at least min{dG(u)−1,⌈34dG(u)+12⌉} vertices of EG(u)EG(u) and to at least min{dG(v)−1,⌈34dG(v)+12⌉} vertices of EG(v)EG(v). Then if L(G)L(G) is Hamiltonian, we show that SL(G)SL(G) is Hamiltonian. As a corollary we obtain a lower bound on the number of edge-disjoint Hamiltonian cycles in L(G)L(G).

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,