Extremal C4-Free/C5-Free Planar Graphs

被引：35

作者：

Dowden, Chris ^{[1
]}

机构：

[1] London Sch Econ, Dept Math, London, England

来源：

JOURNAL OF GRAPH THEORY | 2016年 / 83卷 / 03期

基金：

欧洲研究理事会;

关键词：

extremal graphs; planar graphs; C-4-free; C-5-free;

D O I：

10.1002/jgt.21991

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We study the topic of "extremal" planar graphs, defining ex(P) (n, H) to be the maximum number of edges possible in a planar graph on n vertices that does not contain a given graph H as a subgraph. In particular, we examine the case when H is a small cycle, obtaining ex(P) (n, C-4) <= 15/7 (n-2) for all n >= 4 and ex(P) (n, C-5) = 12n-33/5 for all n >= 11, and showing that both of these bounds are tight. (C) 2015 Wiley Periodicals, Inc.

引用

页码：213 / 230

页数：18