21732 articles – 15570 references  [version française]

hal-00724093, version 1

A note on Fiedler value of classes with sublinear separators

Jaroslav Nesetril () 1, Patrice Ossona De Mendez (Author to contact preferably) 2

Abstract: 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]
  • Domain : Mathematics/Combinatorics
 
  • hal-00724093, version 1
  • http://hal.archives-ouvertes.fr/hal-00724093
  • oai:hal.archives-ouvertes.fr:hal-00724093
  • From: Patrice Ossona De Mendez <>
  • Submitted on: Friday, 17 August 2012 13:31:24
  • Updated on: Friday, 17 August 2012 14:03:51