# Question:On the bondage number of a graph.

## Question:On the bondage number of a graph.

Maple 2023
• 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 σ(GE)>σ(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 , 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);
 (1)
 > Domination_number(g)
 (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.

﻿