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

Michael A. Henning; Anders Yeo

doi:10.1002/jgt.22846

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

Michael A. Henning^*
, Anders Yeo

^*Kontaktforfatter

University of Johannesburg

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › peer review

167 Downloads (Pure)

Abstract

Let (Formula presented.) be the set of pairs (Formula presented.) of real numbers with the property there exists a constant (Formula presented.), depending only on (Formula presented.) and (Formula presented.), such that (Formula presented.) for every connected graph (Formula presented.) of order (Formula presented.), size (Formula presented.), with maximum degree at most (Formula presented.) and edge-connectivity at least (Formula presented.). In a recent paper, the authors give a complete description of the set (Formula presented.). In this article we raise the problem to a higher level, and give a complete description of the convex set (Formula presented.) for all (Formula presented.), and determine its extreme points.

Originalsprog	Engelsk
Tidsskrift	Journal of Graph Theory
Vol/bind	101
Udgave nummer	4
Sider (fra-til)	643-667
ISSN	0364-9024
DOI	https://doi.org/10.1002/jgt.22846
Status	Udgivet - dec. 2022

Bibliografisk note

Funding Information:
The authors wish to thank the referees for their considerable efforts in working through our article, and for their very helpful comments and suggestions that resulted in a much improved version of the article. Research of the first author supported in part by the University of Johannesburg, and research of the second author supported by the Danish research council under grant number DFF‐7014‐00037B.

Publisher Copyright:
© 2022 Wiley Periodicals LLC.

Finansiering

The authors wish to thank the referees for their considerable efforts in working through our article, and for their very helpful comments and suggestions that resulted in a much improved version of the article. Research of the first author supported in part by the University of Johannesburg, and research of the second author supported by the Danish research council under grant number DFF‐7014‐00037B.

Dokumenter og links

10.1002/jgt.22846

Open Access VersionAccepteret manuskript, 255 KB

SDU link

Tjek adgangen til materialet i Syddansk Universitetsbiblioteks søgemaskine

Citationsformater

@article{fce8f9051458419faa1db1f1640d7399,

title = "A complete description of convex sets associated with matchings and edge-connectivity in graphs",

abstract = "Let (Formula presented.) be the set of pairs (Formula presented.) of real numbers with the property there exists a constant (Formula presented.), depending only on (Formula presented.) and (Formula presented.), such that (Formula presented.) for every connected graph (Formula presented.) of order (Formula presented.), size (Formula presented.), with maximum degree at most (Formula presented.) and edge-connectivity at least (Formula presented.). In a recent paper, the authors give a complete description of the set (Formula presented.). In this article we raise the problem to a higher level, and give a complete description of the convex set (Formula presented.) for all (Formula presented.), and determine its extreme points.",

keywords = "convex set, edge-connectivity, matching number, maximum degree",

author = "Henning, \{Michael A.\} and Anders Yeo",

note = "Funding Information: The authors wish to thank the referees for their considerable efforts in working through our article, and for their very helpful comments and suggestions that resulted in a much improved version of the article. Research of the first author supported in part by the University of Johannesburg, and research of the second author supported by the Danish research council under grant number DFF‐7014‐00037B. Publisher Copyright: {\textcopyright} 2022 Wiley Periodicals LLC.",

year = "2022",

month = dec,

doi = "10.1002/jgt.22846",

language = "English",

volume = "101",

pages = "643--667",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley",

number = "4",

}

TY - JOUR

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

AU - Henning, Michael A.

AU - Yeo, Anders

N1 - Funding Information: The authors wish to thank the referees for their considerable efforts in working through our article, and for their very helpful comments and suggestions that resulted in a much improved version of the article. Research of the first author supported in part by the University of Johannesburg, and research of the second author supported by the Danish research council under grant number DFF‐7014‐00037B. Publisher Copyright: © 2022 Wiley Periodicals LLC.

PY - 2022/12

Y1 - 2022/12

N2 - Let (Formula presented.) be the set of pairs (Formula presented.) of real numbers with the property there exists a constant (Formula presented.), depending only on (Formula presented.) and (Formula presented.), such that (Formula presented.) for every connected graph (Formula presented.) of order (Formula presented.), size (Formula presented.), with maximum degree at most (Formula presented.) and edge-connectivity at least (Formula presented.). In a recent paper, the authors give a complete description of the set (Formula presented.). In this article we raise the problem to a higher level, and give a complete description of the convex set (Formula presented.) for all (Formula presented.), and determine its extreme points.

AB - Let (Formula presented.) be the set of pairs (Formula presented.) of real numbers with the property there exists a constant (Formula presented.), depending only on (Formula presented.) and (Formula presented.), such that (Formula presented.) for every connected graph (Formula presented.) of order (Formula presented.), size (Formula presented.), with maximum degree at most (Formula presented.) and edge-connectivity at least (Formula presented.). In a recent paper, the authors give a complete description of the set (Formula presented.). In this article we raise the problem to a higher level, and give a complete description of the convex set (Formula presented.) for all (Formula presented.), and determine its extreme points.

KW - convex set

KW - edge-connectivity

KW - matching number

KW - maximum degree

U2 - 10.1002/jgt.22846

DO - 10.1002/jgt.22846

M3 - Journal article

AN - SCOPUS:85132547456

SN - 0364-9024

VL - 101

SP - 643

EP - 667

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 4

ER -

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

Abstract

Bibliografisk note

Finansiering

Dokumenter og links

SDU link

Fingeraftryk

Citationsformater