A342211 -id:A342211 - cp's OEIS frontend

A342212 Largest number of maximal bipartite node-induced subgraphs of an n-node graph.

1, 1, 3, 6, 10, 15, 21, 38, 64

Offset: 1

Pontus von Brömssen, Mar 05 2021

This sequence is log-superadditive, i.e., a(m+n) >= a(m)*a(n). By Fekete's subadditive lemma, it follows that the limit of a(n)^(1/n) exists and equals the supremum of a(n)^(1/n). - Pontus von Brömssen, Mar 03 2022

Byskov, Madsen, and Skjernaa (2005) construct a 10-node graph with 105 maximal bipartite subgraphs, so a(10) >= 105.

			All optimal graphs (i.e., graphs having n nodes and a(n) maximal bipartite subgraphs) for 1 <= n <= 9 are listed below. Here, FCB(n_1, ..., n_k) denotes the full cyclic braid graph with cluster sizes n_1, ..., n_k, as defined by Morrison and Scott (2017), i.e., the graph obtained by arranging complete graphs of orders n_1, ..., n_k (in that order) in a cycle, and joining all pairs of nodes in neighboring parts with edges. (The graph in the paper by Byskov, Madsen, and Skjernaa, which shows that a(10) >= 105, is FCB(2, 2, 2, 2, 2).)
        n = 1: the 1-node graph;
        n = 2: the complete graph and the empty graph;
  3 <= n <= 6: the complete graph;
        n = 7: FCB(1, 1, 2, 1, 2) (the Moser spindle) and the complete graph;
        n = 8: FCB(1, 2, 1, 2, 2) and the 4-antiprism graph;
        n = 9: FCB(1, 2, 2, 1, 3).

Jesper Makholm Byskov, Bolette Ammitzbøll Madsen, and Bjarke Skjernaa, On the number of maximal bipartite subgraphs of a graph, Journal of Graph Theory 48 (2005), 127-132.
Natasha Morrison and Alex Scott, Maximising the number of induced cycles in a graph, Journal of Combinatorial Theory Series B 126 (2017), 24-61.

Cf. A005142, A033995.

For a list of related sequences, see cross-references in A342211.

a(m+n) >= a(m)*a(n).
a(n) <= n*12^(n/4). (Byskov, Madsen, and Skjernaa (2005))
1.5926... = 105^(1/10) <= lim_{n->oo} a(n)^(1/n) <= 12^(1/4) = 1.8612... . (Byskov, Madsen, and Skjernaa (2005))

A342213 Largest number of maximal planar node-induced subgraphs of an n-node graph.

Original entry on oeis.org

1, 1, 1, 1, 5, 15, 35, 70, 126, 211

Offset: 1

Pontus von Brömssen, Mar 05 2021

This sequence is log-superadditive, i.e., a(m+n) >= a(m)*a(n). By Fekete's subadditive lemma, it follows that the limit of a(n)^(1/n) exists and equals the supremum of a(n)^(1/n). - Pontus von Brömssen, Mar 03 2022

a(11) >= 381, because the complete 5-partite graph K_{1,1,3,3,3} has 381 maximal planar subgraphs.

			For 4 <= n <= 9, a(n) = binomial(n,4) = A000332(n) and the complete graph is optimal, but a(10) = 211 > 210 = binomial(10,4) with the optimal graph being the complete 6-partite graph K_{1,1,1,1,3,3}. The optimal graph is unique when 5 <= n <= 10.

Cf. A000332, A003094, A005470.

For a list of related sequences, see cross-references in A342211.

a(m+n) >= a(m)*a(n).

Lim_{n->oo} a(n)^(1/n) >= 381^(1/11) = 1.71644... .

A342324 Largest number of maximal chordal node-induced subgraphs of an n-node graph.

Original entry on oeis.org

1, 1, 1, 4, 5, 12, 16, 36, 81

Offset: 1

Pontus von Brömssen, Mar 08 2021

This sequence is log-superadditive, i.e., a(m+n) >= a(m)*a(n). By Fekete's subadditive lemma, it follows that the limit of a(n)^(1/n) exists and equals the supremum of a(n)^(1/n). - Pontus von Brömssen, Mar 03 2022

			All graphs with at most three nodes are chordal, so a(n) = 1 for n <= 3 and any graph will be optimal (containing 1 maximal chordal subgraph).
For 4 <= n <= 9, the following graphs are optimal:
  n = 4: the 4-cycle;
  n = 5: the 5-cycle and the complete bipartite graph K_{2,3};
  n = 6: the 3-prism graph and the octahedral graph;
  n = 7: the 3-prism graph with one edge (not in a triangle) subdivided by an additional node, and the complete tripartite graph K_{2,2,3};
  n = 8: the gyrobifastigium graph;
  n = 9: the Paley graph of order 9.

Cf. A048192, A048193.

For a list of related sequences, see cross-references in A342211.

a(m+n) >= a(m)*a(n).

Lim a(n)^(1/n) >= 3^(4/9).

A352208 Largest number of maximal 3-colorable node-induced subgraphs of an n-node graph.

Original entry on oeis.org

1, 1, 1, 4, 10, 20, 35, 56, 84

Offset: 1

Pontus von Brömssen, Mar 08 2022

This sequence is log-superadditive, i.e., a(m+n) >= a(m)*a(n). By Fekete's subadditive lemma, it follows that the limit of a(n)^(1/n) exists and equals the supremum of a(n)^(1/n).
In the following, FCB(n_1, ..., n_k) denotes the full cyclic braid graph with cluster sizes n_1, ..., n_k, as defined by Morrison and Scott (2017), i.e., the graph obtained by arranging complete graphs of orders n_1, ..., n_k (in that order) in a cycle, and joining all pairs of nodes in neighboring parts with edges.
  a(10) >= 140 by FCB(2, 2, 2, 2, 2);
  a(11) >= 268 by FCB(2, 2, 2, 2, 3);
  a(12) >= 517 by FCB(2, 2, 3, 2, 3);
  a(13) >= 911 by FCB(2, 3, 2, 3, 3);
  a(14) >= 1515 by FCB(2, 3, 3, 3, 3);
  a(15) >= 2525 by FCB(3, 3, 3, 3, 3).

			For 3 <= n <= 9, a(n) = binomial(n,3) = A000292(n-2) and the complete graph is optimal (it is the unique optimal graph for 4 <= n <= 9), but a(10) >= 140 > binomial(10,3).

Natasha Morrison and Alex Scott, Maximising the number of induced cycles in a graph, Journal of Combinatorial Theory Series B 126 (2017), 24-61.

Cf. A000292, A076315, A076322.

For a list of related sequences, see cross-references in A342211.

a(m+n) >= a(m)*a(n).

Limit_{n->oo} a(n)^(1/n) >= 911^(1/13) = 1.68909... .

A352209 Largest number of maximal perfect node-induced subgraphs of an n-node graph.

Original entry on oeis.org

1, 1, 1, 1, 5, 5, 13, 18, 42

Offset: 1

Pontus von Brömssen, Mar 08 2022

This sequence is log-superadditive, i.e., a(m+n) >= a(m)*a(n). By Fekete's subadditive lemma, it follows that the limit of a(n)^(1/n) exists and equals the supremum of a(n)^(1/n).

			All graphs with at most four nodes are perfect, so a(n) = 1 for n <= 4 and any graph is optimal.
All optimal graphs (i.e., graphs that have n nodes and a(n) maximal perfect subgraphs) for 5 <= n <= 9 are listed below. Since a graph is perfect if and only if its complement is perfect, the optimal graphs come in complementary pairs.
  n = 5: the 5-cycle;
  n = 6: the wheel graph with any subset of the spokes removed (8 graphs in total);
  n = 7: the chestahedral graph and its complement;
  n = 8: the bislit cube graph, the snub disphenoidal graph, and their complements;
  n = 9: the bislit cube graph with an additional node with edges to two neighboring nodes of degree 4 and to the two nodes of degree 3 on the opposite face of the cube, the snub disphenoidal graph with an additional node with edges to the four nodes of degree 4, and their complements.

Cf. A052431, A052433.

For a list of related sequences, see cross-references in A342211.

a(m+n) >= a(m)*a(n).

Limit_{n->oo} a(n)^(1/n) >= 42^(1/9) = 1.51482... .

A352210 Largest number of maximal 2-degenerate node-induced subgraphs of an n-node graph.

Original entry on oeis.org

1, 1, 1, 4, 10, 20, 35, 56, 97

Offset: 1

Pontus von Brömssen, Mar 08 2022

This sequence is log-superadditive, i.e., a(m+n) >= a(m)*a(n). By Fekete's subadditive lemma, it follows that the limit of a(n)^(1/n) exists and equals the supremum of a(n)^(1/n).

			For 3 <= n <= 8, a(n) = binomial(n,3) = A000292(n-2) and the complete graph is optimal, but a(9) = 97 > binomial(9,3) with the optimal graph being the complement of the disjoint union of K_3 and K_{3,3}. The optimal graph is unique when 4 <= n <= 9.

Cf. A000292, A352067.

For a list of related sequences, see cross-references in A342211.

a(m+n) >= a(m)*a(n).

Limit_{n->oo} a(n)^(1/n) >= 97^(1/9) = 1.66246... .

A352211 Largest number of maximal node-induced cluster subgraphs of an n-node graph.

Original entry on oeis.org

1, 1, 3, 6, 8, 11, 18, 36, 48

Offset: 1

Pontus von Brömssen, Mar 08 2022

This sequence is log-superadditive, i.e., a(m+n) >= a(m)*a(n). By Fekete's subadditive lemma, it follows that the limit of a(n)^(1/n) exists and equals the supremum of a(n)^(1/n).

Assuming that there exists a disconnected optimal graph for n >= 7 (this is the case for 7 <= n <= 9), it would hold that a(n) = 6*a(n-4) for n >= 7.

			For 3 <= n <= 9, the following are all optimal graphs, i.e., graphs that have n nodes and a(n) maximal cluster subgraphs:
  n = 3: the path of length 2;
  n = 4: the 4-cycle;
  n = 5: K_{2,3};
  n = 6: the Hajós graph (also known as a Sierpiński sieve graph), the square pyramid with an additional node with an edge to the top of the pyramid, K_{3,3}, the prism graph, and the octahedral graph;
  n = 7: the disjoint union of any optimal graph for n = 3 and any optimal graph for n = 4;
  n = 8: the disjoint union of any two optimal graphs for n = 4;
  n = 9: the disjoint union of any optimal graph for n = 4 and any optimal graph for n = 5.

Cf. A000041 (number of cluster graphs on n nodes).

For a list of related sequences, see cross-references in A342211.

a(m+n) >= a(m)*a(n).

Limit_{n->oo} a(n)^(1/n) >= 6^(1/4) = 1.56508... .

A352212 Largest number of maximal triangle-free node-induced subgraphs of an n-node graph.

Original entry on oeis.org

1, 1, 3, 6, 10, 15, 21, 36, 60

Offset: 1

Pontus von Brömssen, Mar 08 2022

This sequence is log-superadditive, i.e., a(m+n) >= a(m)*a(n). By Fekete's subadditive lemma, it follows that the limit of a(n)^(1/n) exists and equals the supremum of a(n)^(1/n).

Assuming that there exists a disconnected optimal graph for n >= 8 (this is the case for n = 8 and n = 9), it would hold that a(10) = 100, a(11) = 150, a(12) = 225, and a(n) = 10*a(n-5) for n >= 13.

			For 2 <= n <= 7, a(n) = binomial(n,2) = A000217(n-1) and the complete graph is optimal (it is the unique optimal graph for 3 <= n <= 7), but a(8) = 36 > binomial(8,2), with the optimal graphs being K_4 + K_4, with up to 4 additional node-disjoint edges. For n = 9 the optimal graphs are K_4 + K_5 with up to 4 additional node-disjoint edges.

Cf. A000217, A006785, A024607.

For a list of related sequences, see cross-references in A342211.

a(m+n) >= a(m)*a(n).

Limit_{n->oo} a(n)^(1/n) >= 10^(1/5) = 1.58489... .

A352213 Largest number of maximal cographical node-induced subgraphs of an n-node graph.

Original entry on oeis.org

1, 1, 1, 4, 10, 12, 23, 38, 64

Offset: 1

Pontus von Brömssen, Mar 08 2022

This sequence is log-superadditive, i.e., a(m+n) >= a(m)*a(n). By Fekete's subadditive lemma, it follows that the limit of a(n)^(1/n) exists and equals the supremum of a(n)^(1/n).

			All graphs with at most three nodes are cographs, so a(n) = 1 for n <= 3 and any graph is optimal.
All optimal graphs (i.e., graphs that have n nodes and a(n) maximal cographical subgraphs) for 4 <= n <= 9 are listed below. Since a graph is a cograph if and only if its complement is a cograph, the optimal graphs come in complementary pairs.
  n = 4: the path of length 3 (self-complementary);
  n = 5: the 5-cycle (self-complementary);
  n = 6: the Hajós graph (also known as a Sierpiński sieve graph) and its complement;
  n = 7: the elongated triangular pyramid and its complement;
  n = 8: the Möbius ladder and its complement (the antiprism graph);
  n = 9: the pentagonal bipyramid with an additional path of length 3 between the two apex nodes (self-complementary).

Cf. A000084, A000669.

For a list of related sequences, see cross-references in A342211.

a(m+n) >= a(m)*a(n).

Limit_{n->oo} a(n)^(1/n) >= 64^(1/9) = 1.58740... .

A352214 Largest number of maximal claw-free node-induced subgraphs of an n-node graph.

Original entry on oeis.org

1, 1, 1, 4, 7, 11, 23, 44, 71

Offset: 1

Pontus von Brömssen, Mar 08 2022

This sequence is log-superadditive, i.e., a(m+n) >= a(m)*a(n). By Fekete's subadditive lemma, it follows that the limit of a(n)^(1/n) exists and equals the supremum of a(n)^(1/n).

			All graphs with at most three nodes are claw-free, so a(n) = 1 for n <= 3 and any graph is optimal.
For 4 <= n <= 9, the following are all optimal graphs, i.e., graphs that have n nodes and a(n) maximal claw-free subgraphs:
  n = 4: K_{1,3};
  n = 5: K_{1,4};
  n = 6: K_{1,5}, K_{3,3} with one edge removed, and K_{3,3};
  n = 7: K_{3,4} with one edge removed;
  n = 8: K_{4,4} with one edge removed;
  n = 9: K_{4,5} with one edge removed.

Cf. A022562, A086991.

For a list of related sequences, see cross-references in A342211.

a(m+n) >= a(m)*a(n).

Limit_{n->oo} a(n)^(1/n) >= 71^(1/9) = 1.60581... .

cp's OEIS Frontend

A342212 Largest number of maximal bipartite node-induced subgraphs of an n-node graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A342213 Largest number of maximal planar node-induced subgraphs of an n-node graph.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A342324 Largest number of maximal chordal node-induced subgraphs of an n-node graph.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A352208 Largest number of maximal 3-colorable node-induced subgraphs of an n-node graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A352209 Largest number of maximal perfect node-induced subgraphs of an n-node graph.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A352210 Largest number of maximal 2-degenerate node-induced subgraphs of an n-node graph.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A352211 Largest number of maximal node-induced cluster subgraphs of an n-node graph.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A352212 Largest number of maximal triangle-free node-induced subgraphs of an n-node graph.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A352213 Largest number of maximal cographical node-induced subgraphs of an n-node graph.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A352214 Largest number of maximal claw-free node-induced subgraphs of an n-node graph.

Views

Author

Keywords

Comments