Order plus size of τ-critical graphs

被引：2

作者：

Gyarfas, Andras ^{[1
]}

Lehel, Jeno ^{[1
,2
]}

机构：

[1] Alfred Reny Math Inst, Budapest, Hungary

[2] Univ Louisville, Dept Math, Louisville, KY 40292 USA

来源：

JOURNAL OF GRAPH THEORY | 2021年 / 96卷 / 01期

关键词：

combined bound; tau-critical; order plus size;

D O I：

10.1002/jgt.22603

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let G = (V, E) be a tau-critical graph with tau(G) = t. Erdos and Gallai proved that vertical bar V vertical bar <= 2t and the bound vertical bar E vertical bar <= ( [GRAPHICS] ) was obtained by Erdos, Hajnal, and Moon. We give here the sharp combined bound vertical bar E vertical bar + vertical bar V vertical bar <= ( [GRAPHICS] ) 2 and find all graphs with equality.

引用

页码：85 / 86

页数：2