A159847 The number of non-isomorphic n-node graphs with the maximal number of edges, and containing no three-cycles or four-cycles.

1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 3, 7, 1, 4, 1, 22, 14, 15, 1, 1, 3, 3, 7, 1, 6, 2, 1, 4, 1, 1, 2, 1

Offset: 1

Author

David Garnick, Apr 23 2009

Keywords

• nonn
• hard
• more

Comments

The Moore graphs are unique examples of these graphs for their orders. Thus the fiftieth term in this sequence is 1.

Two additional values of this sequence determined: a(24)=1 and a(32)=1. [Michael Codish, Apr 09 2013]

References

• D. K. Garnick and N. A. Nieuwejaar, Non-isomorphic Extremal Graphs without Three-Cycles or Four-Cycles, Journal of Combinatorial Mathematics and Combinatorial Computing, 12(1992), 33-56.

Links

• 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.
• Alice Miller and Michael Codish, Graphs with girth at least 5 with orders between 20 and 32, arXiv:1708.06576 [math.CO], 2017.

Crossrefs

Cf. A006856.

Extensions

a(22)-a(31) from Miller and Codish, David Garnick, Dec 24 2022