Unicycle graphs and uniquely restricted maximum matchings |
| |
| Affiliation: | 1. Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, UK;2. Department of Mathematical Sciences, University of Memphis, Memphis, TN 38152, USA;3. London Institute for Mathematical Sciences, 35a South St., Mayfair, London W1K 2XF, UK;4. Lomonosov Moscow State University, Mechanics and Mathematics Faculty, Department of Math. Statistics and Random Processes, Leninskie gory, Moscow, 119991, Russia;5. Moscow Institute of Physics and Technology, Faculty of Innovations and High Technology, Institutskiy per., Dolgoprudny, Moscow Region, 141700, Russia;1. Sobolev Institute of Mathematics, Ak. Koptyug av. 4, Novosibirsk, 630090, Russia;2. School of Mathematical Sciences, Hebei International Joint Research Center for Mathematics and Interdisciplinary Science, Hebei Normal University, Shijiazhuang 050024, PR China;3. Novosibirsk State University, Pirogova str. 2, Novosibirsk, 630090, Russia;4. Three Gorges Mathematical Research Center, China Three Gorges University, 8 University Avenue, Yichang 443002, Hubei Province, China;1. Department of Computer Science and Information Engineering, National Cheng Kung University, No. 1, University Road, Tainan 701, Taiwan;2. Institute of Manufacturing Information Systems, National Cheng Kung University, No. 1, University Road, Tainan 701, Taiwan |
| |
| Abstract: | A matching M is called uniquely restricted in a graph G if it is the unique perfect matching of the subgraph induced by the vertices that M saturates. G is a unicycle graph if it owns only one cycle. Golumbic, Hirst and Lewenstein observed that for a tree or a graph with only odd cycles the size of a maximum uniquely restricted matching is equal to the matching number of the graph. In this paper we characterize unicycle graphs enjoying this equality. Moreover, we describe unicycle graphs with only uniquely restricted maximum matchings. Using these findings, we show that unicycle graphs having only uniquely restricted maximum matchings can be recognized in polynomial time. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
