Revision history [back]

This answer uses also networks, else there is an overlap with the answer of fidbc .

First of all let us restate the question in a mathematical setting, fixing thus the key words for programming in sage.

Let $T$ be a tree with $n$ verices. Let $L=L(T)$ be the laplacian matrix of $T$. The laplace spectrum of $T$ is the spectrum of $L$, $$\mu_1\ge \mu_2\ge \dots\ge \mu_{n-1}\ge\mu_n=0\ .$$ (Here, $0$ is always an eigenvalue with eigenvector $(1,1,\dots,1)$, since $T$ is connected. Its multiplicity is one.)

The second smallest value $\mu_{n-1}=a(T)$ is the

algebraic connectivity

of $T$. The biggest eigenvalue $\mu_1$ is the laplace spectral radius of $T$. Aka the norm of $L$.

The posted questions wants among all trees $T$ with $n=18$ vertices and diameter $d=5$ those $T$ with $$\mu_1\mu_{n-1} = 1\ .$$ Then for each such tree $T$ also the Fiedler vector (see loc. cit.), i.e. the $L$--eigenvector corresponding to the algebraic connectivity $a(T)=\mu_{n-1}$.

There are $2015$ relevant trees with $n=18$ vertices and diameter $5$ .

sage: T18_5 = [ T for T in graphs.trees(18) if T.diameter() == 5 ]
sage: len( T18_5 )
2015

We select the needed subset:

T_LIST = []
# count = 0
for T in T18_5:
    spec = T.laplacian_matrix().eigenvalues()
    spec . sort()
    # count += 1
    # if count%100 == 0:    print count 
    if spec[1] * spec[-1] == 1:
        T_LIST.append( T )

Using networks we can now ask for...

from networkx import algebraic_connectivity as a
from networkx import fiedler_vector         as fiedler

for T in T_LIST:
    Tx = T.networkx_graph()
    print "a(T) = %s\nFiedler vector:\n%s\n" % ( a(Tx), fiedler(Tx) )

and get:

a(T) = 0.127016653793
Fiedler vector:
[-0.12469138  0.12469138  0.28566726  0.32723106  0.32723105  0.32723106
  0.14283363  0.14283363  0.14283363  0.14283363 -0.28566726 -0.32723107
 -0.32723105 -0.32723104 -0.14283363 -0.14283362 -0.14283364 -0.14283364]

a(T) = 0.14589803375
Fiedler vector:
[-0.15316861  0.15316861  0.22416617  0.26245832  0.22416619  0.26245836
  0.22416616  0.26245831  0.22416616  0.26245831 -0.22416618 -0.26245834
 -0.22416617 -0.26245833 -0.22416615 -0.26245829 -0.22416618 -0.26245834]

a(T) = 0.133108958618
Fiedler vector:
[-0.06494166  0.19176279  0.2688225   0.31009952  0.2688225   0.31009952
  0.2688225   0.31009952 -0.25699018 -0.29645038 -0.29645038 -0.29645038
 -0.29645038 -0.09103845 -0.1050172  -0.07491327 -0.07491327 -0.07491327]

This is all.

Note: Outside networkx we can also get valuable information, for instance ask for the minimal polynomial of the algebraic_connectivity:

E = matrix.identity(18)
for T in T_LIST:
    L =  T.laplacian_matrix()
    spec = L.eigenvalues()
    spec . sort()

    print "  a(T)   = %s with minpoly = %s" % ( spec[ 1], spec[ 1].minpoly() )
    print "| L(T) | = %s with minpoly = %s" % ( spec[-1], spec[-1].minpoly() )
    print "Fiedler vector:\n%s\n\n" % column_matrix(( L - spec[1]*E ).kernel().basis()[0])
    # printed version of ( L - spec[1]*E ).kernel()

This gives:

  a(T)   = 0.1270166537925831? with minpoly = x^2 - 8*x + 1
| L(T) | = 7.872983346207417? with minpoly = x^2 - 8*x + 1
Fiedler vector:
[                  1]
[                 -1]
[-2.290994448735806?]
[-2.624327782069139?]
[-2.624327782069139?]
[-2.624327782069139?]
[-1.145497224367903?]
[-1.145497224367903?]
[-1.145497224367903?]
[-1.145497224367903?]
[ 2.290994448735806?]
[ 2.624327782069139?]
[ 2.624327782069139?]
[ 2.624327782069139?]
[ 1.145497224367903?]
[ 1.145497224367903?]
[ 1.145497224367903?]
[ 1.145497224367903?]


  a(T)   = 0.1458980337503155? with minpoly = x^2 - 7*x + 1
| L(T) | = 6.854101966249684? with minpoly = x^2 - 7*x + 1
Fiedler vector:
[                  1]
[                 -1]
[-1.463525491562421?]
[-1.713525491562421?]
[-1.463525491562421?]
[-1.713525491562421?]
[-1.463525491562421?]
[-1.713525491562421?]
[-1.463525491562421?]
[-1.713525491562421?]
[ 1.463525491562421?]
[ 1.713525491562421?]
[ 1.463525491562421?]
[ 1.713525491562421?]
[ 1.463525491562421?]
[ 1.713525491562421?]
[ 1.463525491562421?]
[ 1.713525491562421?]


  a(T)   = 0.1331089586175058? with minpoly = x^4 - 10*x^3 + 20*x^2 - 10*x + 1
| L(T) | = 7.512642352447085? with minpoly = x^4 - 10*x^3 + 20*x^2 - 10*x + 1
Fiedler vector:
[                  1]
[-2.952846325924191?]
[-4.139445001431823?]
[-4.775046463544424?]
[-4.139445001431823?]
[-4.775046463544424?]
[-4.139445001431823?]
[-4.775046463544424?]
[ 3.957245732488123?]
[ 4.564870950998888?]
[ 4.564870950998888?]
[ 4.564870950998888?]
[ 4.564870950998888?]
[ 1.401849112529162?]
[ 1.617099549550692?]
[ 1.153547507429801?]
[ 1.153547507429801?]
[ 1.153547507429801?]

In particular, we can identify the algebraic connectivity values as the algebraic numbers: $$ 4-\sqrt{15}\ ,\qquad \frac 12(7-3\sqrt{5})\ ,\qquad \frac 12\left( 5+\sqrt7-\sqrt{28+10\sqrt7} \right)\ .$$ The laplacian spectral radius (also nom) is obtained by replacing the minus with a plus each time.

This answer uses also networksnetworkx, else there is an overlap with the answer of fidbc .