• NONBONDAGE AND TOTAL NONBONDAGE NUMBERS IN DIGRAPHS

Abstract

Let D= (V, A) be a digraph. A set S of vertices in a digraph D is called a dominating set of D if every vertex v in V – S, there exists a vertex u in S such that (u, v) in A. The domination number g(D) of D is the minimum cardinality of a dominating set of D. A set S of vertices in a digraph D is called a total dominating set of D if S is a dominating set of D and the induced subdigraph áSñ has no isolated vertices. The total domination number g_t(D) of D is minimum cardinality of a total dominating set of D. The nonbondage number b_n(D) of a digraph D is the maximum cardinality among all sets of arcs X Í A such that g(D – X) = g(D). The total nonbondage number b_tn(D) of a digraph D without isolated vertices is the maximum cardinality among all sets of arcs XÍA such that D – X has no isolated vertices and g_t(D – X) = g_t(D). In this paper, the exact value of b_n(D) for any digraph D is found. We obtain several bounds on the bondage and total nonbondage numbers of a graph. Also exact values of these two parameters for some standard graphs are found.