May 31 2023

2
9

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