Graph having largest algebraic connectivity among some given blocks

asked 2018-02-09 13:32:34 +0200

anonymous user

Anonymous

updated 2018-02-09 17:36:44 +0200

tmonteil gravatar image

Suppose we are given some blocks(in sense of graph theory). Now suppose we have to find out that graph(connected) which has maximum algebraic connectivity and consists of those given blocks. the blocks may be path graph,cycle etc.please explain with a sage code.

edit retag flag offensive close merge delete

Comments

The question / the request is unclear for me. First of all do we have as input a Block graph $G$? ("Some blocks" is not really clarifying the input.)

Then the request is to find

  • among all connected subgraphs $H$ of $G$ which "consist of (some of the) given blocks" (does this mean "for every block $B$ of $G$ if $H$ contains an edge of $B$, then it contains the whole $B$ as a subgraph?!)
  • the subgraph(s) $H$ which maximize the algebraic connectivity?!

If yes, please provide some code that initializes an "interesting situation", best, the expected maximizing subgraph should be plese also predicted. References to existing algorithms are welcome. This would be a fair share of the effort, and potential helpers can easily start.

dan_fulea gravatar imagedan_fulea ( 2018-02-09 19:28:34 +0200 )edit
add a comment