Regular graphs with equal matching number and independence number

2020/01/07 by Hongliang Lu, Lu, Hongliang, Xixuan yang +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.2001.01937

openalex publication_date 2020/01/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let r≥ 3 be an integer and G be a graph. Let δ(G), Δ(G), α(G) and μ(G) denotes minimum degree, maximum degree, independence number and matching number of G, respectively. Recently, Caro, Davila and Pepper proved δ(G)α(G)≤ Δ(G)μ(G). Mohr and Rautenbach characterized the extremal graphs for non-regular graphs and 3-regular graphs. In this note, we characterize the extremal graphs for all r-regular graphs in term of Gallai-Edmonds Structure Theorem, which extends Mohr and Rautenbach's result.

Related

• Cubic graphs with equal independence number and matching number
• Comparing the p-independence number of regular graphs to the q-independence number of their line graphs
• On the regular k-independence number of graphs
• Matchings in regular graphs: minimizing the partition function
• Uniqueness of the extremal graph in the problem of maximizing the number of independent sets in regular graphs