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.

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

Author

Luc Ta, Aug 21 2024

Keywords

• nonn
• easy

Comments

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

Examples

			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.
		

Links

• 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

Crossrefs

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

Programs

Mathematica

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

Formula

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