A Size Upper Bound for Dominating Cycles

Abstract

Recently it was shown (by the author) that every graph of size $q$ (the number of edges) and minimum degree $\delta$ is hamiltonian if $q\le {\delta }^2+\delta -1$ (arXiv:1107.2201v1). In this paper we present the exact analog of this result for dominating cycles: if $G$ is a 2-connected graph with $q\le 8$ if $\delta =2$ and $q\le (3(\delta -1)(\delta +2)-1)/2$ if $\delta \ge 3$, then each longest cycle in $G$ is a dominating cycle. The result is sharp in all respects.

29 pages

References in corpus (1)

• A Size Bound for Hamilton Cycles