A unified combinatorial view beyond some spectral properties

Let $β>0$. Motivated by jumbled graphs defined by Thomason, the celebrated expander mixing lemma and Haemers's vertex separation inequality, we define that a graph $G$ with $n$ vertices is a weakly $(n,β)$-graph if $\frac{|X| |Y|}{(n-|X|)(n-|Y|)} \le β^2$ holds for every pair of disjoint proper subsets $X, Y$ of $V(G)$ with no edge between $X$ and $Y$, and it is an $(n,β)$-graph if in addition $X$ and $Y$ are not necessarily disjoint. Our main results include the following. (i) For any weakly $(n,β)$-graph $G$, the matching number $α'(G)\ge \min\left\{\frac{1-β}{1+β},\, \frac{1}{2}\right\}\cdot (n-1).$ If in addition $G$ is a $(U, W)$-bipartite graph with $|W|\ge t|U|$ where $t\ge 1$, then $α'(G)\ge \min\{t(1-2β^2),1\}\cdot |U|$. (ii) For any $(n,β)$-graph $G$, $α'(G)\ge \min\left\{\frac{2-β}{2(1+β)},\, \frac{1}{2}\right\}\cdot (n-1).$ If in addition $G$ is a $(U, W)$-bipartite graph with $|W|\ge |U|$ and no isolated vertices, then $α'(G)\ge \min\{1/β^{2},1\}\cdot |U|$. (iii) If $G$ is a weakly $(n,β)$-graph for $0<β\le 1/3$ or an $(n,β)$-graph for $0<β\le 1/2$, then $G$ has a fractional perfect matching. In addition, $G$ has a perfect matching when $n$ is even and $G$ is factor-critical when $n$ is odd. (iv) For any connected $(n,β)$-graph $G$, the toughness $t(G)\ge \frac{1-β}β$. For any connected weakly $(n,β)$-graph $G$, $t(G)> \frac{5(1-β)}{11β}$ and if $n$ is large enough, then $t(G) >\left(\frac{1}{2}-\varepsilon\right)\frac{1-β}β$ for any $\varepsilon >0$.

No reviews yet.

No comments yet.