×

Graphs with large double domination numbers. (English) Zbl 1073.05050

This article deals with double domination in graphs. A vertex in a graph is considered to be dominating itself and its neighbours; a set \(S\) of vertices is double dominating if \(S\) dominates every vertex of the graph at least twice. The double domination number \(\gamma_{\times2}\) is defined as the minimum cardinality of \(S\).
In the first two sections, a short background on domination is presented including the current best bound on the double domination number for graphs \(G\) where \(\delta(G)\geq2\) which is \(\gamma_{\times2}\leq 11n/13\), with \(n\) the order of the graph. The author continues by presenting the main result of the paper, which is to improve the above bound to \(\gamma_{\times2}\leq 3n/4\), for graphs \(G\neq C_5\). The article then continues by characterizing the graphs that achieve equality. Full proofs are presented throughout this very interesting article on graph domination.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite
Full Text: DOI