A characterization of the subcubic graphs achieving equality in the Haxell‐Scott lower bound for the matching number. Issue 4 (30th September 2020)

• Record Type: Journal Article
• Authors: Henning, Michael A.; Shozi, Zekhaya B.
• Is Part Of: Journal of graph theory. Volume 96:Issue 4(2021)
• Page Start: 455
• Page End: 471
• Publication Date: 2020-09-30
• Subjects: matching number -- subcubic graphs; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22624
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: 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.