Ask Your Question

$k$-independence number in graphs

asked 2021-02-27 16:49:39 +0100

salam gravatar image

I know how to find the independence number in graphs in sagemath. I want to obtain a new parameter called $k$-independence number in graphs which means the maximum size of a set of vertices at pairwise distance greater than $k$.

Would you please tell me how I can find this parameter in a graph?

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2021-02-28 03:06:31 +0100

Max Alekseyev gravatar image

For a given graph $G$, we can construct a new graph $H$ on the same set of vertices as $G$ such that two vertices $u$ and $v$ are connected in $H$ iff the distance between $u,v$ in $G$ is greater than $k$. Then the $k$-independence number of $G$ equals the clique number of $H$.

Here is a sample code, which computes 1-independence number of Petersen graph.

from sage.graphs.distances_all_pairs import distances_all_pairs

def k_independence_number(G,k):
    D = distances_all_pairs(G)   # pairwise distances
    H = Graph([ G.vertices(), [(u,v) for u,N in D.items() for v,d in N.items() if d>k] ])
    return H.clique_number()

print( k_independence_number(graphs.PetersenGraph(),1) )
edit flag offensive delete link more

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


Asked: 2021-02-27 16:49:39 +0100

Seen: 300 times

Last updated: Feb 28 '21