scientific article; zbMATH DE number 1124604

Authors Robert Brigham, Julie R. Carrington

Publication date 29 December 1998

domination number global domination number

Extremal problems in graph theory (05C35)

Given a graph \(G = (V,E)\) whose edges are partitioned among spanning subgraphs \(F_i = (V,E_i)\), a global dominating set is a set of vertices which is a dominating set for each of the subgraphs \(F_i\). The global dominating number \(\gamma_G\) is the cardinality of a minimal global dominating set. The authors give a nice survey of what is known about global domination. This paper is concerned with the question whether, given a set of numbers \(\gamma_1,\ldots,\gamma_k,\gamma_G\), there is a graph \(G\) such that \(\gamma_i\) is the dominating number of \(F_i\) and \(\gamma_G\) is the global dominating number of the partition. An obvious necessary condition is that \(\max(\gamma_i) \leq \gamma_G \leq \gamma_1 + \cdots +\gamma_k\). This condition is also sufficient for \(k=2\), that is, for any integers \(\gamma_1,\gamma_2,\gamma_G\) satisfying it, there exists a partition of a complete graph which realizes the data as domination numbers and global domination numbers respectively, see \textit{R. C. Brigham} and \textit{R. D. Dutton} [Discrete Math. 86, No. 1-3, 127-136 (1990; Zbl 0722.05049)]. The authors give an additional condition which is necessary and sufficient for \(k = 3\), \(k=4\), \(k=5\), and \(k=6\), but which is not sufficient for \(k \geq 7\). For the entire collection see [Zbl 0883.00011].

Recommendations

Cited in

(12)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4378633)