# how to find the number of trees on 18 vertices that have diameter=5 and product of 2nd smallest laplacian eigenvalue(algebraic connectivity)and largest laplacian eigenvalue is equal to 1. If we increase the number of vertices say above 18 why it gives no result? Anonymous

how to find the number of trees on 18 vertices that have diameter=5 and product of 2nd smallest laplacian eigenvalue(algebraic connectivity)and largest laplacian eigenvalue is equal to 1.

edit retag close merge delete

Do you know the difference between a title and a question? That would help the readers a lot!

Sort by » oldest newest most voted

A compact version of the mentioned related question is:

def f( myList ):
return myList * myList[-1]

len( [ T
for T in graphs.trees( 18 )
if  T.diameter() == 5
and f( sorted( T.laplacian_matrix().eigenvalues() ) ) == 1 ] )


Enjoy!

more

Let us do the job for some other values, not only $18$.

def f( myList ):
return myList * myList[-1]

def myTrees( nVertices, diameter ):
return [
T
for T in graphs.trees( nVertices )
if  T.diameter() == diameter
and f( sorted( T.laplacian_matrix().eigenvalues() ) ) == 1 ]

dic = dict( [ ( nv, myTrees( nv, 5 ) ) for nv in [ 6..20 ] ] )
for nv in [6..20]:
print "%2s -> %s tree(s)" % ( nv, len( dic[nv] ) )


It gives:

 6 -> 1 tree(s)
7 -> 0 tree(s)
8 -> 0 tree(s)
9 -> 0 tree(s)
10 -> 1 tree(s)
11 -> 0 tree(s)
12 -> 1 tree(s)
13 -> 1 tree(s)
14 -> 1 tree(s)
15 -> 0 tree(s)
16 -> 1 tree(s)
17 -> 1 tree(s)
18 -> 3 tree(s)
19 -> 2 tree(s)


It seems that the question has changed last days. Note that one can also go further (after waiting a while). After a fresh sage start, using the above functions, i computed:

sage: tList = myTrees( 20, 5 )
sage: len( tList )
2
sage: t1, t2 = tList


So there are two relevant trees with $20$ vertices. Using t1.show() we see t1 as a tree of the shape

\    /
\  /
--0-1-2
/  \
/    \


where we further join in 1 and in 2 some particular trees of diameter one. Alg. connectivity ac and the spectral radius radius are:

sage: [sorted( t1.laplacian_matrix().eigenvalues() )[k] for k in [1,-1]]
[0.1270166537925831?, 7.872983346207417?]
sage: ac.minpoly()
x^2 - 8*x + 1
x^2 - 8*x + 1