A000066 -id:A000066 - cp's OEIS frontend

A218554 Order of (6,n) cage, i.e., minimal order of 6-regular graph of girth n.

7, 12, 40, 62

Offset: 3

Arkadiusz Wesolowski, Nov 02 2012

a(7) <= 294, a(8) = 312, a(12) = 7812. - From Royle's page via Jason Kimberley, Dec 26 2012

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).
Gordon Royle, Cages of higher valency
Eric Weisstein's World of Mathematics, Cage Graph (claims too much)

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

a(n) >= A198306(n).

a(7) deleted by Jason Kimberley, Dec 21 2012

A218555 Order of (7,n) cage, i.e., minimal order of 7-regular graph of girth n.

Original entry on oeis.org

8, 14, 50, 90

Offset: 3

Arkadiusz Wesolowski, Nov 02 2012

a(8) <= 658, a(12) <= 32928. - Jason Kimberley, Dec 29 2012

Andries E. Brouwer, Cages
G. Exoo, Regular graphs of given degree and girth
G. Exoo and R. Jajcay, Dynamic cage survey, Electr. J. Combin. (2008, 2011).
Gordon Royle, Cages of higher valency
Eric Weisstein's World of Mathematics, Cage Graph (claims too much)

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

a(n) >= A198307(n).

Edited by Jason Kimberley, Dec 21 2012

A185130 Irregular triangle E(n,g) counting not necessarily connected 3-regular simple graphs on 2n vertices with girth exactly g.

Original entry on oeis.org

1, 1, 1, 4, 2, 15, 5, 1, 71, 21, 2, 428, 103, 8, 1, 3406, 752, 48, 1, 34270, 7385, 450, 5, 418621, 91939, 5752, 32, 5937051, 1345933, 90555, 385, 94782437, 22170664, 1612917, 7573, 1, 1670327647, 401399440, 31297424, 181224, 3, 32090011476, 7887389438

Offset: 2

Jason Kimberley, Dec 26 2012

The first column is for girth exactly 3. The column for girth exactly g begins when 2n reaches A000066(g).

			1;
1, 1;
4, 2;
15, 5, 1;
71, 21, 2;
428, 103, 8, 1;
3406, 752, 48, 1;
34270, 7385, 450, 5;
418621, 91939, 5752, 32;
5937051, 1345933, 90555, 385;
94782437, 22170664, 1612917, 7573, 1;
1670327647, 401399440, 31297424, 181224, 3;
32090011476, 7887389438, 652159986, 4624481, 21;
666351752261, 166897766824, 14499787794, 122089999, 545, 1;
14859579573845, 3781593764772, 342646826428, 3328899592, 30368, 0;

Jason Kimberley, Index of sequences counting not necessarily connected k-regular simple graphs with girth exactly g

Initial columns of this triangle: A185133 (g=3), A185134 (g=4), A185135 (g=5), A185136 (g=6).

The n-th row is the sequence of differences of the n-th row of A185330:
E(n,g) = A185330(n,g) - A185330(n,g+1), once we have appended 0 to each row of A185330.
Hence the sum of the n-th row is A185330(n,3) = A005638(n).

A185330 Irregular triangle E(n,g) counting not necessarily connected 3-regular simple graphs on 2n vertices with girth at least g.

Original entry on oeis.org

1, 2, 1, 6, 2, 21, 6, 1, 94, 23, 2, 540, 112, 9, 1, 4207, 801, 49, 1, 42110, 7840, 455, 5, 516344, 97723, 5784, 32, 7373924, 1436873, 90940, 385, 118573592, 23791155, 1620491, 7574, 1, 2103205738, 432878091, 31478651, 181227, 3, 40634185402

Offset: 2

Jason Kimberley, Oct 18 2012

The first column is for girth at least 3. The row length is incremented to g-2 when 2n reaches A000066(g).

			1;
2, 1;
6, 2;
21, 6, 1;
94, 23, 2;
540, 112, 9, 1;
4207, 801, 49, 1;
42110, 7840, 455, 5;
516344, 97723, 5784, 32;
7373924, 1436873, 90940, 385;
118573592, 23791155, 1620491, 7574, 1;
2103205738, 432878091, 31478651, 181227, 3;
40634185402, 8544173926, 656784488, 4624502, 21;
847871397424, 181519645163, 14621878339, 122090545, 546, 1;
18987149095005, 4127569521160, 345975756388, 3328929960, 30368, 0;

Jason Kimberley, Table of i, a(i)=E(n,g) for i = 2..60 (n = 2..16)
Jason Kimberley, Index of sequences counting not necessarily connected k-regular simple graphs with girth at least g

Cf. A005638, A185334, A185304.

A210709 Number of trivalent connected simple graphs with 2n nodes and girth at least 9.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 18

Offset: 0

Jason Kimberley, Dec 20 2012

Jason Kimberley, Index of sequences counting connected k-regular simple graphs with girth at least g

Trivalent simple graphs with girth at least g: A185131 (triangle); chosen g: A002851 (g=3), A014371 (g=4), A014372 (g=5), A014374 (g=6), A014375 (g=7), A014376 (g=8), this sequence (g=9).

Trivalent simple graphs with girth exactly g: A198303 (triangle); chosen g: A006923 (g=3), A006924 (g=4), A006925 (g=5), A006926 (g=6), A006927 (g=7).

a(29) = a(A000066(9)/2) = A052453(9) = 18 is the number of (3,9) cages.

A375619 a(n) is the largest integer such that there exists a simple graph with n vertices, a(n) edges, and no cycles of length 0 mod 4.

Original entry on oeis.org

0, 1, 3, 4, 6, 7, 9, 11, 12, 14, 15, 17, 19, 20, 22, 23, 25, 26, 28, 30, 31, 33, 34, 36, 38, 39, 41, 42, 44, 45, 47, 49, 50, 52, 53, 55, 57, 58, 60, 61, 63, 64, 66, 68, 69, 71, 72, 74, 76, 77, 79, 80, 82, 83, 85, 87, 88, 90, 91, 93, 95, 96, 98, 99, 101, 102

Offset: 1

Luc Ta, Aug 21 2024

In the parlance of extremal graph theory, a(n) is the extremal number ex(n, C_(0 mod 4)).

			For n = 4, any simple graph with 4 vertices and 5 edges contains a cycle of length 4 == 0 (mod 4), so a(4) < 5. There are exactly two nonisomorphic graphs with 4 vertices and 4 edges. One of them has no cycles of any length other than 3, so a(4) = 4.

Luc Ta, Table of n, a(n) for n = 1..10000
Ervin Győri, Binlong Li, Nika Salia, Casey Tompkins, Kitti Varga, and Manran Zhu, On graphs without cycles of length 0 modulo 4, arXiv: 2312.09999 [math.CO], 2023.
Index entries for sequences related to graphs

Cf. A172272, A056576, A006855, A000066, A345248, A006184.

Mathematica
```
Table[Floor[19/12 * (n - 1)], {n, 100}]
```

a(n) = floor(19/12(n-1)). See Győri et al. in Links.
a(n) = A172272(n-1) for all n <= 77; then a(78) = 121 != 122 = A172272(77).
a(n) = A056576(n-1) for all n <= 53; then a(54) = 83 != 84 = A056576(53).

A266731 Smallest number of vertices in bi-regular ({3,4};n) graph with girth (shortest cycle) = n.

Original entry on oeis.org

7, 13, 18, 29, 39, 61, 82, 125

Offset: 4

N. J. A. Sloane, Jan 04 2016

Cf. A000066, A266730.

cp's OEIS Frontend

A218554 Order of (6,n) cage, i.e., minimal order of 6-regular graph of girth n.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A218555 Order of (7,n) cage, i.e., minimal order of 7-regular graph of girth n.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A185130 Irregular triangle E(n,g) counting not necessarily connected 3-regular simple graphs on 2n vertices with girth exactly g.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A185330 Irregular triangle E(n,g) counting not necessarily connected 3-regular simple graphs on 2n vertices with girth at least g.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A210709 Number of trivalent connected simple graphs with 2n nodes and girth at least 9.

Views

Author

Keywords

Links

Crossrefs

Formula

A375619 a(n) is the largest integer such that there exists a simple graph with n vertices, a(n) edges, and no cycles of length 0 mod 4.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A266731 Smallest number of vertices in bi-regular ({3,4};n) graph with girth (shortest cycle) = n.

Views

Author

Keywords

Crossrefs