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.
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
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
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.
No problem. But this time your answer is perfect. Very good. Thank you
You're welcome. You can vote and accept using the buttons to the left of the answer.
Asked: 6 years ago
Seen: 588 times
Last updated: Jun 25 '20
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
What is the definition of algebraic connectivity?