Tight upper bounds for the domination numbers of graphs with given order and minimum degree. II
type: Item
instance of: scholarly article
title: Tight upper bounds for the domination numbers of graphs with given order and minimum degree. II
zbMATH Open document ID: 0959.05086
author: W. Edwin Clark
author: Stephen Suen
published in: The Electronic Journal of Combinatorics
publication date: 2000-12-12T00:00:00Z
full work available at URL: https://eudml.org/doc/120897
full work available at URL: v7i1r58.html
review text: A dominating set in a graph \(G\) is a subset \(S\) of its vertex set \(V(G)\) such that each vertex of \(G\) either is in \(S\), or is adjacent to a vertex of \(S\). The minimum number of vertices of a dominating set in \(G\) is the domination number \(\gamma(G)\) of \(G\). In the paper \(\gamma(n,\delta)\) denotes the largest possible domination number of a graph with \(n\) vertices and with the minimum degree \(\delta\). Further, \(\delta_k(n)= \max(\delta\mid \gamma(n,\delta)\geq k)\) for \(k\geq 1\). Bounds for \(\delta_k(n)\) are found; they hold for sufficiently large \(n\). The upper bound is in terms of \(n\) and \(k\), the lower bound depends moreover on some constant \(c_k\) whose existence is asserted.
reviewed by: Bohdan Zelinka
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05B10
zbMATH DE Number: 1542668
zbMATH Keywords: dominating set
zbMATH Keywords: domination number
zbMATH Keywords: minimum degree
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1542668