Graph structure having maximum algebraic connectivity among some given blocks

asked 2018-03-18 07:30:38 +0200

Anonymous

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

answered 2018-03-18 11:21:32 +0200

David Coudert
726 ●11 ●18 http://www-sop.inria.f...

You have two approaches to solve this exercise:

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.
Using a sheet of paper: read carefully the definition of 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.

edit flag offensive delete link

add a comment

Your Answer

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

Graph structure having maximum algebraic connectivity among some given blocks

1 Answer

Your Answer

Question Tools

Stats

Graph structure having maximum algebraic connectivity among some given blocks edit

1 Answer

Your Answer

Question Tools

Stats

Graph structure having maximum algebraic connectivity among some given blocks