2020/08/04 by Wouter Cames van Batenburg, van Batenburg, Wouter Cames
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2008.01863
openalex publication_date 2020/08/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We prove that every connected cubic graph with n vertices has a maximal matching of size at most (5)/(12) n+ (1)/(2). This confirms the cubic case of a conjecture of Baste, Fürst, Henning, Mohr and Rautenbach (2019) on regular graphs. More generally, we prove that every graph with n vertices and m edges and maximum degree at most 3 has a maximal matching of size at most (4n-m)/(6)+ (1)/(2). These bounds are attained by the graph K3,3, but asymptotically there may still be some room for improvement. Moreover, the claimed maximal matchings can be found efficiently. As a corollary, we have a ((25)/(18) + O ( (1)/(n))) -approximation algorithm for minimum maximal matching in connected cubic graphs.