A058227 Number of edges in all simple (loopless) paths, connecting any node with all the remaining ones in optimal graphs of degree 4.

4, 28, 112, 352, 972, 2484, 6040, 14200

Offset

1,1

Comments

Number of edges occurring in all simple, loopless paths, connecting any node with all the remaining ones forming optimal graphs degree of 4, (2*d(G)^2+2*d(G)+1, 2*d(G)+1) with d(G) denoting graph diameter.

References

R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics, Addison-Wesley company, 1994.

Links

Table of n, a(n) for n=1..8.

Formula

a(n) = d(V)*Sum_{k=1..d(G)} k*(2^k-1) where d(V) is graph degree, and d(G) is graph diameter a(n)=d(V)*array(1..d(G))*array(1..(2^d(G)-1));

Conjectures from Sean A. Irvine, Jul 29 2022: (Start)

a(n) = 4 * Sum_{k=1..n} k*(2^k-1).

a(n) = (8*n-8)*2^n - 2*n^2 - 2*n + 8.

a(n) = a(n-1) + 4*n*(2^n-1) with a(0)=0.

(End)

Example

a(5)=4(1+2*3+3*7+4*15+5*31)=972 S := array(1..5,[1,2,3,4,5]); T := array(1..5,[1,3,7,15,31]); a(5) := evalm(S&*T); a(5) := 243

Maple

d(V) := 4; n := 5; a(n) := d(V)*sum('n*(2^n-1)', 'n'=1..n); or d(V) := 4; S := array(1..5, [1, 2, 3, 4, 5]); T := array(1..5, [1, 3, 7, 15, 31]); a(5) := d(V)*evalm(S&*T);

Crossrefs

Sequence in context: A202964 A352322 A183469 * A296392 A318011 A328685

Adjacent sequences: A058224 A058225 A058226 * A058228 A058229 A058230

Keyword

nonn,more

Author

S. Bujnowski (slawb(AT)atr.bydgoszcz.pl), Feb 13 2002

Status

approved