×

The ratio of domination and independent domination numbers on trees. (English) Zbl 1360.05125

Summary: Let \(\gamma(G)\) and \(i(G)\) be the domination number and the independent domination number of \(G\), respectively. T. Beyer et al. [in:Proceedings of the eighth Southeastern conference on combinatorics, graph theory, and computing. Louisiana State University, Baton Rouge, February 28 – March 3, 1977. Winnipeg: Utilitas Mathematica Publishing Inc. 321–328 (1977; Zbl 0417.05020)] began with the comparison of of \(i(G)\) and \(\gamma(G)\) and recently N. J. Rad and L. Volkmann [Discrete Appl. Math. 161, No. 18, 3087–3089 (2013; Zbl 1287.05107)] posted a conjecture that \(i(G)/\gamma(G)\leq \Delta(G)/2\), where \(\Delta(G)\) is the maximum degree of \(G\).
In this work, we prove the conjecture for trees and provide the graph achieved the sharp bound.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: arXiv