ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 13 Mar 2019 03:44:59 -0500Number of neighbors of a set of vertices in a graphhttp://ask.sagemath.org/question/45764/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!Mon, 11 Mar 2019 19:29:53 -0500http://ask.sagemath.org/question/45764/number-of-neighbors-of-a-set-of-vertices-in-a-graph/Answer by David Coudert for <p>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:</p>
<pre><code>from sage.graphs.independent_sets import IndependentSets
G=[some graph]
J=IndependentSets(G)
</code></pre>
<p>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:</p>
<pre><code>F=0
t=var('t')
for x in J:
N=number_of_neighbors(x)
F += t^N
F
</code></pre>
<p>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!</p>
http://ask.sagemath.org/question/45764/number-of-neighbors-of-a-set-of-vertices-in-a-graph/?answer=45775#post-id-45775You 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
Wed, 13 Mar 2019 03:44:59 -0500http://ask.sagemath.org/question/45764/number-of-neighbors-of-a-set-of-vertices-in-a-graph/?answer=45775#post-id-45775Answer by vdelecroix for <p>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:</p>
<pre><code>from sage.graphs.independent_sets import IndependentSets
G=[some graph]
J=IndependentSets(G)
</code></pre>
<p>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:</p>
<pre><code>F=0
t=var('t')
for x in J:
N=number_of_neighbors(x)
F += t^N
F
</code></pre>
<p>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!</p>
http://ask.sagemath.org/question/45764/number-of-neighbors-of-a-set-of-vertices-in-a-graph/?answer=45772#post-id-45772Here 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.Tue, 12 Mar 2019 13:07:17 -0500http://ask.sagemath.org/question/45764/number-of-neighbors-of-a-set-of-vertices-in-a-graph/?answer=45772#post-id-45772