Edge Weighting Functions on Dominating Sets
Justin Southey, Michael A. Henning · Journal of Graph Theory · 2012
Abstract In this article, we use edge weighting functions on dominating sets to show that if we impose a regularity condition on a graph, then upper bounds on both the upper domination number and the upper total domination number can be greatly improved. More precisely, we prove that for if G is a k‐regular graph on n vertices, then the upper domination number of G is at most , and the upper total domination number of G is at most . Furthermore, we show that these bounds are sharp and characterize the infinite families of graphs that achieve equality in both these bounds.