5
$\begingroup$

Assume we have bridgeless cubic graph $G(V, E)$, $n=|V|$. By Petersen's theorem, every such graph has a perfect matching. Moreover, given any edge in $G$ there exists a perfect matching containing this edge. I am interested in finding the size $|C|$ of the smallest set of vertex-disjoint edges $C$ that uniquely determines a perfect matching $M$ (i.e. $C \subset M$).

Notice that every cubic bridgeless graph G has at least $ \Omega (2^{|V(G)|/3656})$ perfect matchings.

What is the minimum number of vertex-disjoint edges $|C|$ that uniquely force any perfect matching in any bridgeless cubic graph?

Equivalently, a subset $C$ of a perfect matching $M$ is called a forcing set if $M$ is the unique perfect matching containing $C$. The forcing number of $M$ is the minimum cardinality of forcing sets of $M$. The forcing number of a cubic bridgeless graph $G(V, E)$ is the minimum number of forcing numbers of all perfect matchings of $G$. So my questions becomes:

What is the forcing number for any bridgeless cubic graph?

I guess a constant is not enough. I guess that we need at least $|C|=\Omega( n)$ and $O(\log n)$ is not enough. Is there a proof?

$\endgroup$
3
  • $\begingroup$ I can understand this question in two ways: (1) what is the minimal $k$ such that in SOME (bridgeless cubic) graph there are $k$ edges uniquely defining a matching; or (2) what is the minimal $k$ such that in ANY (bridgeless cubic) graph there are $k$ edges uniquely defining a matching. Which one are you interested in? $\endgroup$ Apr 15, 2017 at 22:34
  • $\begingroup$ @IlyaBogdanov The second one. I just edited the post. $\endgroup$ Apr 15, 2017 at 22:53
  • $\begingroup$ It may be worth noting that in the first sense (1) of @IlyaBogdanov 's comment, the number $k = 1$. An example is a circular ladder, where we modify one rung to "turn" it parallel to the ladder. (see Figure 1 arxiv.org/pdf/1012.2878.pdf) $\endgroup$ Oct 12, 2017 at 11:03

1 Answer 1

5
$\begingroup$

Take a circular ladder of odd length. Also known as the cartesian product of $C_n$ ($n$ odd) and $K_2$. For every perfect matching there are many ways to change it into a different perfect matching by replacing two edges by another two (these four edges forming a 4-cycle). I didn't work out the exact details, but it seems you can't specify one perfect matching exactly by giving less than about $\frac13 n$ edges, while there is one choice of about $\frac13 n$ edges that suffices. For even $n$, there is another type of perfect matching (not using any rungs) that can be uniquely specified by giving two edges.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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