• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

Turán Type Results for Distance Graphs

Discrete and Computational Geometry. 2016. Vol. 56. No. 3. P. 814-832.
Shabanov L., Raigorodskii A.

The classical Turán theorem determines the minimum number of edges in a graph on n vertices with independence number α. We consider unit-distance graphs on the Euclidean plane, i.e., graphs G= (V, E) with V⊂ R2 and E= {{x, y} : | x- y| = 1} , and show that the minimum number of edges in a unit-distance graph on n vertices with independence number α⩽ λn, λ∈[14,27], is bounded from below by the quantity 19-50λ3n, which is several times larger than the general Turán bound and is tight at least for λ=27. © 2016, Springer Science+Business Media New York.