ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 25 Jun 2020 01:01:46 +0200How to obtain the graph having highest algebraic connectivity?https://ask.sagemath.org/question/52205/how-to-obtain-the-graph-having-highest-algebraic-connectivity/ 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?Wed, 24 Jun 2020 22:24:16 +0200https://ask.sagemath.org/question/52205/how-to-obtain-the-graph-having-highest-algebraic-connectivity/Answer by rburing for <p>for G in graphs.nauty_geng("10-c"):</p>
<p>if G.size()==11:</p>
<p>L = G.laplacian_matrix().eigenvalues()</p>
<p>L.sort()</p>
<p>show(L)</p>
<p>G.show()</p>
<p>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?</p>
https://ask.sagemath.org/question/52205/how-to-obtain-the-graph-having-highest-algebraic-connectivity/?answer=52206#post-id-52206It is [just like last year](https://ask.sagemath.org/question/45629/graphs-having-highest-second-smallest-laplacian-eigen-value-from-a-collection/):
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](/upfiles/159303087430667.png)
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](/upfiles/159303087430667.png)
![image description](/upfiles/15930309731772333.png)Wed, 24 Jun 2020 22:43:15 +0200https://ask.sagemath.org/question/52205/how-to-obtain-the-graph-having-highest-algebraic-connectivity/?answer=52206#post-id-52206Comment by rburing for <p>It is <a href="https://ask.sagemath.org/question/45629/graphs-having-highest-second-smallest-laplacian-eigen-value-from-a-collection/">just like last year</a>:</p>
<pre><code>algebraic_connectivity = lambda g: sorted(g.laplacian_matrix().eigenvalues())[1]
G = max(graphs.nauty_geng("10 11:11 -c"), key=algebraic_connectivity)
G
</code></pre>
<p><img alt="image description" src="/upfiles/159303087430667.png"></p>
<p>Here I also used <code>nauty</code> to restrict the number of edges to <code>11</code>, for efficiency.</p>
<p>Of course there could be more than one such graph. Indeed, using the code from the old answer, the output is:</p>
<pre><code>There are 2 graphs of (maximal) algebraic connectivity 1
</code></pre>
<p><img alt="image description" src="/upfiles/159303087430667.png">
<img alt="image description" src="/upfiles/15930309731772333.png"></p>
https://ask.sagemath.org/question/52205/how-to-obtain-the-graph-having-highest-algebraic-connectivity/?comment=52209#post-id-52209@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).Wed, 24 Jun 2020 23:05:35 +0200https://ask.sagemath.org/question/52205/how-to-obtain-the-graph-having-highest-algebraic-connectivity/?comment=52209#post-id-52209Comment by Kuldeep for <p>It is <a href="https://ask.sagemath.org/question/45629/graphs-having-highest-second-smallest-laplacian-eigen-value-from-a-collection/">just like last year</a>:</p>
<pre><code>algebraic_connectivity = lambda g: sorted(g.laplacian_matrix().eigenvalues())[1]
G = max(graphs.nauty_geng("10 11:11 -c"), key=algebraic_connectivity)
G
</code></pre>
<p><img alt="image description" src="/upfiles/159303087430667.png"></p>
<p>Here I also used <code>nauty</code> to restrict the number of edges to <code>11</code>, for efficiency.</p>
<p>Of course there could be more than one such graph. Indeed, using the code from the old answer, the output is:</p>
<pre><code>There are 2 graphs of (maximal) algebraic connectivity 1
</code></pre>
<p><img alt="image description" src="/upfiles/159303087430667.png">
<img alt="image description" src="/upfiles/15930309731772333.png"></p>
https://ask.sagemath.org/question/52205/how-to-obtain-the-graph-having-highest-algebraic-connectivity/?comment=52207#post-id-52207Ok. Thanks a lot for your answer.Wed, 24 Jun 2020 22:47:50 +0200https://ask.sagemath.org/question/52205/how-to-obtain-the-graph-having-highest-algebraic-connectivity/?comment=52207#post-id-52207Comment by Kuldeep for <p>It is <a href="https://ask.sagemath.org/question/45629/graphs-having-highest-second-smallest-laplacian-eigen-value-from-a-collection/">just like last year</a>:</p>
<pre><code>algebraic_connectivity = lambda g: sorted(g.laplacian_matrix().eigenvalues())[1]
G = max(graphs.nauty_geng("10 11:11 -c"), key=algebraic_connectivity)
G
</code></pre>
<p><img alt="image description" src="/upfiles/159303087430667.png"></p>
<p>Here I also used <code>nauty</code> to restrict the number of edges to <code>11</code>, for efficiency.</p>
<p>Of course there could be more than one such graph. Indeed, using the code from the old answer, the output is:</p>
<pre><code>There are 2 graphs of (maximal) algebraic connectivity 1
</code></pre>
<p><img alt="image description" src="/upfiles/159303087430667.png">
<img alt="image description" src="/upfiles/15930309731772333.png"></p>
https://ask.sagemath.org/question/52205/how-to-obtain-the-graph-having-highest-algebraic-connectivity/?comment=52208#post-id-52208If possible, would you please give the whole code here so that I can obtain the two graphs. Thank you.Wed, 24 Jun 2020 23:00:23 +0200https://ask.sagemath.org/question/52205/how-to-obtain-the-graph-having-highest-algebraic-connectivity/?comment=52208#post-id-52208Comment by Kuldeep for <p>It is <a href="https://ask.sagemath.org/question/45629/graphs-having-highest-second-smallest-laplacian-eigen-value-from-a-collection/">just like last year</a>:</p>
<pre><code>algebraic_connectivity = lambda g: sorted(g.laplacian_matrix().eigenvalues())[1]
G = max(graphs.nauty_geng("10 11:11 -c"), key=algebraic_connectivity)
G
</code></pre>
<p><img alt="image description" src="/upfiles/159303087430667.png"></p>
<p>Here I also used <code>nauty</code> to restrict the number of edges to <code>11</code>, for efficiency.</p>
<p>Of course there could be more than one such graph. Indeed, using the code from the old answer, the output is:</p>
<pre><code>There are 2 graphs of (maximal) algebraic connectivity 1
</code></pre>
<p><img alt="image description" src="/upfiles/159303087430667.png">
<img alt="image description" src="/upfiles/15930309731772333.png"></p>
https://ask.sagemath.org/question/52205/how-to-obtain-the-graph-having-highest-algebraic-connectivity/?comment=52210#post-id-52210ok. I Have got it now. Thank you so much.Wed, 24 Jun 2020 23:10:56 +0200https://ask.sagemath.org/question/52205/how-to-obtain-the-graph-having-highest-algebraic-connectivity/?comment=52210#post-id-52210Comment by Kuldeep for <p>It is <a href="https://ask.sagemath.org/question/45629/graphs-having-highest-second-smallest-laplacian-eigen-value-from-a-collection/">just like last year</a>:</p>
<pre><code>algebraic_connectivity = lambda g: sorted(g.laplacian_matrix().eigenvalues())[1]
G = max(graphs.nauty_geng("10 11:11 -c"), key=algebraic_connectivity)
G
</code></pre>
<p><img alt="image description" src="/upfiles/159303087430667.png"></p>
<p>Here I also used <code>nauty</code> to restrict the number of edges to <code>11</code>, for efficiency.</p>
<p>Of course there could be more than one such graph. Indeed, using the code from the old answer, the output is:</p>
<pre><code>There are 2 graphs of (maximal) algebraic connectivity 1
</code></pre>
<p><img alt="image description" src="/upfiles/159303087430667.png">
<img alt="image description" src="/upfiles/15930309731772333.png"></p>
https://ask.sagemath.org/question/52205/how-to-obtain-the-graph-having-highest-algebraic-connectivity/?comment=52211#post-id-52211Now, 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?Wed, 24 Jun 2020 23:21:59 +0200https://ask.sagemath.org/question/52205/how-to-obtain-the-graph-having-highest-algebraic-connectivity/?comment=52211#post-id-52211Comment by rburing for <p>It is <a href="https://ask.sagemath.org/question/45629/graphs-having-highest-second-smallest-laplacian-eigen-value-from-a-collection/">just like last year</a>:</p>
<pre><code>algebraic_connectivity = lambda g: sorted(g.laplacian_matrix().eigenvalues())[1]
G = max(graphs.nauty_geng("10 11:11 -c"), key=algebraic_connectivity)
G
</code></pre>
<p><img alt="image description" src="/upfiles/159303087430667.png"></p>
<p>Here I also used <code>nauty</code> to restrict the number of edges to <code>11</code>, for efficiency.</p>
<p>Of course there could be more than one such graph. Indeed, using the code from the old answer, the output is:</p>
<pre><code>There are 2 graphs of (maximal) algebraic connectivity 1
</code></pre>
<p><img alt="image description" src="/upfiles/159303087430667.png">
<img alt="image description" src="/upfiles/15930309731772333.png"></p>
https://ask.sagemath.org/question/52205/how-to-obtain-the-graph-having-highest-algebraic-connectivity/?comment=52212#post-id-52212@Kuldeep You're right, there was a mistake in the original code: sometimes the algebraic connectivity was `1` as an element of `QQbar`, and sometimes it was `1` as an element of `QQ`, and they were counted separately. Now I changed it (in the old answer) so that they are all in `QQbar` and it works.Thu, 25 Jun 2020 01:01:46 +0200https://ask.sagemath.org/question/52205/how-to-obtain-the-graph-having-highest-algebraic-connectivity/?comment=52212#post-id-52212