Turan numbers for odd wheels

被引：14

作者：

Dzido, Tomasz ^{[1
]}

Jastrzebski, Andrzej ^{[2
]}

机构：

[1] Univ Gdansk, Fac Math Phys & Informat, Inst Informat, PL-80308 Gdansk, Poland

[2] Gdansk Univ Technol, Fac Elect Telecommun & Informat, Dept Algorithms & Syst Modeling, PL-80233 Gdansk, Poland

来源：

DISCRETE MATHEMATICS | 2018年 / 341卷 / 04期

关键词：

Turan numbers; Odd wheels;

D O I：

10.1016/j.disc.2017.10.003

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The Turan number ex(n, G) is the maximum number of edges in any n-vertex graph that does not contain a subgraph isomorphic to G. A wheel W-n is a graph on n vertices obtained from a Cn-1 by adding one vertex w and making w adjacent to all vertices of the Cn-1. We obtain two exact values for small wheels: ex(n, W-5) = left perpendicularn(2/4) + n/2right perpendicular, ex(n, W-7) = left perpendicularn(2)/4 + n/2 +1right perpendicular. Given that ex(n, W-6) is already known, this paper completes the spectrum for all wheels up to 7 vertices. In addition, we present the construction which gives us the lower bound ex(n, W2k+1) > + left perpendicularn(2)/4 + right perpendicular + left perpendicularn/2 right perpendicular in general case. (C) 2017 Elsevier B.V. All rights reserved.

引用

页码：1150 / 1154

页数：5