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

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