A290758 -id:A290758 - cp's OEIS frontend

A369605 Irregular triangle read by rows: T(n,k) is the number of inequivalent connected induced k-vertex subgraphs of the hypercube graph of dimension n >= 0, 1 <= k <= 2^n.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 2, 3, 1, 1, 1, 1, 1, 3, 5, 11, 19, 36, 37, 41, 24, 18, 6, 4, 1, 1, 1, 1, 1, 3, 5, 17, 44, 158, 493, 1628, 4670, 12266, 27043, 51018, 79042, 103179, 112219, 105232, 84045, 59021, 35533, 19114, 8769, 3716, 1311, 468, 130, 47, 10, 5, 1, 1

Offset: 0

Pontus von Brömssen, Jan 27 2024

Two subgraphs are equivalent if there is an automorphism of the hypercube graph that takes one to the other.
Two isomorphic subgraphs may both be counted. For example, the path with 5 vertices is an induced subgraph of the 4-dimensional hypercube in two inequivalent ways: one that is contained in a 3-dimensional subcube and one that is not. This implies that T(4,5) > A369997(4,5). (In A369997, the subgraphs are counted up to isomorphism.)
Also, number of free k-celled polycubes in n dimensions, whose width in any coordinate direction is at most 2.
Also, number of k-celled polyominoes whose cells are subsets of the (n-1)-dimensional facets of the n-dimensional cross-polytope (or orthoplex). (See A049540.)
A039754 is the corresponding sequence for not necessarily connected subgraphs.

			Triangle begins:
  1;
  1, 1;
  1, 1, 1, 1;
  1, 1, 1, 3, 2,  3,  1,  1;
  1, 1, 1, 3, 5, 11, 19, 36, 37, 41, 24, 18, 6, 4, 1, 1;
  ...
There are T(3,4) = 3 inequivalent connected induced 4-vertex subgraphs of the 3-cube: four vertices of a 2-dimensional face or three vertices of a face together with a vertex from the opposite face, adjacent to either of two inequivalent vertices from the first face.

Cf. A049540 (main diagonal), A333333 (edge-induced subgraphs).
Different ways of counting induced subgraphs in the hypercube graph (totals or by number of vertices):
            \   Subgraphs   |       All       |   Connected
  Symmetries \              |                 |
  --------------------------+-----------------+----------------
  None                      | A001146/ N/A    | A290758/A369999
  Automorphisms of the cube | A000616/A039754 | A369606/A369605
  Isomorphism               | A369996/A369995 | A369998/A369997
  (The N/A entry corresponds to rows 2^n of Pascal's triangle; A345135 comes close.)

T(n,k) = A049540(k) for k <= n+1.

T(n,k) = A039754(n,k) for k > 2^n-n.

Row 5 from Pontus von Brömssen, May 14 2025

A369998 Number of connected induced subgraphs, up to isomorphism, of the hypercube graph of dimension n.

Original entry on oeis.org

1, 2, 4, 13, 194

Offset: 0

Pontus von Brömssen, Feb 07 2024

The null subgraph is not considered to be connected.

In A369606, two isomorphic subgraphs may both be counted, namely if there is no automorphism of the hypercube graph that takes one to the other. The first difference is a(4) = 194 < A369606(4) = 209. For example, the path with 5 vertices is an induced subgraph of the 4-dimensional hypercube in two inequivalent ways: one that is contained in a 3-dimensional subcube and one that is not.

Row sums of A369997.

Cf. A290758, A369606 (up to automorphisms of the hypercube), A369996 (not necessarily connected subgraphs).

A372705 Number of connected spanning subgraphs of the n-dimensional hypercube graph.

Original entry on oeis.org

1, 1, 5, 1083, 1239326145

Offset: 0

Pontus von Brömssen, May 11 2024

a(n)/A061301(n) is the probability that the n-dimensional hypercube graph is still connected after each edge has been independently deleted with probability 1/2.

Cf. A006237, A061301, A290758, A359992, A373034, A373035.

A369606 Number of inequivalent connected induced subgraphs of the hypercube graph of dimension n.

Original entry on oeis.org

1, 2, 4, 13, 209, 709191

Offset: 0

Pontus von Brömssen, Jan 27 2024

The null subgraph is not considered to be connected.
See A369605 for details.
In A290758, equivalent subgraphs are counted separately.
A000616 is the corresponding sequence for not necessarily connected subgraphs.

Row sums of A369605.

Cf. A000616, A290758.

a(5) from Pontus von Brömssen, May 14 2025

A369999 Irregular triangle read by rows: T(n,k) is the number of connected induced k-vertex subgraphs of the hypercube graph of dimension n >= 0, 1 <= k <= 2^n.

Original entry on oeis.org

1, 2, 1, 4, 4, 4, 1, 8, 12, 24, 38, 48, 28, 8, 1, 16, 32, 96, 280, 784, 1952, 4304, 7280, 8720, 7136, 4192, 1804, 560, 120, 16, 1

Offset: 0

Pontus von Brömssen, Feb 07 2024

			Triangle begins:
   1;
   2,  1;
   4,  4,  4,   1;
   8, 12, 24,  38,  48,   28,    8,    1;
  16, 32, 96, 280, 784, 1952, 4304, 7280, 8720, 7136, 4192, 1804, 560, 120, 16, 1;
  ...

Cf. A290758 (row sums), A369605 (up to automorphisms of the hypercube), A369997 (up to isomorphism).

A288988 Number of connected (non-null) induced subgraphs of the n-halved cube graph.

Original entry on oeis.org

1, 3, 15, 251, 65039, 4292581227

Offset: 1

Eric W. Weisstein, Jun 20 2017

Eric Weisstein's World of Mathematics, Connected Graph
Eric Weisstein's World of Mathematics, Halved Cube Graph
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph

Cf. A288987, A290758.

a(6) from Andrew Howroyd, Aug 15 2017

A291704 Number of connected dominating sets in the n-hypercube graph.

Original entry on oeis.org

1, 3, 9, 115, 28853, 1920678791

Offset: 0

Eric W. Weisstein, Aug 30 2017

Eric Weisstein's World of Mathematics, Connected Dominating Set
Eric Weisstein's World of Mathematics, Hypercube Graph

Cf. A284704, A290758.

a(5) from Andrew Howroyd, Sep 04 2017

A362519 Number of vertex cuts in the hypercube graph Q_n.

Original entry on oeis.org

0, 0, 2, 88, 28242, 1770149360

Offset: 0

Eric W. Weisstein, Apr 23 2023

Eric Weisstein's World of Mathematics, Hypercube Graph
Eric Weisstein's World of Mathematics, Vertex Cut

Cf. A290758.

a(n) = 2^(2^n) - 1 - A290758(n). - Pontus von Brömssen, Apr 23 2023

a(5) (based on data in A290758) from Pontus von Brömssen, Apr 23 2023

cp's OEIS Frontend

A369605 Irregular triangle read by rows: T(n,k) is the number of inequivalent connected induced k-vertex subgraphs of the hypercube graph of dimension n >= 0, 1 <= k <= 2^n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A369998 Number of connected induced subgraphs, up to isomorphism, of the hypercube graph of dimension n.

Views

Author

Keywords

Comments

Crossrefs

A372705 Number of connected spanning subgraphs of the n-dimensional hypercube graph.

Views

Author

Keywords

Comments

Crossrefs

A369606 Number of inequivalent connected induced subgraphs of the hypercube graph of dimension n.

Views

Author

Keywords

Comments

Crossrefs

Extensions

A369999 Irregular triangle read by rows: T(n,k) is the number of connected induced k-vertex subgraphs of the hypercube graph of dimension n >= 0, 1 <= k <= 2^n.

Views

Author

Keywords

Examples

Crossrefs

A288988 Number of connected (non-null) induced subgraphs of the n-halved cube graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

A291704 Number of connected dominating sets in the n-hypercube graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

A362519 Number of vertex cuts in the hypercube graph Q_n.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions