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,3

Comments

In the parlance of extremal graph theory, a(n) is the extremal number ex(n, C_(0 mod 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

Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,0,0,0,0,0,0,0,1,-1).

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

G.f.: x^2*(1 + 2*x + x^2 + 2*x^3 + x^4 + 2*x^5 + 2*x^6 + x^7 + 2*x^8 + x^9 + 2*x^10 + 2*x^11)/((1 - x)^2*(1 + x)*(1 - x + x^2)*(1 + x^2)*(1 + x + x^2)*(1 - x^2 + x^4)). - Andrew Howroyd, Nov 13 2025

Example

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.

Mathematica

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

Prog

(PARI) a(n) = {19*(n-1)\12} \\ Andrew Howroyd, Nov 13 2025

Crossrefs

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

Sequence in context: A186539 A054385 A284773 * A172272 A056576 A182770

Adjacent sequences: A375616 A375617 A375618 * A375620 A375621 A375622

Keyword

nonn,easy

Author

Luc Ta, Aug 21 2024

Status

approved