Variable Neighborhood Search for Extremal Graphs, 24. Results about the clique number.
Jelena Sedlar, Damir Vukičević, Mustapha Aouchiche, Pierre Hansen · Studia informatica universalis · 2010
A set of vertices S in a graph G is a clique if any two of its vertices are adjacent. The clique number ω is the maximum cardinality of a clique in G. A series of best possible lower and upper bounds on the difference, sum, ratio or product of ω and some other common invariants of G were obtained by the system AGX 2, and most of them 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, algebraic, node and edge connectivities, index, average distance, remoteness, radius and diameter. MOTS-CLES : Cardinalite maximum d’une clique, Invariant, Graphe extreme, AGX