Ask Your Question
0

Number of neighbors of a set of vertices in a graph

asked 2019-03-11 19:34:24 -0500

Magus gravatar image

updated 2019-03-12 15:10:11 -0500

FrédéricC gravatar image

Hi all, I'd like to know how to get the number of vertices that are adjacent to a given set of vertices in a graph. I have the following skeleton:

from sage.graphs.independent_sets import IndependentSets
G=[some graph]
J=IndependentSets(G)

And I would like to know the number of neighbors of x for each x in J (i.e., the number of vertices of G\x that are adjacent to some vertex in x). Ideally I would like something like:

F=0
t=var('t')
for x in J:
     N=number_of_neighbors(x)
     F += t^N
F

If G is a four cycle then number_of_neighbors(x)=2 for any subset x of two vertices of G, and the polynomial F above should be 1+6t^2 (because there is the empty independent set, 4 independent sets of size 1 each with 2 neighbors, and 2 independent sets of size 2 each with 2 neighbors). I appreciate your help!

edit retag flag offensive close merge delete

2 answers

Sort by » oldest newest most voted
0

answered 2019-03-12 13:07:17 -0500

vdelecroix gravatar image

updated 2019-03-12 13:09:58 -0500

Here is one (not so elegant) possibility

sage: J = IndependentSets(graphs.CycleGraph(4))
sage: t = polygen(ZZ, 't')
sage: F = 0
sage: for x in J:
....:     N = len(set().union(*[G.neighbor_iterator(v) for v in x]))
....:     F += t^N
sage: F
6t^2 + 1

It is not so elegant because it constructs the explicit list of neighbors.

edit flag offensive delete link more
1

answered 2019-03-13 03:44:59 -0500

You want the vertex boundary of a set of vertices.

sage: from sage.graphs.independent_sets import IndependentSets
sage: G = graphs.CycleGraph(4)
sage: t = polygen(ZZ, 't')
sage: sum(t^len(G.vertex_boundary(x)) for x in IndependentSets(G))
6*t^2 + 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

Stats

Asked: 2019-03-11 19:29:53 -0500

Seen: 39 times

Last updated: Mar 13