The cost of edge removal in graph domination
Date
2020
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
ABSTRACT
A vertex set D of a graph G is a dominating set of G if each vertex of G is a member of D or is adjacent to a member of D. The domination number of G, denoted by cðGÞ, is the cardinality of a smallest dominating set of G. In this paper two cost functions, dqðGÞ and DqðGÞ, are considered which measure respectively the smallest possible and the largest possible increase in the cardinal-ity of a dominating set, over and above cðGÞ,ifq edges were to be removed from G. Bounds are established on dqðGÞ and DqðGÞ for a general graph G, after which these bounds are sharpened or these parameters are determined exactly for a number of special graph classes, including paths, cycles, complete bipartite graphs and complete graphs.
Description
CITATION:A. P. de Villiers (2020): The cost of edge removal in graph domination, AKCE International Journal of Graphs and Combinatorics
Keywords
Graph domination, edge removal, criticality
Citation
A. P. de Villiers (2020): The cost of edge removal in graph domination, AKCE International Journal of Graphs and Combinatorics