×

Efficient and excess domination in graphs. (English) Zbl 0903.05032

For a graph \(G=(V,E)\), a vertex \(u\) dominates a vertex \(v\) if \(u=v\) or \(uv\in E\). A set \(S\subset V\) is a dominating set if each vertex in \(V\) is dominated by at least one vertex of \(S\) and is an efficient dominating set if each vertex in \(V\) is dominated by exactly one vertex of \(S\). The domination excess \(\text{de} (G)\) is the smallest number of times that the vertices of \(G\) are dominated more than once by a minimum dominating set. The authors characterize coronas and caterpillars as well as the graphs \(G\) for which both \(G\) and \(\overline G\) have efficient dominating sets. They also obtain bounds on the domination excess in graphs which do not have efficient dominating sets and show that \(\text{de} (T)\leq 2n/3-2\) for any tree \(T\) of order \(n\).

MSC:

05C35 Extremal problems in graph theory
PDFBibTeX XMLCite