Maximum matchings in regular graphs |
| |
Authors: | Dong Ye |
| |
Institution: | Department of Mathematical Sciences and Center for Computational Sciences, Middle Tennessee State University, Murfreesboro, TN 37132, United States |
| |
Abstract: | It was conjectured by Mkrtchyan, Petrosyan and Vardanyan that every graph with has a maximum matching such that any two -unsaturated vertices do not share a neighbor. The results obtained in Mkrtchyan et al. (2010), Petrosyan (2014) and Picouleau (2010) leave the conjecture unknown only for -regular graphs with . All counterexamples for -regular graphs given in Petrosyan (2014) have multiple edges. In this paper, we confirm the conjecture for all -regular simple graphs and also -regular multigraphs with . |
| |
Keywords: | Maximum matching Regular graphs |
本文献已被 ScienceDirect 等数据库收录! |
|