Size conditions and spectral conditions for generalized factor-critical (bicritical) graphs and $k$-$d$-critical graphs

Abstract

Let $\mbox{odd}(G)$ and $i(G)$ denote the number of nontrivial odd components and the number of isolated vertices of a graph $G$, respectively. The $k$-Berge-Tutte-formula of a graph $G$ is defined as: $\mbox{def}_k(G)=\mathop{\text{max}}\limits_{S\subseteq V(G)}\{k\cdot i(G-S)-k|S|\} $ for even $k$; $\mbox{def}_k(G)=\mathop{\mbox{max}}\limits_{S\subseteq V(G)}\{\mbox{odd}(G-S)+k\cdot i(G-S)-k|S|\} $ for odd $k$. A $k$-barrier of a graph $G$ is the subset $S\subseteq V(G)$ that reaches the maximum value in the $k$-Berge-Tutte-formula of $G$. A graph $G$ of odd order (resp. even order) is generalized factor-critical (resp. generalized bicritical) if $\varnothing$ is its only $k$-barrier. Denote by $E_G(v)$ the set of all edges incident to a vertex $v$ in $G$. A $k$-matching of a graph $G$ is a function $f:E(G)\to \{0,1,...,k\}$ such that ${\sum }_{e\in E_G(v)}f(e)$ $\le k$ for every vertex $v\in V(G)$. For $1\le d\le k$ and $d\equiv |V(G)|$(mod 2), if for any $v\in V(G)$, there exists a $k$-matching $f$ such that ${\sum }_{e\in E_G(v)}f(e)=k-d$ and ${\sum }_{e\in E_G(u)}f(e)=k\text{ for any }u\in V(G)-\{v\}$. Then $G$ is $k$-$d$-critical. In this paper, we establish tight sufficient conditions in terms of size or spectral radius respectively for a graph $G$ to be generalized factor-critical, generalized bicritical, and $k$-$d$-critical. Furthermore, we prove the equivalence of the existence of four factors (namely, $\{K_2,\{C_t:t\ge 3\}\}$-factor, $\{K_2,\{C_{2t+1}:t\ge 1\}\}$-factor, fractional perfect matching, perfect $k$-matching with even $k$) in a graph. Thus we also give size conditions and spectral radius conditions for a graph $G-v$ to have one of the four factors for any $v\in V(G)$.