A052431
Number of perfect simple undirected graphs on n nodes.
Original entry on oeis.org
1, 2, 4, 11, 33, 148, 906, 8887, 136756, 3269264, 115811998, 5855499195, 410580177259
Offset: 1
- A. Brandstaedt, V. B. Le and J. P. Spinrad, Graph Classes: A Survey, SIAM Publications, 1999.
- S. Hougardy, Home Page
- S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.
- Florian Kohl, McCabe Olsen, Raman Sanyal, Unconditional reflexive polytopes, arXiv:1906.01469 [math.CO], 2019. Also Discrete and Computational Geom., 64:2 (2020), 427-452.
- Brendan McKay, Perfect graphs
- Eric Weisstein's World of Mathematics, Perfect Graph
A187237
Number of simple connected imperfect graphs on n vertices.
Original entry on oeis.org
0, 0, 0, 0, 1, 7, 129, 3312, 134303, 8594350, 894307856, 158323596832
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.
A287511
Number of simple connected perfect non-bipartite graphs on n vertices.
Original entry on oeis.org
0, 0, 1, 3, 15, 88, 680, 7623, 126047, 3118189, 112367111, 5736020864
Offset: 1
Showing 1-5 of 5 results.
Comments