2019/11/08 by Mehmet Akif Yıldız, Yıldız, Mehmet Akif
Computer Science · Mathematics · #05C70 #05C85 #Advanced Graph Theory Research #Algorithms and Data Compression #Combinatorics (math.CO) #FOS: Mathematics #Graph Theory and Algorithms #math.CO #msc:05C70 #msc:05C85
paper · pdf · doi:10.48550/arxiv.1911.04277
8 pages
arxiv created 2019/11/08 · openalex publication_date 2019/11/08 · arxiv updated 2019/11/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A maximal matching M that consists of independent edges is a subgraph of a simple and undirected graph G for which G-M forms an independent set. A graph G is called equimatchable if all maximal matchings have the same number of edges. On the other hand, G is called as a split graph if its vertices can be partitioned into two subsets for which one of them forms a clique whereas the second forms an independent set. We will give a linear time algorithm for recognition of equimatchable split graphs.