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

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

Offset

2,2

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.

Links

Table of n, a(n) for n=2..8.

Eric Weisstein's World of Mathematics, Independence polynomial

Eric Weisstein's World of Mathematics, Folded cube graph

Example

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).

Prog

(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

Crossrefs

Cf. A058622, A355227, A290888.

Sequence in context: A128415 A227795 A090479 * A227758 A304638 A141903

Adjacent sequences: A355556 A355557 A355558 * A355560 A355561 A355562

Keyword

sign,more

Author

Christopher Flippen, Jul 06 2022

Status

approved