4
$\begingroup$

I'd like to use Corollary 5 of a paper by Hell & Kirkpatrick on graph packings to obtain an NP-hardness result. They want a 2-vertex-connected graph $F$ such that every matching in $F$ leaves at least 3 vertices unmatched. I would also like the graph to be $k$-regular for some $k$. I don't particularly care about the size of the graph or $k$, but smaller would be better.

Petersen's theorem implies that no such graph exists for $k =3$, but other theorems in this spirit that I've found in handbooks etc. don't seem to rule out the existence of such a graph for other $k$. I've searched through the collection of graphs from Mathematica's $\texttt{GraphData}$, but it didn't contain any examples satisfying these conditions.

Is anyone aware of reasons why such an $F$ might not exist, or else has ideas where to look for an example of one?

(I previously mentioned circulant graphs as possibilities, but they won't work because they are Hamiltonian.)

Improve this question
$\endgroup$
1
  • $\begingroup$ Have you checked if the construction given under Theorem 3.8 in www.math.illinois.edu/~dwest/pubs/matchcon.pdf helps? $\endgroup$
    – Jernej
    Commented Jan 30, 2015 at 21:32

1 Answer 1

Reset to default
4
$\begingroup$

Take an even number $r\ge 4$. Take $r$ copies of a 3-connected graph $G$ which has odd order and is regular of degree $r$. Add two new vertices $x$ and $y$. For each copy of $G$, remove one edge and join one of its former endpoints to $x$ and the other to $y$.

This gives a 2-connected $r$-regular graph whose maximum matchings miss at least $r-2$ vertices. This type of construction is pretty standard. The Edmonds–Gallai decomposition theorem tells it all.

Improve this answer
$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .