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

# Using Size for Bounding Expressions of Graph Invariants

## Jelena Sedlar, Damir Vukicevic et Pierre Hansen

With the help of the AutoGraphiX system, we study relations of the form

$\underline{b}_m \le i_1(G) \oplus i_2(G) \le \overline{b}_m$

where $i_1(G)$ and $i_2(G)$ are invariants of the graph $G$, $\oplus$ is one of the operations $-, +, /, \times$, $\underline{b}_m$ and $\overline{b}_m$ are best possible lower and upper bounding functions depending only one the size m of G. Specifically, we consider couples of indices where $i_1(G)$ is a measure of distance, i.e., diameter, radius or average eccentricity, and $i_2(G)$ is a measure of connectivity, i.e., minimum degree, edge connectivity and vertex connectivity. Conjectures are obtained and then proved in almost all cases.

, 20 pages