Long Dλ-cycles in regular graphs

H. Trommel, H.J. Veldman

Research output: Book/ReportReportOther research output

Abstract

Let $k$, $d$ and $\lambda$ be positive integers. A cycle $C$ of $G$ is called a $D_{\lambda}$-cycle if every component of $G-V(C)$ has order less than $\lambda$. It is shown that if $G$ is a $k$-connected $d$-regular graph (\,$k\geq 2$\,) on $n\leq (k+1)\,d$ vertices, then $G$ has a $D_{(\lceil k/2\rceil+1)}$-cycle if $k$ is fixed and $d$ is sufficiently large. As a consequence of this result it is shown that under the same conditions $G$ has a cycle of length greater than $(n+d)/2-c\geq (k+2)n/2(k+1)-c$, where $c$ depends on $k$ only.
Original languageUndefined
Place of PublicationEnschede
PublisherUniversity of Twente
Publication statusPublished - 1998

Keywords

  • MSC-05C35
  • MSC-05C38
  • MSC-05C45
  • EWI-3256

Cite this