A159847 -id:A159847 - cp's OEIS frontend

A006787 Number of n-node graphs with no cycles of length less than 5.

1, 2, 3, 6, 11, 23, 48, 114, 293, 869, 2963, 12066, 58933, 347498, 2455693, 20592932, 202724920, 2322206466, 30743624324, 468026657815, 8161170076257

Offset: 1

N. J. A. Sloane

Includes graphs with no cycles at all as well as graphs with girth greater than 5.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

CombOS - Combinatorial Object Server, Generate graphs
Brendan McKay, Emails to N. J. A. Sloane, 1991
Brendan D. McKay, Isomorph-free exhaustive generation, Table 2.
Brendan D. McKay, Isomorph-Free Exhaustive Generation, J. Algorithms, vol. 26 iss. 2 (1998), 306-324.

Cf. A000066, A000088, A054760, A159847, A126757 (connected, inv. Eul. Transf.), A128236, A128237, A300705.

a(n) = A000088(n) - A128236(n) - A128237(n). - Andrew Howroyd, May 06 2021

Definition corrected by Brendan McKay, Apr 27 2007
a(18)-a(19) (from the McKay reference) added by R. J. Mathar, Jun 17 2008
a(20)-a(21) from Brendan McKay, Mar 11 2018

A006856 Maximal number of edges in n-node graph of girth at least 5.

Original entry on oeis.org

0, 1, 2, 3, 5, 6, 8, 10, 12, 15, 16, 18, 21, 23, 26, 28, 31, 34, 38, 41, 44, 47, 50, 54, 57, 61, 65, 68, 72, 76, 80, 85, 87, 90, 95, 99, 104, 109, 114, 120, 124, 129, 134, 139, 145, 150, 156, 162, 168, 175, 176, 178, 181

Offset: 1

N. J. A. Sloane

From Brendan McKay, Mar 09 2022: (Start)
The unique graph for a(50)=175 is the Hoffman-Singleton graph.
a(53) is at least 181. (End)
a(53) is exactly 181. a(54)-a(56) are at least 185,189,193. - Brendan McKay, Jan 07 2023

Brendan McKay, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

J. Backelin, Sizes of the extremal girth 5 graphs of orders from 40 to 49, arXiv preprint arXiv:1511.08128 [math.CO], 2015.
Michael Codish, Alice Miller, Patrick Prosser, and Peter J. Stuckey, Breaking Symmetries in Graph Representation, IJCAI 2013.
David K. Garnick, Y. H. Harris Kwong and Felix Lazebnik, Extremal Graphs without Three-Cycles or Four-Cycles, Journal of Graph Theory, 17 (1993), 633-645.
Brendan McKay, Extremal Graphs and Turan Numbers.
Alice Miller and Michael Codish, Graphs with girth at least 5 with orders between 20 and 32, arXiv:1708.06576 [math.CO], 2017.

Cf. A159847.

Two more terms from David Garnick (dgarnick(AT)gmail.com), Jan 09 2007
Two more terms from Michael Codish, Apr 07 2013
Definition clarified by Jörgen Backelin, Jun 18 2015
a(33)-a(52) from Brendan McKay, Mar 09 2022
a(53) from Brendan McKay, Jan 06 2023

cp's OEIS Frontend

A006787 Number of n-node graphs with no cycles of length less than 5.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions