A345248 -id:A345248 - cp's OEIS frontend

A345249 Number of labeled simple graphs on n vertices without cycles of length 4.

1, 2, 8, 54, 548, 7984, 163440, 4599908, 174204728, 8721120744, 568964631296, 47787888342520, 5112015062311008, 689824902243337856, 116423739687724785152, 24387469030487505651984, 6296486009090647137387200, 1991072810881504185092485408

Offset: 1

Brendan McKay, Jun 12 2021

Index entries for sequences of squarefree graphs

EXP transform of A345248. Row sums of A352472.
A006786 counts isomorphism classes.
Cf. A213434, A352258 (loops allowed).

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).

cp's OEIS Frontend

A345249 Number of labeled simple graphs on n vertices without cycles of length 4.

Views

Author

Keywords

Links

Crossrefs

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