Abstract
A graph is called subpancyclic if it contains a cycle of length $\ell$ for each $\ell$ between 3 and the circumference of the graph. We show that if $G$ is a connected graph on $n\ge 146$ vertices such that $d(u)+d(v)+d(x)+d(y)>(n+10/2)$ for all four vertices $u,v,x,y$ of any path $P=uvxy$ in $G$, then the line graph $L(G)$ is subpancyclic, unless $G$ is isomorphic to an exceptional graph. Moreover, we show that this result is best possible, even under the assumption that $L(G)$ is hamiltonian. This improves earlier sufficient conditions by a multiplicative factor rather than an additive constant.
Original language | English |
---|---|
Pages (from-to) | 1453-1463 |
Number of pages | 11 |
Journal | Discrete applied mathematics |
Volume | 154 |
Issue number | 9 |
DOIs | |
Publication status | Published - 2 Jun 2006 |
Keywords
- MSC-05C45
- MSC-05C35