login
A109094
Length of the longest path (repeated edges not allowed) between two arbitrary, distinct nodes in K_n, the complete graph on n vertices.
1
0, 1, 2, 5, 9, 13, 20, 25, 35, 41, 54, 61, 77, 85, 104, 113, 135, 145, 170, 181, 209, 221, 252, 265, 299, 313, 350, 365, 405, 421, 464, 481, 527, 545, 594, 613, 665, 685, 740, 761, 819, 841, 902, 925, 989, 1013, 1080, 1105, 1175, 1201, 1274, 1301, 1377, 1405
OFFSET
1,3
LINKS
Eric Weisstein's World of Mathematics, Complete Graph.
Eric Weisstein's World of Mathematics, Euler Path.
FORMULA
a(1)=0; a(2n+1) = n*(n-1)/2-1 = A014107(n+1), n>0; a(2n)=n*(n-2)/2+1= A001844(n-1). - Martin Fuller, R. J. Mathar and Mitch Harris, Dec 06 2007
O.g.f.: x^2*(x^4-2*x^3-x^2-x-1)/((-1+x)^3 *(x+1)^2) . - R. J. Mathar, Jan 17 2008
EXAMPLE
a(4) = 5 because the length of the longest path between any two distinct vertices in K_4 is 5.
CROSSREFS
Sequence in context: A281171 A190713 A288347 * A325647 A367403 A049753
KEYWORD
nonn,easy
AUTHOR
Ryan Propper, Jun 18 2005
STATUS
approved