Journées de l'optimisation 2007 Optimizations days

We consider the problem of determining the size w(G) of a maximum clique in a graph G. Given any procedure U that computes an upper bound U(G) on w(G), we present a decomposition algorithm that produces an upper bound U’(G) that is at least as good as U(G). Tests on DIMACS instances demonstrate that the proposed algorithm is able, in average, to reduce the gap between U(G) and w(G) by about 60%. We also show how to use our algorithm to improve the computation of lower bounds on w(G).

We prove that the average distance between the vertices of a connected graph does not exceed half the maximum size (number of vertices) of an induced forest (graph without cycles). As a corollary, this result permits to give a positive answer to a 15 years old conjecture. We also announce a stronger conjecture.

The Randic index, a graph invariant with applications in chemistry, is widely studied by graph theorists. Since its definition by Randic in 1975, more than 1500 papers deal with it. Using the AutoGraphiX system, an automated comparison, of the Randic index with some of the most studied invariants in graph theory, is made. Here, we report on the results and conjectures involving 9 invariants: minimum, average and maximum degree, diameter, girth, algebraic and node connectivity, index and matching numbers.

The 2-stability number of a graph G is the largest number of vertices in a 2-colorable subgraph of G. A graph is 2-stable-critical if it has no isolated vertices and removing any of its edges increases its 2-stability number. We study 2-stable-critical graphs using the AutoGraphiX system.