A characterization of trees with equal independent domination and secure domination numbers

作者：Li, Zepeng^*; Xu, Jin

来源：Information Processing Letters, 2017, 119: 14-18.

DOI：10.1016/j.ipl.2016.11.004

• Tree
• Independent domination number
• Secure domination number
• Combinatorial problems

Let i(G) and gamma(s)(G) be the independent domination number and secure domination number of a graph G, respectively. Merouane and Chellali (2015) [12] proved that i(T) <= gamma(s)(T) for any tree T and asked to characterize the trees T with i(T) = gamma(s)(T). In this paper, we answer the question. We introduce three operations on trees and prove that any tree T with i(T) = gamma(s)(T) can be obtained by these operations.

• 出版日期2017-3
• 单位北京大学