The $k$-Total Bondage Number of a Graph

Abstract

Let $G=(V,E)$ be a connected, finite undirected graph. A set $S\subseteq V$ is said to be a total dominating set of $G$ if every vertex in $V$ is adjacent to some vertex in $S$. The total domination number, ${\gamma }_t(G)$, is the minimum cardinality of a total dominating set in $G$. We define the $k$-total bondage of $G$ to be the minimum number of edges to remove from $G$ so that the resulting graph has a total domination number at least $k$ more than ${\gamma }_t(G)$. We establish general properties of $k$-total bondage and find exact values for certain graph classes including paths, cycles, wheels, complete and complete bipartite graphs.

arXiv comment23 pages, 13 figures