Variable neighborhood search for extremal graphs. 22. Extending bounds for independence to upper irredundance

Mustapha Aouchiche, Odile Favaron, Pierre Hansen

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)

Abstract

A set of vertices S in a graph G is independent if no neighbor of a vertex of S belongs to S. A set of vertices U in a graph G is irredundant if each vertex v of U has a private neighbor, which may be v itself, i.e., a neighbor of v which is not a neighbor of any other vertex of U. The independence number α (resp. upper irredundance number I R) is the maximum number of vertices of an independent (resp. irredundant) set of G. In previous work, a series of best possible lower and upper bounds on α and some other usual invariants of G were obtained by the system AGX 2, and proved either automatically or by hand. These results are strengthened in the present paper by systematically replacing α by I R. The resulting conjectures were tested by AGX which could find no counter-example to an upper bound nor any case where a lower bound could not be shown to remain tight. Some proofs for the bounds on α carry over. In all other cases, new proofs are provided.

Original languageEnglish
Pages (from-to)3497-3510
Number of pages14
JournalDiscrete Applied Mathematics
Volume157
Issue number17
DOIs
Publication statusPublished - Oct 28 2009
Externally publishedYes

Keywords

  • AGX
  • Extremal graph
  • Invariant
  • Upper irredundance

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Variable neighborhood search for extremal graphs. 22. Extending bounds for independence to upper irredundance'. Together they form a unique fingerprint.

Cite this