All graphs in this question are finite, simple, undirected, and unweighted. A graph is said to be factorizable if has a perfect matching, and non-factorizable otherwise. An edge in a graph is said to be allowed if it belongs to some maximum matching of the graph. Call a graph $G$ permissive1 if every edge of $G$ is allowed.

I am interested in the properties of non-factorizable permissive graphs. What do we know about these? Where can I read up more on such graphs?

I could find quite a bit of existing work, both structural [1, 2] and algorithmic [3], on factorizable permissive graphs, which are called matching-covered graphs in the literature. However, I could not find anything at all about the case when every edge of a graph belongs to some maximum matching of the graph, and the graph itself does not have a perfect matching. What properties do such graphs have? Do we know something about their structure?

[1] On the structure of factorizable graphs. Lovasz, 1972.

[2] Extending matchings in graphs: A survey. Plummer, 1994

[3] An $O(VE)$ algorithm for ear decompositions of matching-covered graphs. de Carvalho and Cheriyan, 2005

1 My terminology, not standard.

  • $\begingroup$ What do you call a maximum matching? I have seen this terminology to describe matchings of a graph that cannot be extended with another edge. In this case, any matching is a subset of a maximal matching in a finite graph, and in particular every edge belongs to a maximal matching. $\endgroup$ – zarathustra Apr 14 '15 at 7:21
  • $\begingroup$ @zarathustra: "matchings of a graph that cannot be extended with another edge" are called maximal matchings, as you yourself do in your second sentence. A maximum matching (in a graph without weights, as are those in my question) is a matching of the largest size. I am interested in edges which belong to maximmum matchings and not just those which belong to maximal matchings; these latter are, as you pointed out, not very interesting. $\endgroup$ – G Philip Apr 14 '15 at 8:25
  • $\begingroup$ My bad, I really should have thought about this for some more seconds before posting this silly comment. $\endgroup$ – zarathustra Apr 14 '15 at 8:43

The the Edmonds-Gallai decomposition could be what you're looking for. It decomposes a graph into sets $A$, $B$ and $C$, where $A$ is all the vertices missed by at least one maximum matching, $B = N(A)$, and $C$ is all other vertices. Basically, every maximum matching matches vertices in $B$ to odd components of $G - B$ in $A$. In $G - B$, $C$ consists of even components with perfect matchings.

If you follow what this means for a permissive graph, $B$ must be an independent set, since such edges must not be used in a maximum matching. Furthermore, there are no edges from $C$ to the rest of the graph (so if we assume $G$ is connected, $C$ is empty). That's quite a bit of structure right there. I believe the components of $A$ are automatically permissive, and that any of the edges from $A$ to $B$ can automatically be used in maximum matchings, but I'm not sure.

Edit: I noticed the Lovasz article you cite basically makes the same points I was making above, so you may have been aware of this information. But regardless quite a bit is known about such graphs.

  • 1
    $\begingroup$ The components of $A$ are factor-critical (remove any vertex from a component, and the rest of the component has a perfect matching), which implies both that we may use any matching of $B$ into $A$ in a maximum matching of $G$, and that the components of $A$ are permissive. $\endgroup$ – Gregory J. Puleo Apr 14 '15 at 17:24
  • $\begingroup$ Thank you. Sadly, my question arose in fact from observing that graphs for which (i) part $C$ of the Gallai-Edmonds decomposition is empty and (ii) part $B$ is independent, are permissive; my question was prompted by my inability to find any more properties of such graphs. I guess I should have stated this in my question. $\endgroup$ – G Philip Apr 14 '15 at 18:16
  • $\begingroup$ Also: that any edge from $A$ to $B$ can be used in a maximum matching follows directly from the definition of a permissive graph. And as @GregoryJ.Puleo observed, since deleting any one vertex from a component $H$ of $A$ results in a subgraph $H'$ with a perfect matching, deleting an additional vertex from $H'$ gives us a subgraph $H''$ whose matching size is exactly one less than that of $H$. In particular this implies that the component $A$ is also permissive. $\endgroup$ – G Philip Apr 14 '15 at 18:17

I think your problem can be reduced to just looking at matching-covered graphs. Let $G$ be a graph and let $\mu$ be its matching number. Let $S$ be the set of all vertices covered by all maximum matchings. Let $G'$ be the larger graph obtained by adding a new independent set of size $|V(G)| - 2\mu$, adjacent to the vertices of $V(G)-S$.

If $G'$ is well-covered, then $G$ is permissive: given any $e \in E(G)$, we can extend to a perfect matching in $G'$, whose restriction to $G$ must be a matching of size $\mu$. On the other hand, if $G$ is permissive then $G'$ is well-covered: given any $e \in E(G')$, either $e \in E(G)$ in which case we can use permissiveness to extend to a maximum $G$-matching and then fix the leftover vertices with the independent set, or else $e$ joins some $v \in V(G) - S$ to the independent set, in which case we can take some maximum $G$-matching that misses $v$ and fix the leftovers (necessarily including $v$) with the independent set, using the edge $e$.

Using this trick, you can probably "transfer" results about matching-covered graphs to your context.

  • $\begingroup$ Thank you. To rephrase what you said using the terminology of the question: Let $G,\mu,S$ be as in your answer. We construct $G'$ by adding an independent set of vertices, call it $T$, of size $|V(G)|-2\mu$ to $G$ and then adding all possible edges between $T$ and $V(G)\setminus{S}$. Now $G'$ has a perfect matching: take any maximum matching of $G$, and match the leftover vertices with vertices in $T$. The fact you prove is that $G'$ is permissive if and only if $G$ is permissive. This construction is probably the reason why nobody cares about permissive graphs without perfect matchings.! $\endgroup$ – G Philip Apr 15 '15 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.