Variable neighborhood search for extremal graphs. 21. Conjectures and results about the independence number

被引：14

作者：

Aouchiche, Mustapha ^{[1
]}

Brinkmann, Gunnar ^{[3
]}

Hansen, Pierre ^{[1
,2
]}

机构：

[1] HEC Montreal, Montreal, PQ, Canada

[2] Gerad, Montreal, PQ, Canada

[3] Univ Ghent, Dept Appl Math & Comp Sci, B-9000 Ghent, Belgium

来源：

DISCRETE APPLIED MATHEMATICS | 2008年 / 156卷 / 13期

关键词：

independence number; invariant; extremal graph; AGX;

D O I：

10.1016/j.dam.2008.03.011

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A set of vertices S in a graph G is independent if no neighbor of a vertex of S belongs to S. The independence number alpha is the maximum cardinality of ail independent set of G. A series of best possible lower and Upper bounds on alpha, and some other common invariants of G are obtained by the system AGX 2. and proved either automatically or by hand. In the present paper, we report on such lower and upper bounds considering, as second invariant, minimum, average and maximum degree, diameter, radius, average distance, spread of eccentricities, chromatic number and matching number. (c) 2008 Elsevier B.V. All rights reserved.

引用

页码：2530 / 2542

页数：13

共 23 条

[1]

Aouchiche M., 2005, Electron. Notes Discret. Math, V22, P515, DOI [10.1016/j.endm.2005.06.090, DOI 10.1016/J.ENDM.2005.06.090]

[2]

Aouchiche M, 2006, VARIABLE NEIGHBORHOO, P281

[3]

AOUCHICHE M, 2007, VARIABLE NEIGHBORHOO, V22

[4]

AOUCHICHE M, 2006, THESIS ECOLE POLYTEC