Ask Your Question

Graphs having highest second smallest laplacian eigen value from a collection

asked 2019-03-03 19:00:07 +0100

anonymous user


updated 2019-03-03 19:03:46 +0100

vdelecroix gravatar image

Using this code

for G in graphs(7):
    if G.girth()==4:
        L = G.laplacian_matrix().eigenvalues()

I have generated all graphs on $7$ vertices having girth=4. Now, from this code can we get the only unique graph having largest algebraic connectivity among all others.

edit retag flag offensive close merge delete


What is the definition of algebraic connectivity?

vdelecroix gravatar imagevdelecroix ( 2019-03-03 19:04:24 +0100 )edit

1 Answer

Sort by ยป oldest newest most voted

answered 2019-03-04 10:48:50 +0100

rburing gravatar image

updated 2020-06-25 00:57:48 +0100

For convenience we can define

algebraic_connectivity = lambda g: sorted(g.laplacian_matrix().eigenvalues())[1]

Then we can obtain at once

G = max((g for g in graphs(7) if g.girth() == 4), key=algebraic_connectivity)

But this assumes there is only one maximum. If we want to be more on the safe side:

my_graphs = [g for g in graphs(7) if g.girth() == 4]
from collections import defaultdict
acs = defaultdict(list)
for g in my_graphs:
    ac = QQbar(algebraic_connectivity(g)) # ensure keys are always in QQbar, even if rational
max_ac = max(acs.keys())
print('There are {} graphs of (maximal) algebraic connectivity {}'.format(len(acs[max_ac]), max_ac))
for g in acs[max_ac]:


There are 1 graphs of (maximal) algebraic connectivity 3

graph 2 with maximal a.c.

edit flag offensive delete link more


Ok. But suppose we use this code for all connected graphs on $8$ vertices and choose girth=$5$. Then this code is not giving the correct result

rewi gravatar imagerewi ( 2019-03-05 12:38:06 +0100 )edit

Why do you say it's not correct? When I run G = max((g for g in graphs(8) if g.is_connected() and g.girth() == 5), key=algebraic_connectivity) (or more efficiently G = max((g for g in graphs.nauty_geng('8 -c') if g.girth() == 5), key=algebraic_connectivity)) (or the longer code with analogous modification) then it seems correct.

rburing gravatar imagerburing ( 2019-03-05 13:58:54 +0100 )edit

@Kuldeep you're right, I got the definition of algebraic connectivity wrong because Wikipedia was not clear. I updated both Wikipedia and my answer.

rburing gravatar imagerburing ( 2019-03-06 08:45:34 +0100 )edit

No problem. But this time your answer is perfect. Very good. Thank you

rewi gravatar imagerewi ( 2019-03-06 18:43:24 +0100 )edit

You're welcome. You can vote and accept using the buttons to the left of the answer.

rburing gravatar imagerburing ( 2019-03-07 11:46:06 +0100 )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


Asked: 2019-03-03 19:00:07 +0100

Seen: 443 times

Last updated: Jun 25 '20