A006856 -id:A006856 - cp's OEIS frontend

A054760 Table T(n,k) = order of (n,k)-cage (smallest n-regular graph of girth k), n >= 2, k >= 3, read by antidiagonals.

3, 4, 4, 5, 6, 5, 6, 8, 10, 6, 7, 10, 19, 14, 7, 8, 12, 30, 26, 24, 8, 9, 14, 40, 42, 67, 30, 9, 10, 16, 50, 62

Offset: 0

N. J. A. Sloane, Apr 26 2000

			First eight antidiagonals are:
   3  4  5  6  7  8  9 10
   4  6 10 14 24 30 58
   5  8 19 26 67 80
   6 10 30 42  ?
   7 12 40 62
   8 14 50
   9 16
  10

P. R. Christopher, Degree monotonicity of cages, Graph Theory Notes of New York, 38 (2000), 29-32.

Andries E. Brouwer, Cages
M. Daven and C. A. Rodger, (k,g)-cages are 3-connected, Discr. Math., 199 (1999), 207-215.
Geoff Exoo, Regular graphs of given degree and girth
G. Exoo and R. Jajcay, Dynamic cage survey, Electr. J. Combin. (2008, 2011).
Gordon Royle, Cubic Cages
Gordon Royle, Cages of higher valency
Pak Ken Wong, Cages-a survey, J. Graph Theory 6 (1982), no. 1, 1-22.

Moore lower bound: A198300.
Orders of cages: this sequence (n,k), A000066 (3,n), A037233 (4,n), A218553 (5,n), A218554 (6,n), A218555 (7,n),  A191595 (n,5).
Graphs not required to be regular: A006787, A006856.

T(k,g) >= A198300(k,g) with equality if and only if: k = 2 and g >= 3; g = 3 and k >= 2; g = 4 and k >= 2; g = 5 and k = 2, 3, 7 or possibly 57; or g = 6, 8, or 12, and there exists a symmetric generalized g/2-gon of order k - 1. - Jason Kimberley, Jan 01 2013

Edited by Jason Kimberley, Apr 25 2010, Oct 26 2011, Dec 21 2012, Jan 01 2013

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

Original entry on oeis.org

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

David Garnick, Apr 23 2009

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]

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.

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.

Cf. A006856.

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

cp's OEIS Frontend

A054760 Table T(n,k) = order of (n,k)-cage (smallest n-regular graph of girth k), n >= 2, k >= 3, read by antidiagonals.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Formula

Extensions