login
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.
1

%I #13 Aug 29 2024 10:50:15

%S 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,

%T 39,41,42,44,45,47,49,50,52,53,55,57,58,60,61,63,64,66,68,69,71,72,74,

%U 76,77,79,80,82,83,85,87,88,90,91,93,95,96,98,99,101,102

%N 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.

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

%H Luc Ta, <a href="/A375619/b375619.txt">Table of n, a(n) for n = 1..10000</a>

%H Ervin Győri, Binlong Li, Nika Salia, Casey Tompkins, Kitti Varga, and Manran Zhu, <a href="http://arxiv.org/abs/2312.09999">On graphs without cycles of length 0 modulo 4</a>, arXiv: 2312.09999 [math.CO], 2023.

%H <a href="/index/Gra#graphs">Index entries for sequences related to graphs</a>

%F a(n) = floor(19/12(n-1)). See Győri et al. in Links.

%F a(n) = A172272(n-1) for all n <= 77; then a(78) = 121 != 122 = A172272(77).

%F a(n) = A056576(n-1) for all n <= 53; then a(54) = 83 != 84 = A056576(53).

%e 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.

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

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

%K nonn,easy

%O 1,3

%A _Luc Ta_, Aug 21 2024