An upper bound for the independent domination number

被引：16

作者：

Sun, L ^{[1
]}

Wang, JF

机构：

[1] Beijing Inst Technol, Dept Appl Math, Beijing 100081, Peoples R China

[2] Chinese Acad Sci, Inst Appl Math, Beijing 100080, Peoples R China

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 1999年 / 76卷 / 02期

基金：

中国国家自然科学基金;

关键词：

D O I：

10.1006/jctb.1999.1907

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let G be a simple graph of order n and minimum degree delta. The independent domination number i(G) is defined to be the minimum cardinality among all maximal independent sets of vertices of G. In this paper we show that i(G) less than or equal to n + 2 delta - 2 root n delta. Thus a conjecture of Favaron is settled ill the affirmative. (C) 1999 Academic Press.

引用

页码：240 / 246

页数：7

共 12 条

[1] GRAPH-THEORETIC PARAMETERS CONCERNING DOMINATION, INDEPENDENCE, AND IRREDUNDANCE [J].

BOLLOBAS, B ;

COCKAYNE, EJ .

JOURNAL OF GRAPH THEORY, 1979, 3 (03) :241-249

[2] THE PRODUCT OF THE INDEPENDENT DOMINATION NUMBERS OF A GRAPH AND ITS COMPLEMENT [J].

COCKAYNE, EJ ;

FAVARON, O ;

LI, H ;

MACGILLIVRAY, G .

DISCRETE MATHEMATICS, 1991, 90 (03) :313-317

[3] ON A NORDHAUS-GADDUM TYPE PROBLEM FOR INDEPENDENT DOMINATION [J].

COCKAYNE, EJ ;

FRICKE, G ;

MYNHARDT, CM .

DISCRETE MATHEMATICS, 1995, 138 (1-3) :199-205

[4] CONTRIBUTIONS TO THE THEORY OF DOMINATION, INDEPENDENCE AND IRREDUNDANCE IN GRAPHS [J].

COCKAYNE, EJ ;

FAVARON, O ;

PAYAN, C ;

THOMASON, AG .

DISCRETE MATHEMATICS, 1981, 33 (03) :249-258

[5]

COCKAYNE EJ, 1974, UTILITAS MATH

[6] 2 RELATIONS BETWEEN THE PARAMETERS OF INDEPENDENCE AND IRREDUNDANCE [J].

FAVARON, O .

DISCRETE MATHEMATICS, 1988, 70 (01) :17-20

[7] ON MINIMUM MAXIMAL INDEPENDENT SETS OF A GRAPH [J].

HAVILAND, J .

DISCRETE MATHEMATICS, 1991, 94 (02) :95-101

[8] INDEPENDENT DOMINATION IN REGULAR GRAPHS [J].

HAVILAND, J .

DISCRETE MATHEMATICS, 1995, 143 (1-3) :275-280

[9]

HAVILAND J, 1989, THESIS U CAMBRIDGE

[10] BIBLIOGRAPHY ON DOMINATION IN GRAPHS AND SOME BASIC DEFINITIONS OF DOMINATION PARAMETERS [J].

HEDETNIEMI, ST ;

LASKAR, RC .

DISCRETE MATHEMATICS, 1990, 86 (1-3) :257-277

← 1 2 →