cp's OEIS Frontend

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.

%I A375619 #13 Aug 29 2024 10:50:15
%S A375619 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 A375619 39,41,42,44,45,47,49,50,52,53,55,57,58,60,61,63,64,66,68,69,71,72,74,
%U A375619 76,77,79,80,82,83,85,87,88,90,91,93,95,96,98,99,101,102
%N 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.
%C A375619 In the parlance of extremal graph theory, a(n) is the extremal number ex(n, C_(0 mod 4)).
%H A375619 Luc Ta, <a href="/A375619/b375619.txt">Table of n, a(n) for n = 1..10000</a>
%H A375619 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 A375619 <a href="/index/Gra#graphs">Index entries for sequences related to graphs</a>
%F A375619 a(n) = floor(19/12(n-1)). See Győri et al. in Links.
%F A375619 a(n) = A172272(n-1) for all n <= 77; then a(78) = 121 != 122 = A172272(77).
%F A375619 a(n) = A056576(n-1) for all n <= 53; then a(54) = 83 != 84 = A056576(53).
%e A375619 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 A375619 Table[Floor[19/12 * (n - 1)], {n, 100}]
%Y A375619 Cf. A172272, A056576, A006855, A000066, A345248,  A006184.
%K A375619 nonn,easy
%O A375619 1,3
%A A375619 _Luc Ta_, Aug 21 2024