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, 04 Apr 2019 13:47:02 +0200Bicyclic Graphs having highest second smallest laplacian eigen value from a collectionhttps://ask.sagemath.org/question/45953/bicyclic-graphs-having-highest-second-smallest-laplacian-eigen-value-from-a-collection/for G in graphs(8):
L = G.laplacian_matrix().eigenvalues()
L.sort()
show(L)
G.show()
Using this code I have been able to generate all graphs on 8 vertices. Now I need the connected graph with exactly two cycle (https://en.wikipedia.org/wiki/Cycle_(graph_theory)) whose algebraic connectivity (https://en.wikipedia.org/wiki/Algebraic_connectivity) is smallest among all connected graphs on 8 vertices which contains exactly two cycle. How we can solve this problem.Sat, 30 Mar 2019 19:29:23 +0100https://ask.sagemath.org/question/45953/bicyclic-graphs-having-highest-second-smallest-laplacian-eigen-value-from-a-collection/Answer by dan_fulea for <p>for G in graphs(8):</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 been able to generate all graphs on 8 vertices. Now I need the connected graph with exactly two cycle (<a href="https://en.wikipedia.org/wiki/Cycle_(graph_theory)">https://en.wikipedia.org/wiki/Cycle_(...</a>) whose algebraic connectivity (<a href="https://en.wikipedia.org/wiki/Algebraic_connectivity">https://en.wikipedia.org/wiki/Algebra...</a>) is smallest among all connected graphs on 8 vertices which contains exactly two cycle. How we can solve this problem.</p>
https://ask.sagemath.org/question/45953/bicyclic-graphs-having-highest-second-smallest-laplacian-eigen-value-from-a-collection/?answer=45976#post-id-45976The following code loops over the `graphs(8)` generator, eliminates the graphs that are not connected, then those that have a cycle basis with either more or less than two cycles (hope this corresponds to what is wanted, **please chech this point**), then puts in a list the (tuple assembling the) algebraic connectivity together with the full graph. This redundant information is then sorted, sorting is done w.r.t. the first entry of the tuple, this is the algebraic connectivity. At the end, i am printing the first five hits after sorting.
import networkx
count = 0
g_data_list = []
format_string = 'Graph # {} with algebraic connectivity = {}\n{!r}\n'
for g in graphs(8):
if not g.is_connected():
continue
g_cycle_basis = g.cycle_basis()
if len(g_cycle_basis) != 2:
continue
# ok, here we are in business
count += 1
ng = networkx.Graph(g.to_dictionary())
ag = networkx.algebraic_connectivity(ng)
# print(format_string.format(count, ag, g.adjacency_matrix()))
g_data_list.append((ag, g))
g_data_list.sort()
# show the first three entries in the list
count = 0
for ag, g in g_data_list[:5]:
count += 1
print(format_string.format(count, ag, g.adjacency_matrix()))
Results:
Graph # 1 with algebraic connectivity = 0.186393497352
[0 0 0 1 0 0 1 0]
[0 0 0 0 1 0 1 0]
[0 0 0 0 0 1 0 1]
[1 0 0 0 0 0 1 0]
[0 1 0 0 0 0 0 1]
[0 0 1 0 0 0 0 1]
[1 1 0 1 0 0 0 0]
[0 0 1 0 1 1 0 0]
Graph # 2 with algebraic connectivity = 0.193041644941
[0 0 0 1 0 1 0 1]
[0 0 0 0 1 0 1 0]
[0 0 0 0 0 0 1 1]
[1 0 0 0 0 1 0 1]
[0 1 0 0 0 0 0 0]
[1 0 0 1 0 0 0 0]
[0 1 1 0 0 0 0 0]
[1 0 1 1 0 0 0 0]
Graph # 3 with algebraic connectivity = 0.202256672304
[0 0 0 0 1 1 0 0]
[0 0 0 0 0 1 0 1]
[0 0 0 0 0 0 1 1]
[0 0 0 0 0 0 1 1]
[1 0 0 0 0 0 0 0]
[1 1 0 0 0 0 0 0]
[0 0 1 1 0 0 0 1]
[0 1 1 1 0 0 1 0]
Graph # 4 with algebraic connectivity = 0.218346547469
[0 0 0 0 1 0 1 0]
[0 0 0 0 0 1 1 0]
[0 0 0 0 0 1 0 1]
[0 0 0 0 0 0 0 1]
[1 0 0 0 0 0 1 0]
[0 1 1 0 0 0 0 1]
[1 1 0 0 1 0 0 0]
[0 0 1 1 0 1 0 0]
Graph # 5 with algebraic connectivity = 0.224287144264
[0 0 0 0 1 0 0 1]
[0 0 0 0 0 1 1 0]
[0 0 0 0 0 1 1 0]
[0 0 0 0 0 0 1 1]
[1 0 0 0 0 0 0 1]
[0 1 1 0 0 0 0 0]
[0 1 1 1 0 0 0 0]
[1 0 0 1 1 0 0 0]
And the winner is:
sage: g_data_list[0][1].show()
Launched png viewer for Graphics object consisting of 18 graphics primitives
![Connected graph with $8$ vertices and minimal algebraic connectivity](/upfiles/15541231232410244.png)
Mon, 01 Apr 2019 14:54:19 +0200https://ask.sagemath.org/question/45953/bicyclic-graphs-having-highest-second-smallest-laplacian-eigen-value-from-a-collection/?answer=45976#post-id-45976Answer by David Coudert for <p>for G in graphs(8):</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 been able to generate all graphs on 8 vertices. Now I need the connected graph with exactly two cycle (<a href="https://en.wikipedia.org/wiki/Cycle_(graph_theory)">https://en.wikipedia.org/wiki/Cycle_(...</a>) whose algebraic connectivity (<a href="https://en.wikipedia.org/wiki/Algebraic_connectivity">https://en.wikipedia.org/wiki/Algebra...</a>) is smallest among all connected graphs on 8 vertices which contains exactly two cycle. How we can solve this problem.</p>
https://ask.sagemath.org/question/45953/bicyclic-graphs-having-highest-second-smallest-laplacian-eigen-value-from-a-collection/?answer=45996#post-id-45996instead of `graph(8)`, use `graphs.nauty_geng("8 -c")` to get only connected graphs.Wed, 03 Apr 2019 09:37:52 +0200https://ask.sagemath.org/question/45953/bicyclic-graphs-having-highest-second-smallest-laplacian-eigen-value-from-a-collection/?answer=45996#post-id-45996Comment by rewi for <p>instead of <code>graph(8)</code>, use <code>graphs.nauty_geng("8 -c")</code> to get only connected graphs.</p>
https://ask.sagemath.org/question/45953/bicyclic-graphs-having-highest-second-smallest-laplacian-eigen-value-from-a-collection/?comment=46013#post-id-46013Thank you for your answer. It is very good. Now if I want the highest algebraic connectivity among all connected graphs on 8 vertices which contains exactly two cycle with at least one cycle of length greater than equal to 4. How we can solve this problem.Thu, 04 Apr 2019 13:47:02 +0200https://ask.sagemath.org/question/45953/bicyclic-graphs-having-highest-second-smallest-laplacian-eigen-value-from-a-collection/?comment=46013#post-id-46013