Connected domination of regular graphs
From MaRDI portal
Publication:1025488
DOI10.1016/j.disc.2008.05.029zbMath1211.05106OpenAlexW2059898563MaRDI QIDQ1025488
Publication date: 19 June 2009
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disc.2008.05.029
Random graphs (graph-theoretic aspects) (05C80) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (9)
Properties of regular graphs with large girth via local algorithms ⋮ Traceability of connected domination critical graphs ⋮ Domination in 4-regular graphs with girth 3 ⋮ Connected domination in maximal outerplanar graphs ⋮ Connected domination in random graphs ⋮ Bounds relating the weakly connected domination number to the total domination number and the matching number ⋮ New results on connected dominating structures in graphs ⋮ Linear separation of connected dominating sets in graphs ⋮ Minimum 2-dominating sets in regular graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Linear programming and the worst-case analysis of greedy algorithms on cubic graphs
- Approximating the minimum maximal independence number
- Constructing full spanning trees for cubic graphs
- Optimization, approximation, and complexity classes
- Spanning trees in graphs of minimum degree 4 or 5
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- A short note on the approximability of the maximum leaves spanning tree problem
- On weakly connected domination in graphs
- Dominating sets whose closed stars form spanning trees
- Approximation algorithms for connected dominating sets
- Analysis of greedy algorithms on graphs with bounded degrees
- Transversal numbers of uniform hypergraphs
- Differential equations for random processes and random graphs
- Spanning trees with many leaves in cubic graphs
- Connected Domination and Spanning Trees with Many Leaves
- Minimum independent dominating sets of random cubic graphs
- The dominating number of a random cubic graph
- On the Independent Domination Number of Random Regular Graphs
- Randomized greedy algorithms for finding smallk-dominating sets of regular graphs
- Minimum connected dominating sets of random cubic graphs
This page was built for publication: Connected domination of regular graphs
