A006785 -id:A006785 - cp's OEIS frontend

A304125 Number of simple graphs with n vertices which contain no K5 subgraph.

Original entry on oeis.org

1, 2, 4, 11, 33, 150, 986, 11416, 245440, 10164119, 793907916, 114150623175, 29709609171994

Offset: 1

Brendan McKay, May 06 2018

The graphs do not need to be connected.

Cf. A000088, A006785 (no K3), A115196 (graphs by clique number), A304124 (no K4).

a(n) = 1+A052450(n)+A052451(n)+A052452(n).

a(13) from Brendan McKay, May 08 2018

A005007 Number of cubic (i.e., regular of degree 3) generalized Moore graphs with 2n nodes.

Original entry on oeis.org

0, 1, 2, 2, 1, 2, 7, 6, 1, 1, 0, 1, 2, 9, 40, 56, 3, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 0, 0

Offset: 1

N. J. A. Sloane

nonn

A generalized Moore graph is a regular graph of degree r where the counts of vertices at each distance from any vertex are 1, r, r(r-1), r(r-1)^2, r(r-1)^3, ... with the last distance having every other vertex. That is, all the levels are full except possibly the last which must have the rest. Alternatively, the girth is as great as the naive bound allows and the diameter is as little as the naive bound allows. Or, the average distance between pairs of vertices achieves the naive lower bound. As far as I know, it is an open problem if there are infinitely many generalized Moore graphs of each degree. - Brendan McKay, Oct 06 2003

a(35)>=1. a(n)=0 for n=94-112 and n=190-202. It is unknown if there are infinitely many. - Brendan McKay, May 02 2025

			The counts are for graphs with 2, 4, 6, 8, ... nodes. In particular, there is a unique graph with 10 nodes.

B. D. McKay and R. G. Stanton, The current status of the generalized Moore graph problem, pp. 21-31 of Combinatorial Mathematics VI (Armidale 1978), Lect. Notes Math. 748, 1979.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Brendan McKay, Emails to N. J. A. Sloane, 1991
Eric Weisstein's World of Mathematics, Generalized Moore Graph

Terms a(16)-a(32) from Brendan McKay, May 02 2025

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... .

A049367 Number of triangle-free planar graphs with n nodes.

Original entry on oeis.org

1, 2, 3, 7, 14, 37, 102, 367, 1532, 8091, 50775, 372417, 3045985, 26989204, 252934543

Offset: 1

Brendan McKay

F. Hüffner, tinygraph, software for generating integer sequences based on graph properties, version 9766535.

Cf. A049368 (inverse Euler transform), A006785.

a(12)-a(15) added using tinygraph by Falk Hüffner, May 09 2019

A292528 Minimal number of vertices in a triangle-free graph with chromatic number n.

Original entry on oeis.org

1, 2, 5, 11, 22

Offset: 1

Charles R Greathouse IV, Feb 01 2018

Mycielski's construction proves that this sequence is infinite.
Harary states in an exercise (12.19) that a(4) <= 11. Chvátal proves that a(4) = 11 and gives a proof of uniqueness. Jensen & Royle prove that a(5) = 22.
Goedgebeur proves that 32 <= a(6) <= 40. - Charles R Greathouse IV, Mar 06 2018

			The unique graph for a(1) = 1 is a lone vertex.
The unique graph for a(2) = 2 is two vertices connected by an edge.
The unique graph for a(3) = 5 is the cycle graph C_5 (the pentagon).
The unique graph for a(4) = 11 is the Grötzsch graph.
There are 80 graphs for a(5) = 22, see Jensen & Royle reference and the Royle link.

F. Harary, Graph Theory, Addison-Wesley, Reading, Mass. (1969), p. 149.

V. Chvátal, The minimality of the Mycielski graph, Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973), Ed. by R. A. Bari and F. Harary, pp. 243-246. Lecture Notes in Mathematics 406, Springer, Berlin, 1974.
Jan Goedgebeur, On minimal triangle-free 6-chromatic graphs (2017)
House of Graphs, Triangle-free k-chromatic graphs
T. Jensen and G. F. Royle, Small graphs with chromatic number 5, A computer search, Journal of Graph Theory 19 (1995), pp. 107-116.
J. Mycielski, Sur le coloriage des graphes, Colloq. Math. 3 (1955), pp. 161-162.
Gordon Royle, Smallest triangle-free graph with chromatic number 5 (2018)

Cf. A006785, A024607.

For n > 3, the Mycielskian of a graph for a(n-1) shows that a(n) <= 2*a(n-1) + 1. This can be used to show that a(n) <= 3/4 * 2^n - 1 for n > 1.

cp's OEIS Frontend

A304125 Number of simple graphs with n vertices which contain no K5 subgraph.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

A005007 Number of cubic (i.e., regular of degree 3) generalized Moore graphs with 2n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Extensions

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A049367 Number of triangle-free planar graphs with n nodes.

Views

Author

Keywords

Links

Crossrefs

Extensions

A292528 Minimal number of vertices in a triangle-free graph with chromatic number n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula