Ask Your Question

Number of neighbors of a set of vertices in a graph

asked 2019-03-12 01:34:24 +0200

Magus gravatar image

updated 2019-03-12 21:10:11 +0200

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]

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:

for x in J:
     F += t^N

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

answered 2019-03-13 09:44:59 +0200

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

answered 2019-03-12 19:07:17 +0200

vdelecroix gravatar image

updated 2019-03-12 19:09:58 +0200

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

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: 2019-03-12 01:29:53 +0200

Seen: 495 times

Last updated: Mar 13 '19