A263855 - OEIS

%I #25 Jan 20 2016 08:07:45

%S 1,6,38,277,3056,59768,2376028,195245762,31700259751

%N Number of connected graphs on n nodes up to isomorphism with a factor of (1+x) in their independence polynomial.

%H F. Hüffner, <a href="https://github.com/falk-hueffner/tinygraph">tinygraph</a>, software for generating integer sequences based on graph properties, version b3ab217.

%e For n = 4, the a(4)=1 solution is the path of length 3.

%o (Sage)

%o from sage.graphs.independent_sets import IndependentSets

%o from math import factorial

%o from time import time

%o #Function to calculate a binomial coefficient (n choose r)

%o def choose(n, r):

%o     return factorial(n) / (factorial(r) * factorial(n - r))

%o #Function that checks if a polynomial has a certain root

%o def root_in_poly(poly, root):

%o     root_list = poly.roots()

%o     for tuple in root_list:

%o         for elt in tuple:

%o             if root == elt:

%o                 return True

%o     return False

%o #Builds an independence polynomial for a graph

%o def build_ip(graph):

%o     number_of = [0] * graph.order()

%o     for set in IndependentSets(graph):

%o         number_of[len_set] += 1;

%o     poly = 0

%o     for index in range(0, len(number_of)):

%o         poly += (number_of[index]) * (x ** index)

%o     return poly

%o ip_list = []

%o R.<x> = QQ[]

%o root = -1

%o for v in range(4, 10):

%o     count = 0

%o     for g in graphs(v):

%o         if g.is_connected():

%o             ip = build_ip(g)

%o             if root_in_poly(ip, root):

%o                 ip_list.append(ip)

%o                 count += 1

%o     print(v, ": ", count)

%K nonn,more

%O 4,2

%A _Ethan J. Brockmann_, Nov 03 2015

%E a(10)-a(12) added using tinygraph by _Falk Hüffner_, Jan 20 2016