Groupe d’études et de recherche en analyse des décisions

# Bounds on differences between some graph theoretic invariants

## Mustapha Aouchiche, Pierre Hansen, Alain Hertz et Cherif Sellal

In the present paper, we are interested in bounding differences between graph invariants as well as in characterizing the corresponding extremal graphs. This kind of results belongs to the more general form known as AGX Form 1 which is extensively studied using the AutoGraphiX system at GERAD, Montreal. The graph invariants involved in the present work are the proximity, the remoteness, the eccentricity, the average distance, the frequencies of the maximum and minimum degrees, the domination number, the stability number and the chromatic number.

, 15 pages