1
$\begingroup$

if we have a graph $G = (V,E)$ and the four values $\beta_1(G)$, $\alpha_1(G)$, $\beta(G)$, $\alpha(G)$, where

$\beta_1(G)$: Edge independence number. The maximal number of independent edges in the graph. $\alpha_1(G)$: Vertex independence number. The maximal number of independent vertices in the graph. $\beta(G)$: Edge covering number. The minimal number of edges that cover all the vertices in the graph $\alpha(G)$: Vertex covering number. The minimal number of vertices that cover all the edges in the graph.

If $\alpha(G) \le \beta_1(G)$ is is necessarily true that we have maximal matching?

I tried with some graphs and I found it true! For exampleexample

$\endgroup$
  • $\begingroup$ Hi Lama, I fixed the formatting of your question. This is a short overview how to use MathJax here on MSE. $\endgroup$ – Stefan Mesken Jul 5 '15 at 12:49
0
$\begingroup$

Hint:

  • Let $M$ be the matching, and $C$ be the cover.
  • Observe that no two edges $e_1,e_2 \in M$ share a vertex, hence $\alpha(G) \geq \beta_1(G)$. In particular each edge $e \in M$ has exactly one of its vertices inside $C$.
  • Suppose there is an augmenting path $P$, which vertices cover the unmatched edges $e \in P \setminus M$ on that path?
  • How many covering vertices of $C$ do you need to cover all the vertices of $P$ and how many you can actually use?

I hope this helps $\ddot\smile$

$\endgroup$

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.