Revision history [back]

You can use method minimal_dominating_sets to list the minimal distance-2 dominating sets on a modified graph H. The modified graph H has an edge between u and v if these vertices are at distance at most 2 in G.

sage: G = graphs.PathGraph(10)
sage: H = G.copy()
sage: for u in G:
....:     H.add_edges((u, v) for v in G.neighbor_iterator())
sage: for d in H.minimal_dominating_sets():
....:     print(d)
{0, 2, 4, 6, 8}
{8, 1, 4, 6}
{0, 8, 3, 6}
{8, 1, 3, 6}
{0, 8, 2, 5}
{8, 1, 2, 5}
{8, 1, 4, 5}
{0, 8, 3, 5}
{8, 1, 3, 5}
{0, 2, 4, 7, 8}
{8, 1, 4, 7}
{0, 3, 4, 7, 8}
{0, 2, 4, 6, 9}
{1, 4, 9, 6}
{0, 9, 3, 6}
{1, 3, 9, 6}
{0, 2, 5, 6, 9}
{1, 2, 5, 6, 9}
{0, 2, 4, 7, 9}
{1, 4, 9, 7}
{0, 3, 4, 7, 9}
{0, 2, 5, 7, 9}
{1, 2, 5, 7, 9}
{0, 3, 5, 7, 9}
{1, 3, 5, 7, 9}

You can use method minimal_dominating_sets to list the minimal distance-2 dominating sets on a modified graph H. The modified graph H has an edge between u and v if these vertices are at distance at most 2 in G.

sage: G = graphs.PathGraph(10)
sage: H = G.copy()
sage: for u in G:
....:     H.add_edges((u, v) for v in G.neighbor_iterator())
G.neighbor_iterator(u))
sage: for d in H.minimal_dominating_sets():
....:     print(d)
{0, 2, 4, 6, 8}
{8, 1, 4, 6}
{0, 8, 3, 6}
{8, 1, 3, 6}
{0, 8, 2, 5}
{8, 1, 2, 5}
{8, 1, 4, 5}
{0, 8, 3, 5}
{8, 1, 3, 5}
{0, 2, 4, 7, 8}
{8, 1, 4, 7}
{0, 3, 4, 7, 8}
{0, 2, 4, 6, 9}
{1, 4, 9, 6}
{0, 9, 3, 6}
{1, 3, 9, 6}
{0, 2, 5, 6, 9}
{1, 2, 5, 6, 9}
{0, 2, 4, 7, 9}
{1, 4, 9, 7}
{0, 3, 4, 7, 9}
{0, 2, 5, 7, 9}
{1, 2, 5, 7, 9}
{0, 3, 5, 7, 9}
{1, 3, 5, 7, 9}

You can use method minimal_dominating_sets to list the minimal distance-2 dominating sets on a modified graph H. The modified graph H has an edge between u and v if these vertices are at distance at most 2 in G.

sage: G = graphs.PathGraph(10)
graphs.PathGraph(5)
sage: H = G.copy()
sage: for u in G:
....:     H.add_edges((u, v) for v in G.neighbor_iterator(u))
G.breadth_first_search(u, distance=2) if u != v)
sage: for d in H.minimal_dominating_sets():
....:     print(d)
{0, 2, 4, 6, 8}
{8, 1, 4, 6}
3}
{1, 3}
{2}
{0, 8, 3, 6}
{8, 1, 3, 6}
{0, 8, 2, 5}
{8, 1, 2, 5}
{8, 1, 4, 5}
{0, 8, 3, 5}
{8, 1, 3, 5}
{0, 2, 4, 7, 8}
{8, 1, 4, 7}
{0, 3, 4, 7, 8}
{0, 2, 4, 6, 9}
4}
{1, 4, 9, 6}
{0, 9, 3, 6}
{1, 3, 9, 6}
{0, 2, 5, 6, 9}
{1, 2, 5, 6, 9}
{0, 2, 4, 7, 9}
{1, 4, 9, 7}
{0, 3, 4, 7, 9}
{0, 2, 5, 7, 9}
{1, 2, 5, 7, 9}
{0, 3, 5, 7, 9}
{1, 3, 5, 7, 9}
4}