Group for Research in Decision Analysis

# Edge realizability of connected simple graphs

## Pierre Hansen, Alain Hertz, Cherif Sellal, Damir Vukicevic, Mustapha Aouchiche, and Gilles Caporossi

Necessary and sufficient conditions are provided for the existence of a simple graph, or a simple connected graph with given numbers $$m_{ij}$$ of edges with end-degrees $$i,j$$ for $$i\leq j\in \left\{ 1,2,\ldots,\Delta \right\}$$, where $$\Delta$$ is the maximum degree. Moreover this allows to determine the $$k^{th}$$ minimum or maximum value of all Adriatic indices together with the corresponding graphs.

, 19 pages