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

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

Offset

4,2

Links

Table of n, a(n) for n=4..12.

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

Adjacent sequences: A263852 A263853 A263854 * A263856 A263857 A263858

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