Double bondage in graphs

作者：Krzywkowski Marcin^*

来源：Utilitas Mathematica, 2016, 101: 227-242.

• double domination
• bondage
• double bondage
• graph tree

Let G = (V, E) be a graph with vertex set V and edge set E. A vertex v is an element of V(G) is said to dominate itself and all vertices in its neighborhood N-G(v) = {u: uv is an element of E(G)}. A set D subset of V(G) is a double dominating set of G if every vertex v is an element of V(G) is dominated by at least two vertices of D. The double domination number -gamma(d)(G) equals the minimum cardinality of a double dominating set of G. Let E' subset of 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 b(d)(G) equals the minimum cardinality, of a set E' C E such that the graph G-E' does not contain an isolated vertex (that is, a vertex u with N-G(u) = empty set) and gamma(d)(G - E') > gamma(d)(G). If for every subset E' subset of E, either gamma(d)(G - E') = gamma(d)(G) or G - E' contains an isolated vertex, then we define b(d)(G) = 0, and we say that G is gamma(d)-strongly 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 b(d)(T) = 1.

• 出版日期2016-11