On the number of edges in graphs with a given connected domination number
type: Item
instance of: scholarly article
title: On the number of edges in graphs with a given connected domination number
zbMATH Open document ID: 0945.05046
DOI: 10.1016/S0012-365X(99)00143-0
author: Laura A. Sanchis
published in: Discrete Mathematics
publication date: 2000-09-27T00:00:00Z
review text: The paper is devoted to the problem of finding the maximum number of edges in a graph with given connected domination number. A connected dominating set \(V\) of a graph \(G\) is a set of vertices that is dominating and the graph induced by \(V\) is connected. The connected domination number of \(G\) is the size of its smallest connected dominating set. The main result of the paper is a characterization of graphs with given connected domination number. It is proved that for a connected graph \(G\) with \(n\) vertices and connected domination number \(d\) the number of edges in \(G\) is at most \(\binom{n-d+1} {2}+(d-1)\). Moreover extremal graphs achieving this bound are characterized.
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1423741
zbMATH Keywords: dominating set
zbMATH Keywords: domination number
zbMATH Keywords: connected domination number
zbMATH Keywords: characterization
zbMATH Keywords: extremal graphs
reviewed by: Ludovit Niepel
MaRDI profile type: Publication
full work available at URL: s0012-365x(99)00143-0
OpenAlex ID: W2012003157
description: scientific article; zbMATH DE number 1423741