| Presentation | 2016-09-15 A consideration on complete multipartite graphs that maximize the algebraic connectivity over all graphs with the same number of vertices and edges Ryoya Ishii, Norikazu Takahashi, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The second smallest eigenvalue of the Laplacian matrix of a graph, also known as the algebraic connectivity, is an important measure that represents how strongly the graph is connected. The algebraic connectivity also characterizes the performance of some dynamic processes on networks such as consensus of multiagent networks and synchronization of coupled oscillators. For example, it is well known that the larger the algebraic connectivity of the multiagent network is, the faster the convergence of a representative consensus algorithm. In this report, we consider graphs that maximize the algebraic connectivity over all graphs with the same number of vertices and edges. We first find such graphs with a small number of vertices by using an exhaustive search based on a graph enumeration algorithm. We next focus our attention on the complete multipartite regular graphs, and prove that they maximize the algebraic connectivity over all graphs with the same number of vertices and edges. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | multiagent network / algebraic connectivity / complete multipartite graph |
| Paper # | NLP2016-54 |
| Date of Issue | 2016-09-07 (NLP) |
| Conference Information | |
| Committee | NLP |
|---|---|
| Conference Date | 2016/9/14(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Konan Univ. |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Hisato Fujisaka(Hiroshima City Univ.) |
| Vice Chair | Masaharu Adachi(Tokyo Denki Univ.) |
| Secretary | Masaharu Adachi(Konan Univ.) |
| Assistant | Hiroyuki Asahara(Okayama Univ. of Science) / Toshihiro Tachibana(Shonan Inst. of Tech.) |
| Paper Information | |
| Registration To | Technical Committee on Nonlinear Problems |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A consideration on complete multipartite graphs that maximize the algebraic connectivity over all graphs with the same number of vertices and edges |
| Sub Title (in English) | |
| Keyword(1) | multiagent network |
| Keyword(2) | algebraic connectivity |
| Keyword(3) | complete multipartite graph |
| 1st Author's Name | Ryoya Ishii |
| 1st Author's Affiliation | Okayama University(Okayama Univ.) |
| 2nd Author's Name | Norikazu Takahashi |
| 2nd Author's Affiliation | Okayama University(Okayama Univ.) |
| Date | 2016-09-15 |
| Paper # | NLP2016-54 |
| Volume (vol) | vol.116 |
| Number (no) | NLP-215 |
| Page | pp.pp.51-56(NLP), |
| #Pages | 6 |
| Date of Issue | 2016-09-07 (NLP) |