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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page