A208647 Numerators 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, 1, 1, 7, 2, 2, 17, 3, 3, 31, 4, 4, 49, 5, 5, 71

Offset

0,4

Comments

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

Sequence in context: A334961 A154759 A300304 * A163981 A126341 A324788

Adjacent sequences: A208644 A208645 A208646 * A208648 A208649 A208650

Keyword

nonn,easy,frac

Author

Jonathan Vos Post, Feb 29 2012

Status

approved