A052433
Number of perfect connected undirected simple graphs on n nodes.
Original entry on oeis.org
1, 1, 2, 6, 20, 105, 724, 7805, 126777, 3122221, 112392709, 5736233644, 404604893810
Offset: 1
- A. Brandstaedt, V. B. Le and J. P. Spinrad, Graph Classes: A Survey, SIAM Publications, 1999.
A187236
Number of simple imperfect graphs on n vertices.
Original entry on oeis.org
0, 0, 0, 0, 1, 8, 138, 3459, 137912, 8735904, 903185866, 159235673397, 50091451190693
Offset: 1
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
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.
For a list of related sequences, see cross-references in
A342211.
A286949
Number of perfect disconnected simple graphs on n nodes.
Original entry on oeis.org
0, 1, 2, 5, 13, 43, 182, 1082, 9979, 147043, 3419289, 119265551
Offset: 1
\bar K_2; (1 graph)
\bar K_3, K_1 \cup K_2; (2 graphs)
\bar K_4, P_2 \cup 2 K_1, P_3 \cup K_1, C_3 \cup K_1, 2P_2 (5 graphs)
Here, \bar indicates a graph complement and \cup a (disjoint) graph union.
A287512
Number of simple perfect non-bipartite graphs on n vertices.
Original entry on oeis.org
0, 0, 1, 4, 20, 113, 818, 8584, 135637, 3263785, 115779695, 5855248060
Offset: 1
Showing 1-5 of 5 results.
Comments