How to obtain the graph having highest algebraic connectivity?

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

rewi

99 ●18 ●31 ●39

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

if G.size()==11:

L = G.laplacian_matrix().eigenvalues()

L.sort()

show(L)

G.show()

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?

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

rburing

10929 ●4 ●80 ●218 https://www.rburing.nl/

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)
G

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

edit flag offensive delete link

Comments

Ok. Thanks a lot for your answer.

rewi ( 2020-06-24 22:47:50 +0100 )edit

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

rewi ( 2020-06-24 23:00:23 +0100 )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 ( 2020-06-24 23:05:35 +0100 )edit

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

rewi ( 2020-06-24 23:10:56 +0100 )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 ( 2020-06-24 23:21:59 +0100 )edit

see more comments

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

How to obtain the graph having highest algebraic connectivity?

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

How to obtain the graph having highest algebraic connectivity? edit

1 Answer

Comments

Your Answer

Question Tools

Stats

Related questions

How to obtain the graph having highest algebraic connectivity?