On unicyclic graphs with uniquely restricted maximum matchings (Q2637732): Difference between revisions

A matching \(M\) is uniquely restricted in a graph \(G\) if it is the unique matching in the graph it spans. The authors study unicyclic bipartite graphs \(G\) in which \(\mu_r(G) = \mu(G)\), where \(\mu(G)\) is the matching number of \(G\) and \(\mu_r(G)\) is the maximum size of a uniquely restricted matching. A characterization of unicyclic bipartite graphs having only uniquely restricted maximum matchings is given. They also give polynomial-time algorithms that recognize such graphs. They prove that if \(G\) is a unicyclic bipartite graph with cycle \(C\), then the following are equivalent: i) \(\mu_r(G) = \mu(G)\); ii) there is a tree \(T\) of the forest \(G - C\) and a vertex \(e \in V(T)\) such that \(\mu(T - w) = \mu(T)\), where \(vw \in E(G) - E(C)\) for some \(v \in V(C)\); iii) there is an edge \(vw\) in a maximum matching of \(G\) such that \(|\{v,w\}| \cap V(C) = 1\).