Premium
A characterization of the subcubic graphs achieving equality in the Haxell‐Scott lower bound for the matching number
Author(s) -
Henning Michael A.,
Shozi Zekhaya B.
Publication year - 2021
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22624
Subject(s) - mathematics , combinatorics , matching (statistics) , upper and lower bounds , graph , characterization (materials science) , order (exchange) , discrete mathematics , mathematical analysis , statistics , materials science , nanotechnology , finance , economics
In 2004, Biedl et al proved that if G is a connected cubic graph of order n , then α ′ ( G ) ≥ 1 9 ( 4 n − 1 ) , where α ′ ( G ) is the matching number of G . The graphs achieving equality in this bound were characterized in 2010 by O and West. In 2017, Haxell and Scott proved that if G is a connected subcubic graph, then α ′ ( G ) ≥ 4 9 n 3 ( G ) + 3 9 n 2 ( G ) + 2 9 n 1 ( G ) − 1 9 , where n i ( G ) denotes the number of vertices of degree i in G . In this paper, we characterize the graphs achieving equality in the lower bound on the matching number given by Haxell and Scott.