login
A263855
Number of connected graphs on n nodes up to isomorphism with a factor of (1+x) in their independence polynomial.
0
1, 6, 38, 277, 3056, 59768, 2376028, 195245762, 31700259751
OFFSET
4,2
LINKS
F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version b3ab217.
EXAMPLE
For n = 4, the a(4)=1 solution is the path of length 3.
PROG
(Sage)
from sage.graphs.independent_sets import IndependentSets
from math import factorial
from time import time
#Function to calculate a binomial coefficient (n choose r)
def choose(n, r):
return factorial(n) / (factorial(r) * factorial(n - r))
#Function that checks if a polynomial has a certain root
def root_in_poly(poly, root):
root_list = poly.roots()
for tuple in root_list:
for elt in tuple:
if root == elt:
return True
return False
#Builds an independence polynomial for a graph
def build_ip(graph):
number_of = [0] * graph.order()
for set in IndependentSets(graph):
number_of[len_set] += 1;
poly = 0
for index in range(0, len(number_of)):
poly += (number_of[index]) * (x ** index)
return poly
ip_list = []
R.<x> = QQ[]
root = -1
for v in range(4, 10):
count = 0
for g in graphs(v):
if g.is_connected():
ip = build_ip(g)
if root_in_poly(ip, root):
ip_list.append(ip)
count += 1
print(v, ": ", count)
CROSSREFS
Sequence in context: A026940 A082427 A192941 * A354326 A221283 A064309
KEYWORD
nonn,more
AUTHOR
Ethan J. Brockmann, Nov 03 2015
EXTENSIONS
a(10)-a(12) added using tinygraph by Falk Hüffner, Jan 20 2016
STATUS
approved