Revision history [back]

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

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!

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 IndependentSets G=[some graph] J=IndependentSets(G)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')
F=0 t=var('t') for x in J: N=number_of_neighbors(x) for x in J: N=number_of_neighbors(x) F += t^N F 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!

          3    retagged 
      
    
        
        updated 2019-03-12 21:10:11 +0200  
    FrédéricC  
 5123  ●3 ●43 ●111  
 
 
 
  
 
 
 
  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!