Spectral strengthening of a theorem on transversal critical graphs

Abstract

A transversal set of a graph $G$ is a set of vertices incident to all edges of $G$. The transversal number of $G$, denoted by $\tau (G)$, is the minimum cardinality of a transversal set of $G$. A simple graph $G$ with no isolated vertex is called $\tau$-critical if $\tau (G-e)<\tau (G)$ for every edge $e\in E(G)$. For any $\tau$-critical graph $G$ with $\tau (G)=t$, it has been shown that $|V(G)|\le 2t$ by Erdős and Gallai and that $|E(G)|\le \left(\genfrac{}{}{0ex}{}{t+1}{2}\right)$ by Erdős, Hajnal and Moon. Most recently, it was extended by Gyárfás and Lehel to $|V(G)|+|E(G)|\le \left(\genfrac{}{}{0ex}{}{t+2}{2}\right)$. In this paper, we prove stronger results via spectrum. Let $G$ be a $\tau$-critical graph with $\tau (G)=t$ and $|V(G)|=n$, and let ${\lambda }_1$ denote the largest eigenvalue of the adjacency matrix of $G$. We show that $n+{\lambda }_1\le 2t+1$ with equality if and only if $G$ is $t{K}_2$, $K_{s+1}\cup (t-s)K_2$, or $C_{2s-1}\cup (t-s)K_2$, where $2\le s\le t$; and in particular, ${\lambda }_1(G)\le t$ with equality if and only if $G$ is $K_{t+1}$. We then apply it to show that for any nonnegative integer $r$, we have $n\left(r+\frac{{\lambda }_1}{2}\right)\le \left(\genfrac{}{}{0ex}{}{t+r+1}{2}\right)$ and characterize all extremal graphs. This implies a pure combinatorial result that $r|V(G)|+|E(G)|\le \left(\genfrac{}{}{0ex}{}{t+r+1}{2}\right)$, which is stronger than Erdős-Hajnal-Moon Theorem and Gyárfás-Lehel Theorem. We also have some other generalizations.