The Disjunctive Bondage Number and the Disjunctive Total Bondage Number of Graphs

摘要

Let G be a graph with vertex set V(G) and edge set E(G). A set S is contained in V(G) is a disjunctive dominating set of G if every vertex in V(G) - S is adjacent to a vertex of 5 or has at least two vertices in S at distance two from it. For G with no isolated vertex, a set S is contained in V(G) is a disjunctive total dominating set of G if every vertex in G is adjacent to a vertex of S or has at least two vertices of S at distance two from it. The disjunctive domination number γ~d(G) of G is the minimum cardinality over all disjunctive dominating sets of G, and the disjunctive total domination number γ_t~d(G) of G is the minimum cardinality over all disjunctive total dominating sets of G. We define disjunctive bondage number of G to be the minimum cardinality among all subsets of edges B is contained in E(G) for which γ~d(G - B) ＞ γ~d(G). For G with no isolated vertex, we define disjunctive total bondage number, b_t~d(G), of G to be the minimum cardinality among all subsets of edges B' is contained in E(G) satisfying γ_t~d(G - B') ＞ γ_t~d(G) and that G - B' contains no isolated vertex; if no such subset B' exists, we define b_t~d(G) = ∞. In this paper, we initiate the study of the disjunctive (total) bondage number of graphs. We determine the disjunctive (total) bondage number of the Petersen graph, cycles, paths, and some complete multipartite graphs. We also obtain upper bounds of the disjunctive bondage number for trees and some Cartesian product graphs, and we show the existence of a tree T satisfying b_t~d(T) = k for each positive integer k.