Double bondage in graphs

Marcin Krzywkowski

Double bondage in graphs

Abstract

A vertex of a graph is said to dominate itself and all of its neighbors. A double dominating set of a graph G=(V,E) is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D. The double domination number of a graph G, denoted by gamma_d(G), is the minimum cardinality of a double dominating set of G. The double bondage number of G, denoted by b_d(G), is the minimum cardinality among all sets of edges E' subseteq E such that delta(G-E') >= 1 and gamma_d(G-E') > gamma_d(G). If for every E' subseteq E, either gamma_d(G-E') = gamma_d(G) or delta(G-E') = 0, then we define b_d(G) = 0, and we say that G is a gamma_d-strongly stable graph. First we discuss the basic properties of double bondage in graphs. We find the double bondage numbers for several classes of graphs. Next we characterize all gamma_d-strongly stable graphs. Finally, we characterize all trees with double bondage number equaling one.