Given a complete graph with edge weights, we consider the problem of partitioning the vertices of the graph into clusters that each have at least S vertices, with each cluster represented by its minimum spanning tree(MST), and where the goal is to minimize the total weight of the edges that are in the MSTs. This is a special kind of clustering problem, the particular objective function gives a reasonable capture of the range of each cluster. It has application in Microaggragation. We give the integer programming formulation and report computational results with a branch-and-cut algorithm.

Describe models for a variant of the diameter-constrained Steiner tree problem: in a graph with a subset Q of special nodes find a minimal Steiner tree spanning a set of required nodes R subject to the condition that the maximum number of intermediate nodes in Q in any tree path does not exceed a specified value. Derive a tight model for an underlying shortest path and adapt characterizations of centers of trees that allow us to model the problem as a tree directed away from a central node/edge.

Given a digraph with real-valued arc costs, the Minimum Arborescence Problem (MAP) consists in finding an arborescence whose cost is the lowest possible. This problem is NP-hard. After presenting a multicommodity flow formulation and a Lagrangean relaxation, we propose a Local Search heuristic working on path insertion / deletion. Numerical experiments will show the efficiency of this approach.

A graph invariant is a function of a graph G which does not depend on labelling of G's vertices or edges. Graph theory is replete with theorems about graph invariants, which are either algebraic, i.e., equalities or inequalities involving such invariants, or structural, i.e., characterizations of which families of graphs are extremal for a given invariant, that is give it maximum or minimum values. Both types of results can be conjectured by the system AutoGraphiX~2 (AGX~2), in an automated way, or in an assisted way. We report here on a systematic comparison of 12 graph invariants: for each pair of them, AGX~2 considers the four operations +, -, x, / and derives best possible lower and upper bounding functions of the number of vertices, as well as extremal graphs.