1
$\begingroup$

The matching number $\alpha'(G)$ of graph $G$, sometimes known as the edge independence number, is the size of a maximum independent edge set

This question was prompted by this post.

Misha Lavrov have proved that the matching number of every $3$-regular graph with $n$ vertices is at least $\frac{7}{16}n$.

So my question is, is it possible to construct a class of $n$-order $3$-regular graphs such that the matching number is exactly equal to $\frac{7}{16}n$.

Note that $\frac{7}{16}n<\frac{n}{2}$. So by Petersen theorem we know that $G$ has a cut edge. I have noticed that the graph below satisfies the condition, but is it possible to construct more? Can infinite number be constructed?

![enter image description here

In the above 3-regular graph(with 16 vertices), $\alpha'(G)=7=\frac{7}{16}\times 16$.

$\endgroup$
3
  • 3
    $\begingroup$ There is a trivial example of disjoint copies of your example. One thing to try might be to make a 32 node graph from two of this one, and then see if you can swap some edges to connect them while keeping $\alpha'$ constant $\endgroup$
    – Alex K
    Commented Feb 5, 2023 at 17:45
  • $\begingroup$ @AlexK Yes, in the connected case your method might work. $\endgroup$
    – licheng
    Commented Feb 6, 2023 at 2:49
  • $\begingroup$ @AlexK We cannot keep α′ constant when the graph with $32$ vertices is connected. See my answer, $\endgroup$
    – licheng
    Commented Feb 6, 2023 at 9:48

1 Answer 1

0
$\begingroup$

Firstly, many thanks to Alex K. I have consulted a literature and found that when a $3$-regular graph is connected, this bound can be improved to $\frac{4n-1}{9}$. And the bound is tight.

  • [1] Biedl, T., Demaine, E.D., Duncan, C.A., Fleischer, R., Kobourov, S.G.: Tight bounds on maximal and maximum matchings. Discrete Math. 285, 7–15 (2004)

Theorem 13. [1] Any 3-regular connected graph of order $n$ has a matching of size $\frac{4 n-1}{9}$.

Note that $\frac{4 n-1}{9}-\frac{7}{16}n=\frac{n}{144}-\frac{1}{9}$. A $36$-order 3-regular connected graph has a maximum matching with size at least $15$.

Proof. Let $G$ be a 3-regular graph of order $n$. By Theorem 11 and Lemma $12, G$ has a matching of size $$ \frac{3 n-2 \ell_2}{6} \geqslant \frac{3 n-\frac{n+2}{3}}{6}=\frac{8 n-2}{18}=\frac{4 n-1}{9} . $$

Theorem 11. Any 3-regular graph $G$ of order $n$ has a matching of size $\frac{3 n-2 \ell_2}{6}$, where $\ell_2$ is the number of leaves in the 2-block tree of $G$.

Lemma 12. The 2-block tree of any 3-regular graph of order $n$ has at most $\frac{n+2}{6}$ leaves.

The bound in Theorem 13 is tight, which can be seen by attaching the smallest possible 3-regular graph to every leaf of the graph as follows.

enter image description here

The resulting graph, shown in the following picture, is defined for $n \equiv 16$ mod 18. There are $\frac{n-7}{9}$ black vertices, inducing $\frac{4 n-10}{18}$ odd components. Hence, any matching has at least $\frac{4 n-10}{18}-\frac{n-7}{9}=\frac{n+2}{9}$ unmatched vertices and therefore at most $\frac{8 n-2}{9}$ matched vertices.

enter image description here

$\endgroup$

You must log in to answer this question.

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