IMPROVED LOWER BOUNDS ON K-INDEPENDENCE

被引：59

作者：

CARO, Y ^{[1
]}

TUZA, Z ^{[1
]}

机构：

[1] HUNGARIAN ACAD SCI,INST COMP & AUTOMAT,H-1250 BUDAPEST,HUNGARY

来源：

JOURNAL OF GRAPH THEORY | 1991年 / 15卷 / 01期

关键词：

D O I：

10.1002/jgt.3190150110

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A vertex set Y in a (hyper)graph is called k-independent if in the sub(hyper)graph induced by Y every vertex is incident to less than k edges. We prove a lower bound for the maximum cardinality of a k-independent set-in terms of degree sequences-which strengthens and generalizes several previously known results, including Turan's theorem.

引用

页码：99 / 107

页数：9

共 10 条

[1] ON TURAN THEOREM FOR SPARSE GRAPHS [J].

AJTAI, M ;

ERDOS, P ;

KOMLOS, J ;

SZEMEREDI, E .

COMBINATORICA, 1981, 1 (04) :313-317

[2] LARGE INDUCED DEGENERATE SUBGRAPHS [J].

ALON, N ;

KAHN, J ;

SEYMOUR, PD .

GRAPHS AND COMBINATORICS, 1987, 3 (03) :203-211

[3]

Caro Y., 1979, TECHNICAL REPORT TEC

[4]

CARO Y, UNPUB LARGE INDEPEND

[5]

Favaron O., 1988, ARS COMBINATORIA, V25, P159

[6] DEGREES AND INDEPENDENT SETS OF HYPERGRAPHS [J].

HANSEN, P ;

LOREA, M .

DISCRETE MATHEMATICS, 1976, 14 (04) :305-309

[7] BIPARTITE DENSITY AND THE INDEPENDENCE RATIO [J].

LOCKE, SC .

JOURNAL OF GRAPH THEORY, 1986, 10 (01) :47-53

[8]

MEYER JC, 1972, CR ACAD SCI A MATH, V274, P144

[9]

Turan P., 1941, MAT FIZ LAPOK, V48, P436

[10]

WEI VK, 1981, TM81112179 BELL LAB

← 1 →