A355559 The independence polynomial of the n-folded cube graph evaluated at -1.

-1, -3, -1, 9, 131, 253, 25607

Offset: 2

Author

Christopher Flippen, Jul 06 2022

Keywords

• sign
• more

Comments

The independence number alpha(G) of a graph is the cardinality of the largest independent vertex set. The n-folded cube has alpha(G) = A058622(n-1). The independence polynomial for the n-folded cube is given by Sum_{k=0..alpha(G)} A355227(n,k)*t^k, meaning that a(n) is the alternating sum of row n of A355227.

Examples

			Row 5 of A355227 is 1, 16, 80, 160, 120, 16. This means the 5-folded cube graph has independence polynomial 1 + 16*t + 80*t^2 + 160*t^3 + 120*t^4 + 16*t^5. Taking the alternating row sum of row 5, or evaluating the polynomial at -1, gives us 1 - 16 + 80 - 160 + 120 - 16 = 9 = a(5).
		

Links

• Eric Weisstein's World of Mathematics, Independence polynomial
• Eric Weisstein's World of Mathematics, Folded cube graph

Crossrefs

Cf. A058622, A355227, A290888.

Programs

Sage

from sage.graphs.independent_sets import IndependentSets
def a(n):
    icount=0
    for Iset in IndependentSets(graphs.FoldedCubeGraph(n)):
        if len(Iset) % 2 == 0:
            icount += 1
        else:
            icount += -1
    return icount