On the number of edges in graphs with a given weakly connected domination number
type: Item
instance of: scholarly article
title: On the number of edges in graphs with a given weakly connected domination number
zbMATH Open document ID: 1008.05113
DOI: 10.1016/S0012-365X(01)00474-5
author: Laura A. Sanchis
published in: Discrete Mathematics
publication date: 2002-12-02T00:00:00Z
review text: A subset \(D\) of the vertex set \(V(G)\) of a graph \(G\) is called a dominating set in \(G\), if it has the property that each vertex of \(G\) either is in \(D\), or is adjacent to a vertex of \(D\). If, moreover, the set of edges incident with no vertex of \(D\) does not separate the graph \(G\), the set \(D\) is a weakly connected dominating set in \(G\). The minimum cardinality of such a set is the weakly connected domination number \(\gamma_w(G)\) of \(G\). The paper determines \(\left(\begin{smallmatrix} n-d+1\\ 2\end{smallmatrix}\right)\) as the maximum number of edges a graph \(G\) with \(n\) vertices and with \(\gamma_w(G)= d\geq 3\) can have.
reviewed by: Bohdan Zelinka
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 1838978
zbMATH Keywords: weakly connected
zbMATH Keywords: domination number
MaRDI profile type: Publication
full work available at URL: s0012-365x(01)00474-5
OpenAlex ID: W4213244352
description: scientific article; zbMATH DE number 1838978