Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
418476 | Discrete Applied Mathematics | 2016 | 9 Pages |
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
Hao Li, Weihua He, Weihua Yang, Yandong Bai,