A208648 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.

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

Offset

0,1

Comments

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.

Links

Table of n, a(n) for n=0..15.

Alexey Pokrovskiy, Edge growth in graph powers, arXiv:1202.6085v1 [math.CO], Feb 27, 2012.

Formula

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

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

Crossrefs

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

Sequence in context: A061462 A294334 A122578 * A005131 A105477 A325772

Adjacent sequences: A208645 A208646 A208647 * A208649 A208650 A208651

Keyword

nonn,easy,frac

Author

Jonathan Vos Post, Feb 29 2012

Status

approved