Ask Your Question

Graphs having highest second smallest laplacian eigen value from a collection

Anonymous

Using this code

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


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

Comments

What is the definition of algebraic connectivity?

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

1 Answer

Sort by ยป oldest newest most voted

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
acs[ac].append(g)
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]:
show(g)


Output:

There are 1 graphs of (maximal) algebraic connectivity 3


more

Comments

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

( 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.

( 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.

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

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

( 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.

( 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

Stats

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

Seen: 443 times

Last updated: Jun 25 '20