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 kc such that every c-connected graph with minimum degree \delta \geq \frac{n}{c+1}+kc 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