Spectral strengthening of a theorem on transversal critical graphs

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 is an element of E(G). For any tau-critical graph G with tau(G) = t, it has been shown that vertical bar V(G)vertical bar <= 2t by Erdos and Gallai and that vertical bar E(G)vertical bar <= ((t+ 1)(2)) by Erdos, Hajnal and Moon. Most recently, it was extended by Gyarfas and Lehel to vertical bar V (G)vertical bar + vertical bar E (G)vertical bar <= ((t+2)(2)). In this paper, we prove stronger results via spectrum. Let G be a tau-critical graph with tau(G) = t and vertical bar V (G)vertical bar = n, and let lambda(1) denote the largest eigenvalue of the adjacency matrix of G. We show that n < lambda(1) <= 2t+1 with equality if and only if G is K-2 , Ks+1 boolean OR (t - s)K-2, or C2s-1 boolean OR (t - s)K-2, where 2 <= s <= t; and in particular, lambda(1) (G) <= t with equality if and only if G is Kt+1. We then apply it to show that for any nonnegative integer r, we have n (r + lambda 1/2) <= (( t+r+1)(2)) and characterize all extremal graphs. This implies a pure combinatorial result that r vertical bar V (G)vertical bar + vertical bar E (G)vertical bar <= (( t+r+1)(2)), which is stronger than Erdos-Hajnal-Moon Theorem and Gyarfas-Lehel Theorem. We also have some other generalizations. (C) 2021 Elsevier B.V. All rights reserved.