21764 articles – 15575 Notices  [english version]

hal-00724093, version 1

A note on Fiedler value of classes with sublinear separators

Jaroslav Nesetril () 1, Patrice Ossona De Mendez (Auteur à contacter de préférence) 2

Résumé : 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
 
  • 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