On Weighted Convex Graphs

Abstract

The main objective of this paper is to develop Krein-Milman-type theorems and Ulam-type stability results for graphs. To establish these results, we introduce several meaningful definitions of vertex-weighted convex graphs inspired by the concept of sequential convexity. We also present a close relationship between the two discrete structures, namely sequential convexity and perfect binary trees. We show that if a graph satisfies a certain convexity property approximately, then this property can be made exact by minimally perturbing the weights assigned to its vertices. Furthermore, we study several structural characterisations, formulate convex minorants for weighted graphs, and derive sandwich-type results. Special emphasis is placed on trees, and an investigation of extremal value problems is also carried out