Double bondage in graphs
Abstract
Let G = (V, E) be a graph with vertex set V and edge set E. A vertex v ∈ V(G) is said to dominate itself and all vertices in its neighborhood Ng(v) = {it: uv ∈ E(G)}. A set D ⊆ V(G) is a double dominating set of G if every vertex v ∈ V(G) is dominated by at least two vertices of D. The double domination number γd(G) equals the minimum cardinality of a double dominating set of G. Let E' ⊆ E be a subset of the set of edges, and let G-E' = (V, E - E') be the graph obtained from G by removing the edges of E'. The double bondage number bd(G) equals the minimum cardinality of a set E' ⊆ E such that the graph G - E' does not contain an isolated vertex (that is, a vertex u with NG(u) = ø) and γd(G - E') > γd(G). If for every subset E' ⊆ E, either γd(G - E') = γd(G) or G - E' contains an isolated vertex, then we define bd(G) = 0, and we say that G is a γdstrongly stable graph. We present several basic properties of double bondage in graphs and we determine the double bondage numbers of several classes of graphs. We also characterize the class of trees T for which bd(T) = 1.
