Increasing the upper irredundance number of a graph by adding edges
by
C. M. Mynhardt
University of South Africa
Coauthors: E. J. Cockayne (University of Victoria), O. Favaron (Université Paris-Sud)

It is easy to find a graph G and an edge e of the complement of G such that the upper irredundance number IR increases when e is added to G, but does there exist a graph whose upper irredundance number increases whenever an edge is added? We obtain properties of such graphs, particularly for the case where \beta( G) = IR( G) = 2 (where \beta( G) denotes the vertex independence number of G).

Date received: March 9, 2001