|
%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
| 