Advanced Search

Question: On the bondage number of a graph.

Question:On the bondage number of a graph.

lcz 1009 Maple 2023
graphtheory
June 02 2023
2
  • A set D of vertices in a graph G is a dominating set if each vertex of G that is not in D is adjacent to at least one vertex of D.
  • The minimum cardinality among all dominating sets in G is called the domination number of G and denoted σ(G).
  • We define the bondage number b(G) of a graph G to be the cardinality of a smallest set E of edges for which σ(G−E)>σ(G). 

In the previous post, Carl Love provided a code for calculating domination number, so we could use it to calculate bondage number. I wrote a piece of code using a relatively basic approach. I feel like there is room for improvement.  I still can't determine the bondage number of the following graph so far.

 
> 

restart:
with(GraphTheory):
with(Iterator):
#Author: Carl Love <carl.j.love@gmail.com>, the Glorious 1st of June, 2023
#
Domination_number:= (G::Graph)->
local V:= {$nops(op(3,G))}, A:= op(4,G) union~ `{}`~(V), s, v, U:= table([{}= {}]), Us;
    in V do
        for s in {indices}(U, 'nolist') do
            Us:= U[s]; U[s]:= evaln(U[s]);
            for v in V minus s do
                if (U[s union {v}]:= Us union A[v]) = V then return nops({s[], v}) fi
            od
        od
    od
:
 
> 

Bondage_number:=proc(g::Graph)
local dom,vn,edge_ofg,t,M,removeedge,H,i,hasNext, getNext,result;
dom:=Domination_number(g);
vn:=nops(op(3,g));
edge_ofg:=convert(Edges(g),list);
result:="Null";
for t from 1 to vn do
    M := Combination(vn, t);
    hasNext, getNext := ModuleIterator(M);
      while hasNext() do
        removeedge:= {seq(edge_ofg[i], i in getNext()+~1)};
        H := DeleteEdge(g, removeedge,inplace = false);
        if Domination_number(H)> dom then       
         result:=nops(removeedge);
         break t;
        end if;  
      end do;
end do:
return result;
end proc:
> 

ed:={{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 7}, {1, 9}, {1, 11}, {2, 3}, {2, 5},
 {2, 6}, {2, 7}, {2, 12}, {2, 14}, {3, 4}, {3, 7}, {3, 8}, {3, 9}, {3, 16}, {4, 5},
 {4, 9}, {4, 10}, {4, 11}, {4, 17}, {5, 6}, {5, 11}, {5, 12}, {5, 19}, {6, 7}, {6, 12},{6, 13}, {6, 14}, {6, 21}, {7, 8}, {7, 14}, {7, 15}, {8, 9}, {8, 14}, {8, 15}, {8, 16}, {8, 22}, {9, 10}, {9, 16}, {9, 17}, {10, 11}, {10, 17}, {10, 18}, {10, 19}, {10, 23}, {11, 12},{11, 18}, {11, 19}, {12, 13}, {12, 19}, {12, 20}, {13, 14}, {13, 19}, {13, 20}, {13, 21}, {13, 24},{14, 15}, {14, 21}, {15, 16}, {15, 21}, {15, 22}, {15, 24}, {16, 17}, {16, 22}, {16, 23}, {17, 18},
{17, 22}, {17, 23}, {18, 19}, {18, 20}, {18, 23}, {18, 24}, {19, 20}, {20, 21}, {20, 23}, {20, 24},{21, 22}, {21, 24}, {22, 23}, {22, 24}, {23, 24}}:
g:=Graph(ed);

GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24], Array(1..24, {(1) = {2, 3, 4, 5, 7, 9, 11}, (2) = {1, 3, 5, 6, 7, 12, 14}, (3) = {1, 2, 4, 7, 8, 9, 16}, (4) = {1, 3, 5, 9, 10, 11, 17}, (5) = {1, 2, 4, 6, 11, 12, 19}, (6) = {2, 5, 7, 12, 13, 14, 21}, (7) = {1, 2, 3, 6, 8, 14, 15}, (8) = {3, 7, 9, 14, 15, 16, 22}, (9) = {1, 3, 4, 8, 10, 16, 17}, (10) = {4, 9, 11, 17, 18, 19, 23}, (11) = {1, 4, 5, 10, 12, 18, 19}, (12) = {2, 5, 6, 11, 13, 19, 20}, (13) = {6, 12, 14, 19, 20, 21, 24}, (14) = {2, 6, 7, 8, 13, 15, 21}, (15) = {7, 8, 14, 16, 21, 22, 24}, (16) = {3, 8, 9, 15, 17, 22, 23}, (17) = {4, 9, 10, 16, 18, 22, 23}, (18) = {10, 11, 17, 19, 20, 23, 24}, (19) = {5, 10, 11, 12, 13, 18, 20}, (20) = {12, 13, 18, 19, 21, 23, 24}, (21) = {6, 13, 14, 15, 20, 22, 24}, (22) = {8, 15, 16, 17, 21, 23, 24}, (23) = {10, 16, 17, 18, 20, 22, 24}, (24) = {13, 15, 18, 20, 21, 22, 23}}), `GRAPHLN/table/1`, 0)

 (1)
> 

Domination_number(g)

4

 (2)
> 

Bondage_number(g);#Long time..
 

 

Bondage_number.mw

For arbitrarily given graph, it has been proved that determining its bondage number is NP-hard.

I always have a feeling that when removing subsets of edges, the symmetry of these edge subsets can be utilized. Above, we blindly traverse k-subsets of edges. If the graph is symmetric enough, perhaps we can reduce the amount of traversal. However, I have been struggling to understand how to express the symmetry of these edge subsets. Recently, I raised a similar question. 

 

 

 
Please Wait...