 |
 |
|
|
| HAL : hal-00724093, version 1 |
| arXiv : 1208.3581 |
| Fiche détaillée |  Récupérer au format |
 |
|
|
| A note on Fiedler value of classes with sublinear separators |
|
|
Jaroslav Nesetril 1Patrice Ossona De Mendez 2 |
|
|
| (17/08/2012) |
|
|
|
| The $n$-th Fiedler value of a class of graphs $\mathcal C$ is the maximum second eigenvalue $\lambda_2(G)$ of a graph $G\in\mathcal C$ with $n$ vertices. In this note we relate this value to shallow minors and, as a corollary, we determine the right order of the $n$-th Fiedler value for some minor closed classes of graphs, including the class of planar graphs. |
|
|
|
|
|
|
|
|
|
|
|
| 1 : | Computer Science Institute of Charles University [Prague] (IUUK) |
|
|
|
Univerzita Karlova v Parze |
|
|
| 2 : | Centre d'analyse et de mathématique sociale (CAMS) |
|
|
|
CNRS : UMR8557 – École des Hautes Études en Sciences Sociales [EHESS] |
|
|
|
|
|
|
|
|
|
| Domaine | : | Mathématiques/Combinatoire |
|
|
| Liste des fichiers attachés à ce document : | ||||||||||
|
||||||||||
|
|
|
| hal-00724093, version 1 | |
| http://hal.archives-ouvertes.fr/hal-00724093 | |
| oai:hal.archives-ouvertes.fr:hal-00724093 | |
| Contributeur : Patrice Ossona De Mendez | |
| Soumis le : Vendredi 17 Août 2012, 13:31:24 | |
| Dernière modification le : Vendredi 17 Août 2012, 14:03:51 | |
