On Unicyclic Graphs with Uniquely Restricted Maximum Matchings |
| |
Authors: | Vadim E. Levit Eugen Mandrescu |
| |
Affiliation: | 1. Department of Computer Science and Mathematics, Ariel University Center of Samaria, Ariel, Israel 2. Department of Computer Science, Holon Institute of Technology, Holon, Israel
|
| |
Abstract: | A graph is called unicyclic if it owns only one cycle. 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. Clearly, μ r (G) ≤ μ(G), where μ r (G) denotes the size of a maximum uniquely restricted matching, while μ(G) equals the matching number of G. In this paper we study unicyclic bipartite graphs enjoying μ r (G) = μ(G). In particular, we characterize unicyclic bipartite graphs having only uniquely restricted maximum matchings. Finally, we present some polynomial time algorithms recognizing unicyclic bipartite graphs with (only) uniquely restricted maximum matchings. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|