login
Denominators of Pokrovskiy's lower bound on the ratio of e(G^n) the number of edges in the n-th power of a graph G, to E(G) the number of edges of G.
1

%I #6 Mar 30 2012 18:40:59

%S 2,1,1,4,1,1,6,1,1,8,1,1,10,1,1,12

%N Denominators of Pokrovskiy's lower bound on the ratio of e(G^n) the number of edges in the n-th power of a graph G, to E(G) the number of edges of G.

%C Numerators are A208647. The fractions begin: 1/2, 1/2, 7/4, 2/1, 2/1, 17/6, 3/1, 3/1, 31/8, 4/1, 4/1, 49/10, 5/1, 5/1, 71/12.

%H Alexey Pokrovskiy, <a href="http://arxiv.org/abs/1202.6085">Edge growth in graph powers</a>, arXiv:1202.6085v1 [math.CO], Feb 27, 2012.

%F If n == 0 (mod 3) then e(G^n)/e(G) = ((n+3)/3) - 3/(2*(n+3));

%F If n =/= 0 (mod 3) then e(G^n)/e(G) = ceiling(n/3).

%Y Cf. A003417 (continued fraction for e), A208647.

%K nonn,easy,frac

%O 0,1

%A _Jonathan Vos Post_, Feb 29 2012