Question: Let M be the set of maximum matchings of G=(V, E). Find a minimum edge subset R, such that, the intersection of R and M is not empty for each M in M.

Have I understand your question well?

I think this is a good question. Could you send me some background materials?

Let r and m be the cardinalities of R and M respectively. Let M(e) be the set of maximum matchings containing edge e. 

For a complete graph K_n, the question is not hard. For example, r(K_2n) = 2n-1.

Proof. Firstly note that, by symmetry, each edge meets equal number of M's in M. Since K_2n has perfect matchings, each M in M saturates vertex v. Let e_1 ...  e_(2n-1) be all the edges incident with v. It is easily seen that, { M(e_1), ..., M(e_(2n-1) } is a partition of M. Thus, R={e_1 ...  e_(2n-1)} is an edge dominating set. Why R is minimum? Recall that, each edge meets equal number of M's in M.

For K_(2n+1), the question is a little harder, but I think it can be solved by counting its maximum matchings (near-perfect).

Question: Let M be the set of maximum matchings of G=(V, E). Find a minimum edge subset R, such that, the intersection of R and M is not empty for each M in M.

Have I understand your question well?

I think this is a good question. Could you send me some background materials?

Let r and m be the cardinalities of R and M respectively. Let M(e) be the set of maximum matchings containing edge e. 

For a complete graph K_n, the question is not hard. For example, r(K_2n) = 2n-1.

Proof. Firstly note that, by symmetry, each edge meets equal number of M's in M. Since K_2n has perfect matchings, each M in M saturates vertex v. Let e_1 ...  e_(2n-1) be all the edges incident with v. It is easily seen that, { M(e_1), ..., M(e_(2n-1) } is a partition of M. Thus, R={e_1 ...  e_(2n-1)} is an edge dominating set. Why R is minimum? Recall that, each edge meets equal number of M's in M.

For K_(2n+1), the question is a little harder, but I think it can be solved by counting its maximum matchings (near-perfect).

Peter Breuer, your dominating set is minimal by inclusion but not by size. For example, in the case of K5, your construction gives 7 edges while the edge set of any subgraph K4 is dominating and contains 6 edges (which is the minimum). However, it is easy to prove that if p=2k+1 then any dominating subset R contains at least 3k = 3(p-1)/2 edges. Indeed, it is known that the edge set of Kp can be partitioned to k Hamiltonian cycles. For each cycle H, we need to take at least 3 of its edges to R, otherwise their exists a maximum matching of Kp formed by the edges of H\R.

At the first glance, the problem is interesting and easy. r(K_2n) = 2n-1 can be obtained in one minute. However, I spent 2 days to work out r(K_(2n+1)) = 4n-1 (n is not 2)!

Anyway, I promised, I do. Hope my work means something. Attached pls find my full manuscript (Word file).

To work out the case of K_(2n+1), the main tool I used is the Gallai-Edmonds Structure Theorem from matching theory.

The manuscript is a little long and it needs enough patience to read, because I not only want to present the solution to the problem, but also want to record my thinking route. Besides, the bypasses in the manuscript may also be useful for further study.

Now, what I care is the background of the problem. If the problem has not a solid background, I think it is not worthy of further study. You see, for Kp, the edges in a minimum dominating edge set are (almost) in a "cluster". Actually, it can be showed that, there are few independent edges in a minimum dominating edge set.

In one word, if the problem will not have any application, forget it, and don't waste time to read my manuscript. So, could Mr. Anwar Alwardi provide some relational materials?

Thanks Mr. Peter Breuer and Mr. Aleksey Nikolaevich Glebov!

Wenshui Lin ([email protected])