Tight upper bounds for the domination numbers of graphs with given order and minimum degree. II (Q1589861)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Tight upper bounds for the domination numbers of graphs with given order and minimum degree. II |
scientific article |
Statements
Tight upper bounds for the domination numbers of graphs with given order and minimum degree. II (English)
0 references
12 December 2000
0 references
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.
0 references
dominating set
0 references
domination number
0 references
minimum degree
0 references