Network Reliability Parameters

Abstract

Let $G=(V,E)$ be a finite undirected graph with no isolated vertices. 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 to be the minimum number of edges to remove from $G$ so that the resulting graph has a total dominating number at least $k$ more than $\gamma_{t}(G)$. In this work we establish general properties of $k$-total bondage, exact values for certain graph classes including paths, cycles, and wheels, and obtain upper bounds for complete and complete bipartite graphs.