2-connected graphs with small 2-connected dominating sets.
type: Item
instance of: scholarly article
title: 2-connected graphs with small 2-connected dominating sets.
zbMATH Open document ID: 1051.05064
DOI: 10.1016/S0012-365X(03)00055-4
author: Yair Caro
author: Raphael Yuster
published in: Discrete Mathematics
publication date: 2003-08-19T00:00:00Z
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)].
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05D40
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 1967276
zbMATH Keywords: domination
zbMATH Keywords: probabilistic method
MaRDI profile type: Publication
cites work: Transversal numbers of uniform hypergraphs
cites work: Q3852212
cites work: Connected Domination and Spanning Trees with Many Leaves
cites work: On Hadwiger's Number and the Stability Number
cites work: On the ratio of optimal integral and fractional covers
cites work: Domination in graphs with minimum degree two
cites work: Q4108373
cites work: A Winning Strategy for the Ramsey Graph Game
full work available at URL: s0012-365x(03)00055-4
OpenAlex ID: W2000987306
description: scientific article; zbMATH DE number 1967276