Question: How can I calculate the domination number of a graph?

In graph theory, a dominating set for a graph G is a subset D of its vertices, such that any vertex of G is either in D, or has a neighbor in D. The domination number γ(G) is the number of vertices in a smallest dominating set for G. The domination number is a well-known parameter in graph theory. But I am unable to find a built-in function in Maple to calculate the domination number of a graph. Did I miss something?

For example, I would like to calculate the domination number of the following graph.

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);

 

 

Please Wait...