A290888 -id:A290888 - cp's OEIS frontend

A355227 Irregular triangle read by rows where T(n,k) is the number of independent sets of size k in the n-folded cube graph.

1, 2, 1, 4, 1, 8, 12, 8, 2, 1, 16, 80, 160, 120, 16, 1, 32, 400, 2560, 9280, 20256, 28960, 31520, 29880, 24320, 16336, 8768, 3640, 1120, 240, 32, 2, 1, 64, 1792, 29120, 307440, 2239552, 11682944, 44769920, 128380880, 279211520, 464621248, 593908224, 582529360, 435648640, 245610720, 102886976, 31658620, 7189056, 1239840, 165760, 17584, 1408, 64

Offset: 2

Christopher Flippen, Jun 24 2022

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)} T(n,k)*t^k.

Since 0 <= k <= alpha(G), row n has length A058622(n-1) + 1.

			Triangle begins:
    k = 1   2   3    4    5   6
n = 2:  1,  2
n = 3:  1,  4
n = 4:  1,  8, 12,   8,   2
n = 5:  1, 16, 80, 160, 120, 16
The 5-folded cube graph has independence polynomial 1 + 16*t + 80*t^2 + 160*t^3 + 120*t^4 + 16*t^5.

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

Row sums are A290888.

Cf. A058622, A355559.

from sage.graphs.independent_sets import IndependentSets
def row(n):
    g = graphs.FoldedCubeGraph(n)
    if n % 2 == 0:
        setCounts = [0] * (pow(2, n-2) + 1)
    else:
        size = int(pow(2, n-2) - 1/4 * (1-pow(-1,n)) * math.comb(n-1, 1/2 * (n-1)) + 1)
        setCounts = [0] * size
    for Iset in IndependentSets(g):
        setCounts[len(Iset)] += 1
    return setCounts

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

Original entry on oeis.org

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

Offset: 2

Christopher Flippen, Jul 06 2022

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

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

Cf. A058622, A355227, A290888.

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

cp's OEIS Frontend

A355227 Irregular triangle read by rows where T(n,k) is the number of independent sets of size k in the n-folded cube graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Sage