OFFSET
1,1
COMMENTS
k >= 2; g >= 3.
The base k-1 reading of the base 10 string of A094626(g).
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.
REFERENCES
E. Bannai and T. Ito, On finite Moore graphs, J. Fac. Sci. Tokyo, Sect. 1A, 20 (1973) 191-208.
R. M. Damerell, On Moore graphs, Proc. Cambridge Phil. Soc. 74 (1973) 227-236.
LINKS
Jason Kimberley, Table of n, a(n) for n = 1..20100 (k+g = 5..204)
Jason Kimberley, Table of n, k+g, k, g, M(k,g)=a(n) for k+g = 5..204 (n = 1..20100)
G. Exoo and R. Jajcay, Dynamic cage survey, Electr. J. Combin. (2008, 2011).
Gordon Royle, Cages of higher valency
FORMULA
M(k,2i) = 2 sum_{j=0}^{i-1}(k-1)^j = string "2"^i read in base k-1.
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.
Recurrence:
M(k,3) = k + 1,
M(k,2i) = M(k,2i-1) + (k-1)^(i-1),
M(k,2i+1) = M(k,2i) + (k-1)^i.
EXAMPLE
This is the table formed from the antidiagonals for k+g = 5..20:
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
4 6 10 14 22 30 46 62 94 126 190 254 382 510 766
5 8 17 26 53 80 161 242 485 728 1457 2186 4373 6560
6 10 26 42 106 170 426 682 1706 2730 6826 10922 27306
7 12 37 62 187 312 937 1562 4687 7812 23437 39062
8 14 50 86 302 518 1814 3110 10886 18662 65318
9 16 65 114 457 800 3201 5602 22409 39216
10 18 82 146 658 1170 5266 9362 42130
11 20 101 182 911 1640 8201 14762
12 22 122 222 1222 2222 12222
13 24 145 266 1597 2928
14 26 170 314 2042
15 28 197 366
16 30 226
17 32
18
MATHEMATICA
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 *)
PROG
(Magma)
ExtendedStringToInt:=func<seq, base|&+[Integers()|seq[i]*base^(#seq-i):i in[1..#seq]]>;
M:=func<k, g|ExtendedStringToInt((IsOdd(g)select[1]else[])cat[2^^(g div 2)], k-1)>;
k_:=2; g_:=3;
anti:=func<kg|[M(kg-g, g):g in[g_..kg-k_]]>;
[anti(kg):kg in[5..15]];
CROSSREFS
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).
Cf. A054760 (the actual order of a (k,g)-cage).
KEYWORD
AUTHOR
Jason Kimberley, Oct 27 2011
STATUS
approved