×

Connected domination number of a graph and its complement. (English) Zbl 1234.05176

Summary: A set \(S\) of vertices in a graph \(G\) is a connected dominating set if every vertex not in \(S\) is adjacent to some vertex in \(S\) and the subgraph induced by \(S\) is connected. The connected domination number \(\gamma_{c}(G)\) is the minimum size of such a set. Let \(\delta^*(G) = \min\{\delta(G),\delta({\overline{G}})\}\), where \(\overline{G}\) is the complement of \(G\) and \(\delta(G)\) is the minimum vertex degree. We prove that when \(G\) and \(\overline{G}\) are both connected, \[ \gamma_c(G) + \gamma_c(\overline{G}) \leq \delta^*(G) + 4 - (\gamma_c(G)-3)(\gamma_c(\overline{G})-3). \]
As a corollary, \(\gamma_c(G) + \gamma_c(\overline{G}) \leq \frac{3n}{4}\) when \(\delta^*(G) \geq 3\) and \(n \geq 14\), where \(G\) has \(n\) vertices. We also prove that \(\gamma_c(G) + \gamma_c(\overline{G}) \leq \delta^*(G) + 2\) when \(\gamma_c(G),\gamma_c(\overline{G}) \geq 4\). This bound is sharp when \(\delta^*(G) = 6\), and equality can only hold when \(\delta^*(G) = 6\). Finally, we prove that \(\gamma_c(G)\gamma_c(\overline{G}) \leq 2n-4\) when \(n \geq 7\), with equality only for paths and cycles.

MSC:

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

References:

[1] Caro Y., Yuster R., West D.B.: Connected domination and spanning trees. SIAM J. Discrete Math. 13, 202–211 (2000) · Zbl 0941.05045 · doi:10.1137/S0895480199353780
[2] Dunbar J.E., Haynes T.W., Hedetniemi S.T.: Nordhaus–Gaddum bounds for domination sum in graphs with specified minimum degree. Util. Math. 67, 97–105 (2005) · Zbl 1066.05103
[3] Griggs J.R., Wu M.: Spanning trees in graphs of minimum degree 4 or 5. Discrete Math. 104, 167–183 (1992) · Zbl 0776.05031 · doi:10.1016/0012-365X(92)90331-9
[4] Hedetniemi S.T., Laskar R.C.: Connected domination in graphs. In: Bollobás, B. (eds) Graph Theory and Combinatorics (Cambridge, 1983), pp. 209–217. Academic Press, London (1984) · Zbl 0548.05055
[5] Joseph J.P., Arumugam S.: Domination in graphs. Internat. J. Manag. Syst. 11, 177–182 (1995)
[6] Jaeger F., Payan C.: Relations du type Nordhais-Gaddum pour le nombre d’absorption d’un graphe simple. C. R. Acad. Sci. Paris Sér. A 274, 728–730 (1972) · Zbl 0226.05121
[7] Kleitman D.J., West D.B.: Spanning trees with many leaves. SIAM J. Discrete Math. 4, 99–106 (1991) · Zbl 0734.05041 · doi:10.1137/0404010
[8] Nordhaus E.A., Gaddum J.W.: On complementary graphs. Amer. Math. Monthly 63, 175–177 (1956) · Zbl 0070.18503 · doi:10.2307/2306658
[9] Sampathkumar E., Walikar H.B.: The connected domination number of a graph. J. Math. Phys. Sci. 13(6), 607–613 (1979) · Zbl 0449.05057
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.