# 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?

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

Perhaps this question is related to https://ask.sagemath.org/question/385...

( 2017-08-21 16:28:08 +0200 )edit

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

( 2017-08-31 17:59:50 +0200 )edit

( 2017-08-31 18:42:51 +0200 )edit

Sort by ยป oldest newest most voted

A compact version of the mentioned related question is:

def f( myList ):
return myList[1] * 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[1] * 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)

( 2017-08-22 02:26:17 +0200 )edit

( 2017-08-22 09:02:17 +0200 )edit

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

( 2017-08-23 03:14:37 +0200 )edit