# Number of neighbors of a set of vertices in a graph 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 close merge delete

Sort by » oldest newest most voted

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

more

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.

more