A355558 -id:A355558 - cp's OEIS frontend

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

1, 1, 1, 2, 1, 4, 1, 8, 4, 1, 16, 40, 1, 32, 256, 480, 120, 1, 64, 1344, 11200, 36400, 40320, 13440, 1920, 240, 1, 128, 6336, 156800, 2104480, 15644160, 63672000, 136970880, 147748560, 76396800, 21087360, 4273920, 840000, 161280, 28800, 3840, 240

Offset: 1

Christopher Flippen, Jun 24 2022

The independence number alpha(G) of a graph is the cardinality of the largest independent vertex set. The n-halved graph has alpha(G) = A005864(n). The independence polynomial for the n-halved cube is given by Sum_{k=0..alpha(G)} T(n,k)*t^k.

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

			Triangle begins:
    k = 0   1   2
n = 1:  1,  1
n = 2:  1,  2
n = 3:  1,  4
n = 4:  1,  8,  4
n = 5:  1, 16, 40
The 4-halved cube graph has independence polynomial 1 + 8*t + 4*t^2.

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

Row sums are A288943.

Cf. A005864, A355558.

from sage.graphs.independent_sets import IndependentSets
from collections import Counter
def row(n):
    if n == 1:
        g = graphs.CompleteGraph(1)
    else:
        g = graphs.HalfCube(n)
    setCounts = Counter()
    for Iset in IndependentSets(g):
        setCounts[len(Iset)] += 1
    outList = [0] * len(setCounts)
    for n in range(0,len(setCounts)):
        outList[n] = setCounts[n]
    return outList

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Sage