Ask Your Question
0

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?

asked 2017-08-21 07:43:15 -0500

anonymous user

Anonymous

updated 2017-08-22 08:20:52 -0500

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 flag offensive close merge delete

Comments

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

fidbc gravatar imagefidbc ( 2017-08-21 09:28:08 -0500 )edit

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

vdelecroix gravatar imagevdelecroix ( 2017-08-31 10:59:50 -0500 )edit

Thanks for your suggestion.

A gravatar imageA ( 2017-08-31 11:42:51 -0500 )edit

1 answer

Sort by ยป oldest newest most voted
0

answered 2017-08-21 19:24:03 -0500

dan_fulea gravatar image

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!

edit flag offensive delete link more

Comments

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)
dan_fulea gravatar imagedan_fulea ( 2017-08-21 19:26:17 -0500 )edit

Thanks for your reply.Thank you

A gravatar imageA ( 2017-08-22 02:02:17 -0500 )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, radius = _
sage: ac.minpoly()
x^2 - 8*x + 1
sage: radius.minpoly()
x^2 - 8*x + 1
dan_fulea gravatar imagedan_fulea ( 2017-08-22 20:14:37 -0500 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2017-08-21 07:43:15 -0500

Seen: 69 times

Last updated: Aug 22