G-2007-100
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
where and
are invariants of the graph
,
is one
of the operations
,
and
are best possible lower and upper bounding functions depending only one the
size m of G. Specifically, we consider couples of indices where
is a measure of distance, i.e., diameter, radius or average
eccentricity, and
is a measure of connectivity, i.e., minimum
degree, edge connectivity and vertex connectivity. Conjectures are obtained
and then proved in almost all cases.
Paru en décembre 2007 , 20 pages