We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
A complete description of convex sets associated with matchings and edge‐connectivity in graphs.
- Authors
Henning, Michael A.; Yeo, Anders
- Abstract
Let Lk,λ ${L}_{k,\lambda }$ be the set of pairs (γ,β) $(\gamma ,\beta)$ of real numbers with the property there exists a constant C(k,λ) $C(k,\lambda)$, depending only on k $k$ and λ $\lambda $, such that α′(G)≥γn+βm−C(k,λ) ${\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 λ≥1 $\lambda \ge 1$. In a recent paper, the authors give a complete description of the set Lk,1 ${L}_{k,1}$. In this article we raise the problem to a higher level, and give a complete description of the convex set Lk,λ ${L}_{k,\lambda }$ for all k≥λ≥2 $k\ge \lambda \ge 2$, and determine its extreme points.
- Subjects
CONVEX sets; REAL numbers; GRAPH connectivity
- Publication
Journal of Graph Theory, 2022, Vol 101, Issue 4, p643
- ISSN
0364-9024
- Publication type
Article
- DOI
10.1002/jgt.22846