DOMINATION DEFECT IN GRAPHS: GUARDING WITH FEWER GUARDS

作者：Das Angsuman^*; Desormeaux Wyatt J

来源：Indian Journal of Pure and Applied Mathematics, 2018, 49(2): 349-364.

DOI：10.1007/s13226-018-0273-8

• Minimum dominating set
• efficient dominating set
• vertex removal
• changing domination
• domination defect

In this paper, we introduce a new graph parameter called the domination defect of a graph. The domination number gamma of a graph G is the minimum number of vertices required to dominate the vertices of G. Due to the minimality of gamma, if a set of vertices of G has cardinality less than gamma then there are vertices of G that are not dominated by that set. The k-domination defect of G is the minimum number of vertices which are left un-dominated by a subset of gamma - k vertices of G. We study different bounds on the k-domination defect of a graph G with respect to the domination number, order, degree sequence, graph homomorphisms and the existence of efficient dominating sets. We also characterize the graphs whose domination defect is 1 and find exact values of the domination defect for some particular classes of graphs.

• 出版日期2018-6