Christopher Flippen - cp's OEIS frontend

A355558 The independence polynomial of the n-halved cube graph evaluated at -1.

0, -1, -3, -3, 25, -135, -2079, 1879969

Offset: 1

Christopher Flippen, Jul 06 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)} A355226(n,k)*t^k, meaning that a(n) is the alternating sum of row n of A355226.

			Row 5 of A355226 is 1, 16, 40. This means the 5-halved cube graph has independence polynomial 1 + 16*t + 40*t^2. Taking the alternating row sum of row 5, or evaluating the polynomial at -1, gives us 1 - 16 + 40 = 25 = a(5).

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

Cf. A005864, A355226, A288943.

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

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

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.

			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

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.

Original entry on oeis.org

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

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.

Original entry on oeis.org

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

A354082 The independence polynomial of the n-hypercube graph evaluated at -1.

Original entry on oeis.org

0, -1, -1, 3, 7, 11, 143, 7715

Offset: 0

Christopher Flippen, Jun 05 2022

The independence number alpha(G) of a graph is the cardinality of the largest independent vertex set. The n-hypercube has alpha(G) = 1 for n = 0 and alpha(G) = 2^(n-1) for n >= 1. The independence polynomial for the n-hypercube is given by Sum_{k=0..alpha(G)} A354802(n,k)*t^k, meaning that a(n) is the alternating sum of row n of A354802.
Jenssen, Perkins and Potukuchi proved asymptotics for independent sets of given size.
It appears that this sequence remains positive for n > 3.

			Row 3 of A354802 is 1, 8, 16, 8, 2. This means the 3-hypercube cube graph has independence polynomial 1 + 8*t + 16*t^2 + 8*t^3 + 2*t^4. Taking the alternating row sum of row 3, or evaluating the polynomial at -1, gives us 1 - 8 + 16 - 8 + 2 = 3 = a(3).

M. Jenssen, W. Perkins and A. Potukuchi, Independent sets of a given size and structure in the hypercube, Combinatorics, Probability and Computing, 2022, 1-19; see also arXiv:2106.09709 [math.CO], 2021-2022.
Eric Weisstein's World of Mathematics, Hypercube graph
Eric Weisstein's World of Mathematics, Independence polynomial

Cf. A027624, A354802.

from sage.graphs.connectivity import connected_components
def recurse(g):
    if g.order() == 0:
            return 1
    comp = g.connected_components()
    if len(comp[-1]) == 1:
        return 0
    elif len(comp) > 1:
        prod = 1
        for c in comp:
            if prod == 0:
                return 0
            else:
                prod = prod*recurse(g.subgraph(vertices=c))
        return prod
    min_degree_vertex = g.vertices()[0]
    for v in g.vertices():
        if g.degree(v) < g.degree(min_degree_vertex):
            min_degree_vertex = v
    to_remove_edge =  g.edges_incident(min_degree_vertex)[0]
    to_remove_vertices = [to_remove_edge[0], to_remove_edge[1]]
    to_remove_vertices.extend(g.neighbors(to_remove_edge[0]))
    to_remove_vertices.extend(g.neighbors(to_remove_edge[1]))
    to_remove_vertices = list(set(to_remove_vertices))
    without_neighborhoods = copy(g)
    without_edge = copy(g)
    without_neighborhoods.delete_vertices(to_remove_vertices)
    without_edge.delete_edge(to_remove_edge)
    return recurse(without_edge) - recurse(without_neighborhoods)
def a(n):
    if n == 0:
        return recurse(graphs.CompleteGraph(1))
    else:
        return recurse(graphs.CubeGraph(n))
# Christopher Flippen and Scott Taylor, Jun 05 2022

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

Original entry on oeis.org

1, 1, 1, 2, 1, 4, 2, 1, 8, 16, 8, 2, 1, 16, 88, 208, 228, 128, 56, 16, 2, 1, 32, 416, 2880, 11760, 29856, 48960, 54304, 44240, 29920, 17952, 9088, 3672, 1120, 240, 32, 2, 1, 64, 1824, 30720, 342400, 2682432, 15328064, 65515840, 213464240, 538811200, 1070860384, 1708551424, 2245780976, 2517976640, 2509047680

Offset: 0

Christopher Flippen, Jun 06 2022

The independence number alpha(G) of a graph is the cardinality of the largest independent vertex set. The n-hypercube has alpha(G) = 1 for n = 0 and alpha(G) = 2^(n-1) for n >= 1. The independence polynomial for the n-hypercube is given by Sum_{k=0..alpha(G)} T(n,k)*t^k.
Since 0 <= k <= alpha(G), row n has length 2^(n-1) + 1 except for n = 0 which has length 2.
Jenssen, Perkins and Potukuchi proved asymptotics for independent sets of given size.

			Triangle begins:
  n=0: 1, 1
  n=1: 1, 2
  n=2: 1, 4, 2
  n=3: 1, 8, 16, 8, 2
  n=4: 1, 16, 88, 208, 228, 128, 56, 16, 2
The 3-hypercube graph has independence polynomial 1 + 8*t + 16*t^2 + 8*t^3 + 2*t^4.

Christopher Flippen, Table of n, a(n) for n = 0..71
M. Jenssen, W. Perkins and A. Potukuchi, Independent sets of a given size and structure in the hypercube, Combinatorics, Probability and Computing, 2022, 1-19; see also arXiv:2106.09709 [math.CO], 2021-2022.
Eric Weisstein's World of Mathematics, Hypercube graph
Eric Weisstein's World of Mathematics, Independence polynomial

Cf. A027624 (row sums), A354082 (alternating sums).

from sage.graphs.independent_sets import IndependentSets
def row(n):
    if n == 0:
        g = graphs.CompleteGraph(1)
        setCounts = [0, 0]
    else:
        g = graphs.CubeGraph(n)
        setCounts = [0] * (pow(2,n - 1) + 1)
    for Iset in IndependentSets(g):
        setCounts[len(Iset)] += 1
    return setCounts
# Christopher Flippen and Scott Taylor, Jun 06 2022

cp's OEIS Frontend

User: Christopher Flippen

A355558 The independence polynomial of the n-halved cube graph evaluated at -1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Sage

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Sage

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

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

A354082 The independence polynomial of the n-hypercube graph evaluated at -1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Sage

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Sage