Cycle lengths in graphs of given minimum degree
Abstract
We prove that if $G$ is a 2-connected graph with minimum degree at least $k\geqslant 4$, then
(1) $G$ contains $k$ cycles whose lengths form an arithmetic progression with common difference one or two, unless $G\cong K_{k+1}$ or $K_{k,n-k}$;
(2) $G$ contains cycles of lengths $\ell$ modulo $k$ for all even $\ell$, unless $G\cong K_{k+1}$ or $K_{k,n-k}$;
(3) $G$ contains cycles of lengths $\ell$ modulo $k$ for all $\ell$, unless $G\cong K_{k+1}$ or $G$ is bipartite.
In addition, we show that if $k$ is even and $G$ is 2-connected with minimum degree at least $k-1$ and order at least $k+2$, then $G$ contains cycles of lengths $\ell$ modulo $k$ for all even $\ell$. As a corollary, we determine the maximum number of edges in a graph that does not contain a cycle of length divisible by $k$ for all odd $k$.
이 뉴스, 어떠셨어요?
한 번의 탭으로 반응을 남겨요 · 로그인 불필요