The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A354082 The independence polynomial of the n-hypercube graph evaluated at -1. 2
 0, -1, -1, 3, 7, 11, 143, 7715 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,4 COMMENTS 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. LINKS Table of n, a(n) for n=0..7. 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 EXAMPLE 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). PROG (Sage) 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 2022 CROSSREFS Cf. A027624, A354802. Sequence in context: A247229 A082598 A082599 * A123259 A116605 A361090 Adjacent sequences: A354079 A354080 A354081 * A354083 A354084 A354085 KEYWORD sign,more AUTHOR Christopher Flippen, Jun 05 2022 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified August 14 19:51 EDT 2024. Contains 375167 sequences. (Running on oeis4.)