Maximum size of connected graphs with bounded maximum degree and matching number

Zixuan Yang; Hongliang Lu; Shenggui Zhang

doi:10.1016/j.disc.2026.115019

Maximum size of connected graphs with bounded maximum degree and matching number

Zixuan Yang
, Hongliang Lu
, Shenggui Zhang

School of Mathematics and Statistics

Research output: Contribution to journal › Article › peer-review

Abstract

In this paper, we determine the maximum number of edges of connected graphs with given maximum degree and matching number. This gives an answer to a problem posed by Dibek et al. (2017) [6] . We also show that the bound in our result is tight.

Original language	English
Article number	115019
Journal	Discrete Mathematics
Volume	349
Issue number	7
DOIs	https://doi.org/10.1016/j.disc.2026.115019
State	Published - Jul 2026

Keywords

Extremal graph
Matching number
Maximum degree

Access to Document

10.1016/j.disc.2026.115019

Cite this

@article{63e09cb56b6448f9a35a2150854fafe4,

title = "Maximum size of connected graphs with bounded maximum degree and matching number",

abstract = "In this paper, we determine the maximum number of edges of connected graphs with given maximum degree and matching number. This gives an answer to a problem posed by Dibek et al. (2017) [6] . We also show that the bound in our result is tight.",

keywords = "Extremal graph, Matching number, Maximum degree",

author = "Zixuan Yang and Hongliang Lu and Shenggui Zhang",

note = "Publisher Copyright: {\textcopyright} 2026 Elsevier B.V.",

year = "2026",

month = jul,

doi = "10.1016/j.disc.2026.115019",

language = "英语",

volume = "349",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "7",

}

TY - JOUR

T1 - Maximum size of connected graphs with bounded maximum degree and matching number

AU - Yang, Zixuan

AU - Lu, Hongliang

AU - Zhang, Shenggui

PY - 2026/7

Y1 - 2026/7

N2 - In this paper, we determine the maximum number of edges of connected graphs with given maximum degree and matching number. This gives an answer to a problem posed by Dibek et al. (2017) [6] . We also show that the bound in our result is tight.

AB - In this paper, we determine the maximum number of edges of connected graphs with given maximum degree and matching number. This gives an answer to a problem posed by Dibek et al. (2017) [6] . We also show that the bound in our result is tight.

KW - Extremal graph

KW - Matching number

KW - Maximum degree

UR - https://www.scopus.com/pages/publications/105028904071

U2 - 10.1016/j.disc.2026.115019

DO - 10.1016/j.disc.2026.115019

M3 - 文章

AN - SCOPUS:105028904071

SN - 0012-365X

VL - 349

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 7

M1 - 115019

ER -

Maximum size of connected graphs with bounded maximum degree and matching number

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this