Ask Your Question

Graph structure having maximum algebraic connectivity among some given blocks

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

anonymous user


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




edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted

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

You 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 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 more

Your Answer

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

Add Answer

Question Tools

1 follower


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

Seen: 248 times

Last updated: Mar 18 '18