A characterization of the subcubic graphs achieving equality in the Haxell-Scott lower bound for the matching number

Michael A. Henning; Zekhaya B. Shozi

doi:10.1002/jgt.22624

A characterization of the subcubic graphs achieving equality in the Haxell-Scott lower bound for the matching number

Michael A. Henning, Zekhaya B. Shozi

Mathematics and Applied Mathematics

University of Johannesburg

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

5 Citations (Scopus)

Abstract

In 2004, Biedl et al proved that if (Formula presented.) is a connected cubic graph of order (Formula presented.), then (Formula presented.), where (Formula presented.) is the matching number of (Formula presented.). The graphs achieving equality in this bound were characterized in 2010 by O and West. In 2017, Haxell and Scott proved that if (Formula presented.) is a connected subcubic graph, then (Formula presented.), where (Formula presented.) denotes the number of vertices of degree (Formula presented.) in (Formula presented.). In this paper, we characterize the graphs achieving equality in the lower bound on the matching number given by Haxell and Scott.

Original language	English
Pages (from-to)	455-471
Number of pages	17
Journal	Journal of Graph Theory
Volume	96
Issue number	4
DOIs	https://doi.org/10.1002/jgt.22624
Publication status	Published - Mar 2021

Keywords

matching number
subcubic graphs

ASJC Scopus subject areas

Geometry and Topology

Access to Document

10.1002/jgt.22624

Cite this

@article{b9ad624310894eb5afe0baae45f7702e,

title = "A characterization of the subcubic graphs achieving equality in the Haxell-Scott lower bound for the matching number",

abstract = "In 2004, Biedl et al proved that if (Formula presented.) is a connected cubic graph of order (Formula presented.), then (Formula presented.), where (Formula presented.) is the matching number of (Formula presented.). The graphs achieving equality in this bound were characterized in 2010 by O and West. In 2017, Haxell and Scott proved that if (Formula presented.) is a connected subcubic graph, then (Formula presented.), where (Formula presented.) denotes the number of vertices of degree (Formula presented.) in (Formula presented.). In this paper, we characterize the graphs achieving equality in the lower bound on the matching number given by Haxell and Scott.",

keywords = "matching number, subcubic graphs",

author = "Henning, {Michael A.} and Shozi, {Zekhaya B.}",

note = "Publisher Copyright: {\textcopyright} 2020 Wiley Periodicals LLC",

year = "2021",

month = mar,

doi = "10.1002/jgt.22624",

language = "English",

volume = "96",

pages = "455--471",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

number = "4",

}

TY - JOUR

T1 - A characterization of the subcubic graphs achieving equality in the Haxell-Scott lower bound for the matching number

AU - Henning, Michael A.

AU - Shozi, Zekhaya B.

PY - 2021/3

Y1 - 2021/3

N2 - In 2004, Biedl et al proved that if (Formula presented.) is a connected cubic graph of order (Formula presented.), then (Formula presented.), where (Formula presented.) is the matching number of (Formula presented.). The graphs achieving equality in this bound were characterized in 2010 by O and West. In 2017, Haxell and Scott proved that if (Formula presented.) is a connected subcubic graph, then (Formula presented.), where (Formula presented.) denotes the number of vertices of degree (Formula presented.) in (Formula presented.). In this paper, we characterize the graphs achieving equality in the lower bound on the matching number given by Haxell and Scott.

AB - In 2004, Biedl et al proved that if (Formula presented.) is a connected cubic graph of order (Formula presented.), then (Formula presented.), where (Formula presented.) is the matching number of (Formula presented.). The graphs achieving equality in this bound were characterized in 2010 by O and West. In 2017, Haxell and Scott proved that if (Formula presented.) is a connected subcubic graph, then (Formula presented.), where (Formula presented.) denotes the number of vertices of degree (Formula presented.) in (Formula presented.). In this paper, we characterize the graphs achieving equality in the lower bound on the matching number given by Haxell and Scott.

KW - matching number

KW - subcubic graphs

UR - http://www.scopus.com/inward/record.url?scp=85091725881&partnerID=8YFLogxK

U2 - 10.1002/jgt.22624

DO - 10.1002/jgt.22624

M3 - Article

AN - SCOPUS:85091725881

SN - 0364-9024

VL - 96

SP - 455

EP - 471

JO - Journal of Graph Theory

JF - Journal of Graph Theory

IS - 4

ER -

A characterization of the subcubic graphs achieving equality in the Haxell-Scott lower bound for the matching number

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this