##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 622.05042

**Autor: ** Clark, Brent N.; Colbourn, Charles J.; Erdös, Paul

**Title: ** A conjecture on dominating cycles. (In English)

**Source: ** Combinatorics, graph theory and computing, Proc. 16th Southeast. Conf., Boca Raton/Fla. 1985, Congr. Numerantium 47, 189-197 (1985).

**Review: ** [For the entire collection see Zbl 619.00006.]

A dominating cycle in a graph is a cycle in which every vertex of the graph is adjacent to at least one vertex on the cycle. We conjecture that for each c there is a constant k_{c} such that every c-connected graph with minimum degree \delta \geq \frac{n}{c+1}+k_{c} has a dominating cycle. We show that this conjecture, is true, if best possible. We further prove the conjecture for graphs of connectivities 1 through 5.

**Classif.: ** * 05C38 Paths and cycles

05C99 Graph theory

**Keywords: ** dominating cycle

**Citations: ** Zbl 619.00006

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag