2-connected graphs with small 2-connected dominating sets.

DOI10.1016/S0012-365X(03)00055-4MaRDI QIDQ1402083zbMATH OpenOpenAlexFDO

Authors Yair Caro, Raphael Yuster

Publication date 19 August 2003

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(03)00055-4

zbMATH Keywords

dominationprobabilistic method

Mathematics Subject Classification ID

Connectivity (05C40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Combinatorial probability (60C05)

Review text

The main result of the paper is the following. Let \(G\) be a \(2\)-connected graph with \(n\) vertices and minimum degree \(\delta\). Then \(\gamma_2 \leq n(\ln(\delta)/\delta)(1+o_{\delta}(1))\), where \(\gamma_2\) is the minimum size of a \(2\)-connected dominating set of \(G\) and \(o_{\delta}(1)\) denotes a function that tends to 0 as \(\delta \rightarrow \infty\). The proof uses the probabilistic method. This result extends similar results for \(\gamma_1\), the size of a minimum connected dominating set [see the authors and \textit{D. West}, SIAM J. Discrete Math. 13, No. 2, 202--211 (1998; Zbl 0941.05045), \textit{L. Lovász}, Discrete Math. 13, 383--390 (1975; Zbl 0323.05127)].

Recommendations

• Making a dominating set of a graph connected
• 2-edge connected dominating sets and 2-connected dominating sets of a graph
• Domination in graphs with minimum degree two
• Domination number in graphs with minimum degree two
• An upper bound on the domination number of a graph with minimum degree 2

Cites work

• A Winning Strategy for the Ramsey Graph Game
• Connected Domination and Spanning Trees with Many Leaves
• Domination in graphs with minimum degree two
• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3531438 (Why is no real title available?)
• On Hadwiger's Number and the Stability Number
• On the ratio of optimal integral and fractional covers
• Transversal numbers of uniform hypergraphs

Cited in

(7)

• Connected domination
• On the (h,k)-domination numbers of iterated line digraphs
• scientific article; zbMATH DE number 1750102 (Why is no real title available?)
• Degree sum and vertex dominating paths
• scientific article; zbMATH DE number 6107241 (Why is no real title available?)
• 2-edge connected dominating sets and 2-connected dominating sets of a graph
• Probabilistic analysis of upper bounds for 2-connected distance \(k\)-dominating sets in graphs

This page was built for publication: 2-connected graphs with small 2-connected dominating sets.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1402083)