Optimal linear‐Vizing relationships for (total) domination in graphs

Abstract

A total dominating set in a graph is a set of vertices of such that every vertex is adjacent to a vertex of the set. The total domination number is the minimum cardinality of a total dominating set in . In this paper, we study the following open problem posed by Yeo. For each , find the smallest value, , such that every connected graph of order at least 3, of order , size , total domination number , and bounded maximum degree , satisfies . Henning showed that for all . Yeo significantly improved this result and showed that for all , and posed as an open problem to determine “whether grows proportionally with or or some completely different function.” In this paper, we determine the growth of , and show that is asymptotically and likewise determine the asymptotics of the analogous constant for standard domination.