ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 18 Mar 2018 05:21:32 -0500Graph structure having maximum algebraic connectivity among some given blockshttp://ask.sagemath.org/question/41609/graph-structure-having-maximum-algebraic-connectivity-among-some-given-blocks/using this code we get a graph on 4 blocks of which 3 are pendant block(pendant in the sense that it has exactly one cut vertex).Now can we have some sage code that gives all connected graphs with these 4block of which exactly 3 blocks are pendant and also among those collection we need that graph having maximum algebraic conectivity
G=graphs.EmptyGraph()
G.add_edges([(1,2),(2,3),(1,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,5),(5,7),(8,6),(5,9),(9,10),(10,11),(11,12),
(12,9),(9,13),(13,14),(14,3)])
G.show()Sun, 18 Mar 2018 01:30:38 -0500http://ask.sagemath.org/question/41609/graph-structure-having-maximum-algebraic-connectivity-among-some-given-blocks/Answer by David Coudert for <p>using this code we get a graph on 4 blocks of which 3 are pendant block(pendant in the sense that it has exactly one cut vertex).Now can we have some sage code that gives all connected graphs with these 4block of which exactly 3 blocks are pendant and also among those collection we need that graph having maximum algebraic conectivity </p>
<p>G=graphs.EmptyGraph()</p>
<p>G.add_edges([(1,2),(2,3),(1,3),(3,4),(4,5),(5,6),(6,7),(7,8),(8,5),(5,7),(8,6),(5,9),(9,10),(10,11),(11,12),</p>
<p>(12,9),(9,13),(13,14),(14,3)])</p>
<p>G.show()</p>
http://ask.sagemath.org/question/41609/graph-structure-having-maximum-algebraic-connectivity-among-some-given-blocks/?answer=41612#post-id-41612You have two approaches to solve this exercise:
1. Using Sagemath: generate all blocks (=biconnected graphs) of order k=3..n using `graphs.nauty_geng("k -C")`, then for each combination of 4 of them build a block graph with the required structure, compute its algebraic connectivity and record the maximum value.
2. Using a sheet of paper: read carefully the definition of [algebraic connectivity](https://en.wikipedia.org/wiki/Algebraic_connectivity) to understand what maximizes this value (hint: check the lower bounds), deduce the biconnected graph with maximum algebraic connectivity, use it to build the block graph you need, and finally prove that this graph answers your question (short proof). You can afterward use Sagemath to compute its algebraic connectivity.
Sun, 18 Mar 2018 05:21:32 -0500http://ask.sagemath.org/question/41609/graph-structure-having-maximum-algebraic-connectivity-among-some-given-blocks/?answer=41612#post-id-41612