|
|
||
|
IMADA - Department of Mathematics and Computer Science |
|
In this talk, we determine tight lower bound on the matching number of a graph with given maximum degree and edge-connectivity in terms of its order and size. For a graph $G$ of order $n$, size $m$, matching number $\alpha'(G)$, edge-connectivity $\lambda(G) \ge \lambda \ge 1$ and maximum degree $k \ge \lambda$ we determine best possible constants $a_{k,\lambda}$, $b_{k,\lambda}$ and $c_{k,\lambda}$ (depending only on $k$ and $\lambda$) such that $\alpha'(G) \ge a_{k,\lambda} \cdot n b_{k,\lambda} \cdot m - c_{k,\lambda}$. Further if $k$ and $\lambda$ have different parities, we determine best possible constants $d_{k,\lambda}$, $e_{k,\lambda}$ and $f_{k,\lambda}$ (depending only on $k$ and $\lambda$) such that $\alpha'(G) \ge d_{k,\lambda} \cdot m - e_{k,\lambda} \cdot n - f_{k,\lambda}$. We also show that $\alpha'(G) \ge n - \frac{1}{\lambda} m$ unless $\alpha'(G) = \frac{1}{2}(n-1)$ in which case $\alpha'(G) \ge n - \frac{1}{\lambda} m - \frac{1}{2}$. We prove that the above bounds are tight for essentially all densities of graphs. Host: Anders Yeo SDU HOME | IMADA HOME | Previous Page Daniel Merkle |