cp's OEIS Frontend

A198300 Square array M(k,g), read by antidiagonals, of the Moore lower bound on the order of a (k,g)-cage.

%I A198300 #49 Sep 08 2022 08:45:59
%S A198300 3,4,4,5,6,5,6,8,10,6,7,10,17,14,7,8,12,26,26,22,8,9,14,37,42,53,30,9,
%T A198300 10,16,50,62,106,80,46,10,11,18,65,86,187,170,161,62,11,12,20,82,114,
%U A198300 302,312,426,242,94,12,13,22,101,146,457,518,937,682,485,126,13
%N A198300 Square array M(k,g), read by antidiagonals, of the Moore lower bound on the order of a (k,g)-cage.
%C A198300 k >= 2; g >= 3.
%C A198300 The base k-1 reading of the base 10 string of A094626(g).
%C A198300 Exoo and Jajcay Theorem 1: M(k,g) <= A054760(k,g) with equality if and only if: k = 2 and g >= 3; g = 3 and k >= 2; g = 4 and k >= 2; g = 5 and k = 2, 3, 7 or possibly 57; or g = 6, 8, or 12, and there exists a symmetric generalized n-gon of order k - 1.
%D A198300 E. Bannai and T. Ito, On finite Moore graphs, J. Fac. Sci. Tokyo, Sect. 1A, 20 (1973) 191-208.
%D A198300 R. M. Damerell, On Moore graphs, Proc. Cambridge Phil. Soc. 74 (1973) 227-236.
%H A198300 Jason Kimberley, <a href="/A198300/b198300.txt">Table of n, a(n) for n = 1..20100 (k+g = 5..204)</a>
%H A198300 Jason Kimberley, <a href="/A198300/a198300.txt">Table of n, k+g, k, g, M(k,g)=a(n) for k+g = 5..204 (n = 1..20100)</a>
%H A198300 G. Exoo and R. Jajcay, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS16">Dynamic cage survey</a>, Electr. J. Combin. (2008, 2011).
%H A198300 Gordon Royle, <a href="http://staffhome.ecm.uwa.edu.au/~00013890/remote/cages/allcages.html">Cages of higher valency</a>
%F A198300 M(k,2i) = 2 sum_{j=0}^{i-1}(k-1)^j =  string "2"^i read in base k-1.
%F A198300 M(k,2i+1) = (k-1)^i +  2 sum_{j=0}^{i-1}(k-1)^j = string "1"*"2"^i read in base k-1.
%F A198300 Recurrence:
%F A198300 M(k,3) = k + 1,
%F A198300 M(k,2i) = M(k,2i-1) + (k-1)^(i-1),
%F A198300 M(k,2i+1) = M(k,2i) + (k-1)^i.
%e A198300 This is the table formed from the antidiagonals for k+g = 5..20:
%e A198300 3   4   5   6    7    8    9     10    11    12    13    14    15   16  17 18
%e A198300 4   6  10  14   22   30    46    62    94   126   190   254   382  510 766
%e A198300 5   8  17  26   53   80   161   242   485   728  1457  2186  4373 6560
%e A198300 6  10  26  42  106  170   426   682  1706  2730  6826 10922 27306
%e A198300 7  12  37  62  187  312   937  1562  4687  7812 23437 39062
%e A198300 8  14  50  86  302  518  1814  3110 10886 18662 65318
%e A198300 9  16  65 114  457  800  3201  5602 22409 39216
%e A198300 10 18  82 146  658 1170  5266  9362 42130
%e A198300 11 20 101 182  911 1640  8201 14762
%e A198300 12 22 122 222 1222 2222 12222
%e A198300 13 24 145 266 1597 2928
%e A198300 14 26 170 314 2042
%e A198300 15 28 197 366
%e A198300 16 30 226
%e A198300 17 32
%e A198300 18
%t A198300 Table[Function[g, FromDigits[#, k - 1] &@ IntegerDigits@ SeriesCoefficient[x (1 + x)/((1 - x) (1 - 10 x^2)), {x, 0, g}]][n - k + 3], {n, 2, 12}, {k, n, 2, -1}] // Flatten (* _Michael De Vlieger_, May 15 2017 *)
%o A198300 (Magma)
%o A198300 ExtendedStringToInt:=func<seq,base|&+[Integers()|seq[i]*base^(#seq-i):i in[1..#seq]]>;
%o A198300 M:=func<k,g|ExtendedStringToInt((IsOdd(g)select[1]else[])cat[2^^(g div 2)],k-1)>;
%o A198300 k_:=2;g_:=3;
%o A198300 anti:=func<kg|[M(kg-g,g):g in[g_..kg-k_]]>;
%o A198300 [anti(kg):kg in[5..15]];
%Y A198300 Moore lower bound on the order of a (k,g) cage: this sequence (square); rows: A000027 (k=2), A027383 (k=3), A062318 (k=4), A061547 (k=5), A198306 (k=6), A198307 (k=7), A198308 (k=8), A198309 (k=9), A198310 (k=10), A094626 (k=11); columns: A020725 (g=3), A005843 (g=4), A002522 (g=5), A051890 (g=6), A188377 (g=7), 2*A053698 (g=8), 2*A053699 (g=10), 2*A053700 (g=12), 2*A053716 (g=14), 2*A053716 (g=16), 2*A102909 (g=18), 2*A103623 (g=20), 2*A060885 (g=22), 2*A105067 (g=24), 2*A060887 (g=26), 2*A104376 (g=28), 2*A104682 (g=30), 2*A105312 (g=32).
%Y A198300 Cf. A054760 (the actual order of a (k,g)-cage).
%K A198300 nonn,tabl,easy,base
%O A198300 1,1
%A A198300 _Jason Kimberley_, Oct 27 2011