A006787 -id:A006787 - 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

A000066 Smallest number of vertices in trivalent graph with girth (shortest cycle) = n.

Original entry on oeis.org

4, 6, 10, 14, 24, 30, 58, 70, 112, 126

Offset: 3

N. J. A. Sloane

Also called the order of the (3,n) cage graph.
Recently (unpublished) McKay and Myrvold proved that the minimal graph on 112 vertices is unique. - May 20 2003
If there are n vertices and e edges, then 3n=2e, so n is always even.
Current lower bounds for a(13)..a(32) are 202, 258, 384, 512, 768, 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576, 32768, 49152, 65536, 98304, 131072. - from Table 3 of the Dynamic cage survey via Jason Kimberley, Dec 31 2012
Current upper bounds for a(13)..a(32) are 272, 384, 620, 960, 2176, 2560, 4324, 5376, 16028, 16206, 49326, 49608, 108906, 109200, 285852, 415104, 1141484, 1143408, 3649794, 3650304. - from Table 3 of the Dynamic cage survey via Jason Kimberley, Dec 31 2012

A. T. Balaban, Trivalent graphs of girth nine and eleven and relationships among cages, Rev. Roum. Math. Pures et Appl. 18 (1973) 1033-1043.
Brendan McKay, personal communication.
H. Sachs, On regular graphs with given girth, pp. 91-97 of M. Fiedler, editor, Theory of Graphs and Its Applications: Proceedings of the Symposium, Smolenice, Czechoslovakia, 1963. Academic Press, NY, 1964.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Gabriela Araujo-Pardo, Geoffrey Exoo, and Robert Jajcay, Small bi-regular graphs of even girth Discrete Mathematics 339.2 (2016): 658-667.
Andries E. Brouwer, Cages
Geoff Exoo, Regular graphs of given degree and girth
G. Exoo and R. Jajcay, Dynamic cage survey, Electr. J. Combin. (2008, 2011).
Brendan McKay, W. Myrvold and J. Nadon, Fast backtracking principles applied to find new cages, 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 1998, 188-191.
M. O'Keefe and P. K. Wong, A smallest graph of girth 10 and valency 3, J. Combin. Theory, B 29 (1980), 91-105.
Gordon Royle, Cubic Cages
Eric Weisstein's World of Mathematics, Cage Graph
Pak Ken Wong, Cages-a survey, J. Graph Theory 6 (1982), no. 1, 1-22.

Cf. A006787, A052453 (number of such graphs).

Orders of cages: A054760 (n,k), this sequence (3,n), A037233 (4,n), A218553 (5,n), A218554 (6,n), A218555 (7,n), A191595 (n,5).

For all g > 2, a(g) >= A027383(g-1), with equality if and only if g = 3, 4, 5, 6, 8, or 12. - Jason Kimberley, Dec 21 2012 and Jan 01 2013

Additional comments from Matthew Cook, May 15 2003

Balaban proved 112 as an upper bound for a(11). The proof that it is also a lower bound is in the paper by Brendan McKay, W. Myrvold and J. Nadon.

A128042 Triangle read by columns: number of n-node (unlabeled) connected graphs with girth k, for n >= 3, k >= 3.

Original entry on oeis.org

1, 3, 1, 15, 2, 1, 93, 11, 1, 1, 794, 41, 5, 1, 1, 10850, 220, 16, 6, 1, 1, 259700, 1243, 66, 17, 5, 1, 1, 11706739, 9368, 266, 69, 15, 6, 1, 1, 1006609723, 89049, 1235, 239, 58, 18, 6, 1, 1, 164058686415, 1135894, 6350, 962, 202, 74, 19, 7, 1, 1

Offset: 3

Keith Briggs, May 05 2007

			Number of n-node (unlabeled) connected graphs with girth k:
.k..|.n=........3........4........5........6........7........8........9........10
---------------------------------------------------------------------------------
.0..|...........0........0........0........0........0........0........0.........0
.1..|...........0........0........0........0........0........0........0.........0
.2..|...........0........0........0........0........0........0........0.........0
.3..|...........1........3.......15.......93......794....10850...259700..11706739
.4..|...........0........1........2.......11.......41......220.....1243......9368
.5..|...........0........0........1........1........5.......16.......66.......266
.6..|...........0........0........0........1........1........6.......17........69
.7..|...........0........0........0........0........1........1........5........15
.8..|...........0........0........0........0........0........1........1.........6
.9..|...........0........0........0........0........0........0........1.........1
10..|...........0........0........0........0........0........0........0.........1
11..|...........0........0........0........0........0........0........0.........0

Georg Grasegger, Table of n, a(n) for n = 3..122

Sequences for k=3..6 are A128240, A128241, A128242, A128243.
Cf. A128041, A006787, A128236, A128237, A128238, A128239.
Cf. A325455 (circumference).

geng -c $n | countg --ng
# Martin Fuller, May 03 2015

Corrected and extended by Martin Fuller, May 01 2015

A128041 Triangle read by columns: number of n-node (unlabeled) graphs with girth k, for n >= 3, k >= 3.

Original entry on oeis.org

1, 4, 1, 20, 3, 1, 118, 15, 2, 1, 937, 59, 8, 2, 1, 11936, 296, 26, 9, 2, 1, 272771, 1604, 101, 28, 8, 2, 1, 11992996, 11303, 396, 107, 25, 9, 2, 1, 1018892793, 102108, 1744, 376, 92, 29, 9, 2, 1, 165089910412, 1250114, 8531, 1457, 321, 113, 30, 10, 2, 1

Offset: 3

Keith Briggs, May 05 2007

			Number of n-node (unlabeled) graphs with girth k, for n >= 3, k >= 3.
.k..|.n=........3........4........5........6........7........8........9........10
---------------------------------------------------------------------------------
.0..|...........0........0........0........0........0........0........0.........0
.1..|...........0........0........0........0........0........0........0.........0
.2..|...........0........0........0........0........0........0........0.........0
.3..|...........1........4.......20......118......937....11936...272771..11992996
.4..|...........0........1........3.......15.......59......296.....1604.....11303
.5..|...........0........0........1........2........8.......26......101.......396
.6..|...........0........0........0........1........2........9.......28.......107
.7..|...........0........0........0........0........1........2........8........25
.8..|...........0........0........0........0........0........1........2.........9
.9..|...........0........0........0........0........0........0........1.........2
10..|...........0........0........0........0........0........0........0.........1

Cf. A128042, A006787, A128236-A128243.

geng $n | countg --ng # Martin Fuller, May 03 2015

Corrected and extended by Martin Fuller, May 01 2015

A128237 Number of n-node (unlabeled) graphs with girth 4.

Original entry on oeis.org

0, 1, 3, 15, 59, 296, 1604, 11303, 102108, 1250114, 20738069, 467523871, 14230096759, 581439661069, 31720637440030

Offset: 3

Keith Briggs, May 05 2007

nonn

Cf. A006785, A006787.

Cf. A128041, A128042, A128236-A128243.

a(n) = A006785(n) - A006787(n).

Corrected and extended by Martin Fuller, May 01 2015

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

Original entry on oeis.org

1, 1, 1, 2, 4, 8, 18, 47, 137, 464, 1793, 8167, 43645, 275480, 2045279, 17772647, 179593823, 2098423758, 28215583324, 434936005284, 7662164738118

Offset: 1

N. J. A. Sloane, Feb 18 2007

Keith M. Briggs, Combinatorial Graph Theory
CombOS - Combinatorial Object Server, Generate graphs

Cf. A006787, A140440.

A006787 = Cases[Import["https://oeis.org/A006787/b006787.txt", "Table"], {, }][[All, 2]];
(* EulerInvTransform is defined in A022562 *)
EulerInvTransform[A006787] (* Jean-François Alcover, May 13 2019, updated Mar 17 2020 *)

This is the inverse Euler transform of A006787. - Conjectured by Vladeta Jovovic, Jun 16 2008, proved by Max Alekseyev and Brendan McKay, Jun 17 2008

Definition corrected by Max Alekseyev and Brendan McKay, Jun 17 2008

a(20)-a(21) using Brendan McKay's extension to A006787 by Alois P. Heinz, Mar 11 2018

A300705 Triangle T(n,k) read by rows: the number of n-node connected graphs with k components with no cycles of length less than 5.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 2, 2, 1, 1, 0, 4, 3, 2, 1, 1, 0, 8, 7, 4, 2, 1, 1, 0, 18, 14, 8, 4, 2, 1, 1, 0, 47, 33, 17, 9, 4, 2, 1, 1, 0, 137, 81, 40, 18, 9, 4, 2, 1, 1, 0, 464, 228, 98, 43, 19, 9, 4, 2, 1, 1, 0, 1793, 716, 269, 105, 44, 19, 9, 4, 2, 1, 1, 0, 8167, 2596, 827, 287, 108, 45, 19, 9, 4, 2, 1, 1, 0

Offset: 0

R. J. Mathar, Mar 12 2018

Multiset transform of A126757.

			The triangle starts in row n=0 with columns 0<=k<=n as:
 1;
0 1
0 1 1
0 1 1 1
0 2 2 1 1
0 4 3 2 1 1
0 8 7 4 2 1 1
0 18 14 8 4 2 1 1
0 47 33 17 9 4 2 1 1
0 137 81 40 18 9 4 2 1 1
0 464 228 98 43 19 9 4 2 1 1
0 1793 716 269 105 44 19 9 4 2 1 1
0 8167 2596 827 287 108 45 19 9 4 2 1 1
0 43645 11030 2904 870 294 109 45 19 9 4 2 1 1
0 275480 55628 11992 3022 888 297 110 45 19 9 4 2 1 1
0 2045279 334676 58968 12320 3066 895 298 110 45 19 9 4 2 1 1
0 17772647 2395216 348166 59991 12440 3084 898 299 110 45 19 9 4 2 1 1

Cf. A126757 (column k=1), A006787 (row sums)

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

Original entry on oeis.org

1, 2, 7, 38, 303, 3424, 53365, 1121412, 31197241, 1131759944, 52851880791, 3141661092280, 235381934211847, 22034726000877312, 2557207299577993717, 365328083228276428304, 63837414801921587915025, 13564359864218330055841312, 3485934653871954826576733959

Offset: 1

Brendan McKay, Sep 15 2020

Equivalently, labeled graphs of girth at least 5. Disconnected graphs are included.

LOG transform of A345349.

A006787 counts isomorphism classes.

A345349 Number of connected labeled n-node graphs with no cycles of length less than 5.

Original entry on oeis.org

1, 1, 3, 16, 137, 1716, 29767, 689704, 20868129, 811683280, 40112905211, 2495678969664, 193978310951977, 18707104147471936, 2224427540682088575, 324218245786867111936, 57606132897772268960513, 12412563223145385150556416, 3227770981209698325415487539

Offset: 1

Brendan McKay, Jun 15 2021

Equivalently, connected labeled graphs of girth at least 5.

EXP transform of A337685.

A006787 counts isomorphism classes.

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

A000066 Smallest number of vertices in trivalent graph with girth (shortest cycle) = n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A128042 Triangle read by columns: number of n-node (unlabeled) connected graphs with girth k, for n >= 3, k >= 3.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

nauty

Extensions

A128041 Triangle read by columns: number of n-node (unlabeled) graphs with girth k, for n >= 3, k >= 3.

Views

Author

Keywords

Examples

Crossrefs

Programs

nauty

Extensions

A128237 Number of n-node (unlabeled) graphs with girth 4.

Views

Author

Keywords

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A300705 Triangle T(n,k) read by rows: the number of n-node connected graphs with k components with no cycles of length less than 5.

Views

Author

Keywords

Comments

Examples

Crossrefs

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

Views

Author

Keywords

Comments

Crossrefs

A345349 Number of connected labeled n-node graphs with no cycles of length less than 5.

Views

Author

Keywords

Comments

Crossrefs