2015/01/29 by Eduard Eiben, Eiben, Eduard, Michal Kotrbčı́k +2
Computer Science · Mathematics · #05C70 #Advanced Graph Theory Research #Bipartite graph #Combinatorics #Combinatorics (math.CO) #Complement graph #Discrete mathematics #FOS: Mathematics #Graph #Graph Labeling and Dimension Problems #Graph power #Independence number #Limits and Structures in Graph Theory #Line graph #Mathematics #math.CO #msc:05C70
paper · pdf · doi:10.48550/arxiv.1501.07549
14 pages
arxiv created 2015/01/29 · openalex publication_date 2015/01/29 · arxiv updated 2015/01/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
A graph is equimatchable if each of its matchings is a subset of a maximum matching. It is known that any 2-connected equimatchable graph is either bipartite, or factor-critical, and that these two classes are disjoint. This paper provides a description of k-connected equimatchable factor-critical graphs with respect to their k-cuts for k≥ 3. As our main result we prove that if G is a k-connected equimatchable factor-critical graph with at least 2k+3 vertices and a k-cut S, then G-S has exactly two components and both these components are close to being complete or complete bipartite. If both components of G-S additionally have at least 3 vertices and k≥ 4, then the graph has independence number 2. On the other hand, since every 2-connected odd graph with independence number 2 is equimatchable, we get the following result. For any k≥ 4 let G be a k-connected odd graph with at least 2k+3 vertices and a k-cut S such that G-S has two components with at least 3 vertices. Then G has independence number 2 if and only if it is equimatchable and factor-critical. Furthermore, we show that a 2-connected odd graph G with at least 4 vertices has independence number at most 2 if and only if G is equimatchable and factor-critical and G+e is equimatchable for every edge of the complement of G.