A complete description of convex sets associated with matchings and edge-connectivity in graphs

Let L k , lambda ${L}_{k,\lambda }$ be the set of pairs ( gamma , beta ) $(\gamma ,\beta )$ of real numbers with the property there exists a constant C ( k , lambda ) $C(k,\lambda )$, depending only on k $k$ and lambda $\lambda $, such that alpha ' ( G ) >= gamma n + beta m - C ( k , lambda ) ${\alpha }<^>{<^>{\prime} }(G)\ge \gamma n+\beta m-C(k,\lambda )$ for every connected graph G $G$ of order n $n$, size m $m$, with maximum degree at most k $k$ and edge-connectivity at least lambda >= 1 $\lambda \ge 1$. In a recent paper, the authors give a complete description of the set L k , 1 ${L}_{k,1}$. In this article we raise the problem to a higher level, and give a complete description of the convex set L k , lambda ${L}_{k,\lambda }$ for all k >= lambda >= 2 $k\ge \lambda \ge 2$, and determine its extreme points.

Automated summary

The paper discusses the complete description of the convex set Lk, lambda for all k greater than or equal to lambda, and also determines its extreme points.