Ask Your Question

How to obtain the graph having highest algebraic connectivity?

asked 2020-06-24 22:24:16 +0200

rewi gravatar image

for G in graphs.nauty_geng("10-c"):

if G.size()==11:

L = G.laplacian_matrix().eigenvalues()



Using this code I have obtained the connected graphs on 10 vertices with 11 edges. Also I have obtained the Laplacian eigenvalues also for the corresponding graphs. The second smallest eigenvalue of Laplacian matrix is called the algebraic connectivity. Now among all these graphs, I need those graphs which have highest algebraic connectivity among all the graphs on 10 vertices with 11 edges. How we can do that?

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

answered 2020-06-24 22:43:15 +0200

rburing gravatar image

It is just like last year:

algebraic_connectivity = lambda g: sorted(g.laplacian_matrix().eigenvalues())[1]
G = max(graphs.nauty_geng("10 11:11 -c"), key=algebraic_connectivity)

image description

Here I also used nauty to restrict the number of edges to 11, for efficiency.

Of course there could be more than one such graph. Indeed, using the code from the old answer, the output is:

There are 2 graphs of (maximal) algebraic connectivity 1

image description image description

edit flag offensive delete link more


Ok. Thanks a lot for your answer.

rewi gravatar imagerewi ( 2020-06-24 22:47:50 +0200 )edit

If possible, would you please give the whole code here so that I can obtain the two graphs. Thank you.

rewi gravatar imagerewi ( 2020-06-24 23:00:23 +0200 )edit

@Kuldeep You're welcome. In the old code, just put my_graphs = graphs.nauty_geng("10 11:11 -c") at the top, and replace print ... by print(...) (we need parentheses in now, in Python 3).

rburing gravatar imagerburing ( 2020-06-24 23:05:35 +0200 )edit

ok. I Have got it now. Thank you so much.

rewi gravatar imagerewi ( 2020-06-24 23:10:56 +0200 )edit

Now, if we run the same coder for 8 vertices and 9 edges, we should get three graphs having algebraic connectivity=1. But I am getting only 2. Where is the fault. will you please help?

rewi gravatar imagerewi ( 2020-06-24 23:21:59 +0200 )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


Asked: 2020-06-24 22:24:16 +0200

Seen: 415 times

Last updated: Jun 24 '20