A lower bound on the independence number of a graph

被引：15

作者：

Harant, J ^{[1
]}

机构：

[1] Tech Univ Ilmenau, Dept Math, D-98684 Ilmenau, Germany

来源：

DISCRETE MATHEMATICS | 1998年 / 188卷 / 1-3期

关键词：

independence number; stability;

D O I：

10.1016/S0012-365X(98)00048-X

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A new lower bound on the independence number of a graph is established and an accompanying efficient algorithm constructing an independent vertex set the cardinality of which is at least this lower bound is given. (C) 1998 Elsevier Science B.V. All rights reserved.

引用

页码：239 / 243

页数：5

共 14 条

[1]

[Anonymous], CASOPIS PEST MAT, DOI DOI 10.21136/CPM.1955.108220

[2]

CARO Y, UNPUB

[3]

FAJTLOWICZ S, CONJECTURES GRAFFITI

[4] ON THE RESIDUE OF A GRAPH [J].

FAVARON, O ;

MAHEO, M ;

SACLE, JF .

JOURNAL OF GRAPH THEORY, 1991, 15 (01) :39-64

[5] INDEPENDENCE AND THE HAVEL-HAKIMI RESIDUE [J].

GRIGGS, JR ;

KLEITMAN, DJ .

DISCRETE MATHEMATICS, 1994, 127 (1-3) :209-212

[6] ON REALIZABILITY OF A SET OF INTEGERS AS DEGREES OF THE VERTICES OF A LINEAR GRAPH .1. [J].

HAKIMI, SL .

JOURNAL OF THE SOCIETY FOR INDUSTRIAL AND APPLIED MATHEMATICS, 1962, 10 (03) :496-506

[7]

HARANT J, UNPUB DOMINATING SET

[8] MAXIMA FOR GRAPHS AND A NEW PROOF OF A THEOREM OF TURAN [J].

MOTZKIN, TS ;

STRAUS, EG .

CANADIAN JOURNAL OF MATHEMATICS, 1965, 17 (04) :533-&

[9] LOWER BOUNDS ON THE STABILITY NUMBER OF GRAPHS COMPUTED IN TERMS OF DEGREES [J].

MURPHY, O .

DISCRETE MATHEMATICS, 1991, 90 (02) :207-211

[10] A PROBABILISTIC LOWER-BOUND ON THE INDEPENDENCE NUMBER OF GRAPHS [J].

SELKOW, SM .

DISCRETE MATHEMATICS, 1994, 132 (1-3) :363-365

← 1 2 →