Ask Your Question
0

Is there any code to list all minimal k-distance dominating sets of a simple graph G in sagemath?

asked 2023-04-03 07:51:59 +0200

anonymous user

Anonymous

A distance- k-dominating set S of a graph G is a set of its vertices of minimal cardinality such that any vertex of G is in S or is at distance at most k from a vertex in S.

I need to find all minimal distance 2- dominating sets of a simple graph G.

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
0

answered 2023-04-08 11:23:40 +0200

updated 2023-04-08 11:31:29 +0200

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(5)
sage: H = G.copy()
sage: for u in G:
....:     H.add_edges((u, v) for v in G.breadth_first_search(u, distance=2) if u != v)
sage: for d in H.minimal_dominating_sets():
....:     print(d)
{0, 3}
{1, 3}
{2}
{0, 4}
{1, 4}
edit flag offensive delete link more

Comments

This is now Issue 35461.

David Coudert gravatar imageDavid Coudert ( 2023-04-08 14:03:28 +0200 )edit

Thanks a lot dear sir..

vairas_sa gravatar imagevairas_sa ( 2023-04-15 08:27:46 +0200 )edit

i need some more help in code... can you help me sir?

vairas_sa gravatar imagevairas_sa ( 2023-04-15 08:28:34 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2023-04-03 07:51:59 +0200

Seen: 120 times

Last updated: Apr 08 '23