Signed spectral Turań-type theorems (Q2685382)

This paper on signed graphs investigates a few conjectures and provides answers to certain outstanding problems. A signed graph \(\Sigma = (G, \sigma)\) is a graph where the function \(\sigma\) assigns either \(1\) or \(-1\) to each edge of the simple graph \(G\). The adjacency matrix of \(\Sigma\), denoted by \(A(\Sigma)\), is defined canonically. This paper is divided into \(5\) sections. The first section named `Introduction' gives basic definitions and statements of important theorems related to the topic such as the Motzkin and Straus Theorems, Nikiforov's proof for the conjecture by Edwards and Elphick, Cvetković's Theorem extended by Wang et al, etc. In section \(2\) on `Preliminaries', the needed matrix theoretic preliminaries about doubly stochastic matrices, where a non-negative square matrix is doubly stochastic if the sum of the entries in every row and every column is 1, are explained. In a recent paper, \textit{W. Wang} et al. [Linear Algebra Appl. 619, 137--145 (2021; Zbl 1466.05125)] extended the spectral bounds of Hoffman and Cvetković for the chromatic number of signed graphs. They proposed an open problem related to the balanced clique number and the largest eigenvalue of a signed graph. Giving proof for a strengthened version of this open problem for the signed graph is one of the primary goals of this paper. Moreover, the authors extend Turán's inequality for the signed graphs in terms of the balanced clique number and frustration index. Again, they give an alternate proof for Cvetković's Theorem, which was extended by Wang et al too [loc. cit.]. As a byproduct, it gives alternate proofs for some of the known classical bounds for the least eigenvalues of unsigned graphs such as the spectral lower bound for the edge bipartiteness of a simple graph, and deduces the upper bounds for the least eigenvalues of unsigned graphs obtained by \textit{G. Constantine} [ibid. 65, 171--178 (1985; Zbl 0584.15009)]. The edge bipartiteness of an unsigned graph G is the least number of edges whose deletion yields a bipartite graph. These results are given in section \(3\) on `Eigenvalues and Balanced Clique Number'. Though \textit{H. Lin} et al. [Comb. Probab. Comput. 30, No. 2, 258--270 (2020; Zbl 1466.05121)] confirmed a conjecture of \textit{B. Bollobás} and \textit{V. Nikiforov} [J. Comb. Theory, Ser. B 97, No. 5, 859--865 (2007; Zbl 1124.05058)] for the triangle-free graphs recently, this paper demonstrates that even for triangle-free graphs, the signed graph form of this claim need not be true. For the triangle-free graphs whose greatest eigenvalue is the spectral radius, the authors demonstrate the signed analogue of this proposition. Section \(4\) on `Bollobás and Nikiforov's Conjecture: Signed Version' deals with these concepts in detail. Section \(5\) on `Signed Walks and Largest Eigenvalue' discusses some of the relationships between the number of signed walks and the largest eigenvalue of a signed graph. Wang et al. [loc. cit.] proved the Wilf's theorem and the Motzkin-Strauss theorem for signed graphs and a theorem for signed graphs is cited as an open problem in the same work. This paper proves a stronger version of this open problem as: Let \(\Sigma = (G, \sigma)\) be a signed graph with \(m\) edges. If \(\lambda_1(\Sigma)\) is the largest eigenvalue of the adjacency matrix \(A(\Sigma)\), then \(\lambda_1^2(\Sigma) \le 2 (m-\epsilon(\Sigma)) (1- \frac{1}{\omega_b(\Sigma)}) \) where \(\omega_b(\Sigma)\) and \(\epsilon(\Sigma)\) are the balanced clique number and frustration index of \(\Sigma\), respectively. The result stated next is presented by \textit{O. Favaron} et al. [Discrete Math. 111, No. 1--3, 197--220 (1993; Zbl 0785.05065)]. But, here, in this paper, the outcome was stated differently with the bound is rewritten in terms of edge bipartiteness. The result is: Let \(G\) be a graph with \(n\) vertices and \(m\) edges. Let \(A(G)\) be its adjacency matrix and \(\omega(G)\) be its clique number. Let \(\epsilon_b(G)\) denote the edge bipartiteness of the graph \(G\). Let \(\lambda_n(G)\) be the least eigenvalue of \(A(G)\). Then \(\lambda_n^2(G) \le m -\epsilon_b(G)\). The classical Turán inequality for the unsigned graphs is given as: Let \(G\) be a graph on \(n\) vertices and \(m\) edges with clique number \(\omega\). Then, \(m \le \frac{n^2}{2}(1- \frac{1}{\omega(\Sigma)})\). The authors extended Turán's inequality for the signed graphs in terms of the balanced clique number and frustration index as: Let \(\Sigma = (G, \sigma)\) be a signed graph with \(n\) vertices, \(m\) edges, balanced clique number \(\omega_b(\Sigma)\) and the frustration index \(\epsilon(\Sigma)\). Then \(m \le \epsilon(\Sigma) + \frac{n^2}{2}(1- \frac{1}{\omega_b(\Sigma)})\). In the following theorem, though Nikiforov's bound for the signed graphs is extended, the proof pattern is that of Nikiforov: Let \(\Sigma = (G, \sigma)\) be a signed graph with \(n\) vertices, \(m\) edges, balanced clique number \(\omega_b(\Sigma)\) and frustration index \(\epsilon(\Sigma)\). Then \(\lambda_1(\Sigma) \le \sqrt{2(m- \epsilon(\Sigma))(1- \lfloor \frac{1}{2}+\sqrt{2(m- \epsilon(\Sigma))+\frac{1}{4} \rfloor^{-1}})} \) where \(\lambda_1(\Sigma) \) is the largest eigenvalue of \(A(\Sigma)\). Thus, the next result of Stanić is obtained as a corollary of the above theorem: Let \(\Sigma = (G, \sigma)\) be a signed graph with \(n\) vertices, \(m\) edges and frustration index \(\epsilon(\Sigma)\). Then \(\lambda_1(\Sigma) \le \sqrt{2(m- \epsilon(\Sigma))+ \frac{1}{4}} - \frac{1}{2}\), where \(\lambda_1(\Sigma)\) is the largest eigenvalue of \(A(\Sigma)\). Bollobás and Nikiforov proposed the following conjecture: If \(G\) is a \(K_{r+1}\)-free graph of order at least \(r+ 1 \) with \(m\) edges, and \(\lambda_1 \ge \lambda_2 \ge \ldots \ge \lambda_n\) are the eigenvalues of \(A(G)\), then \(\lambda_1^2 + \lambda_2^2 \le \frac{r-1}{r}2m\). Recently Lin et al. confirmed this conjecture for the triangle-free graphs as: Let \(G\) be a triangle-free graph on \(n\) vertices and \(m\) edges with \(n\ge 3\). Then \(\lambda_1^2 + \lambda_2^2 \le m\). The authors proved that this theorem, as well as the conjecture of Bollobás and Nikiforov, need not be true for signed graphs by an example where signed graph \(\Sigma = (C_5, \sigma)\) with \(\sigma\) assigns \(-1\) to the edge between the vertices \(v_1\) and \(v_2\), and \(1\) to the remaining edges. They have proved the following result for the signed graph. Let \(\Sigma\) be a signed graph with \(n\) vertices and \(m\) edges with \(n \ge 3\), and \(\Sigma\) has no balanced triangles. If \(\lambda_1(\Sigma) \ge \lambda_2(\Sigma) \ge \ldots \ge \lambda_n(\Sigma)\) are the eigenvalues of \(A(\Sigma)\) and \(\lambda_1(\Sigma) \ge |\lambda_n(\Sigma)|\), then \(\lambda_1^2(\Sigma) + \lambda_2^2(\Sigma) \le m\). In the following theorem, the authors give a different bound for the largest eigenvalue of a signed graph in terms of the total number of triangles present in the signed graph whenever the number of positive triangles is greater than the number of negative triangles in the signed graph. The theorem is as follows: Let \(\Sigma\) be a signed graph with \(n\) vertices and \(m\) edges with \(n \ge 3\). Let \(\lambda_1(\Sigma)\) be the largest eigenvalue of \(A(\Sigma)\). If \(t_s(\Sigma)\ge 0\), then \(\lambda_1^2(\Sigma) \le m+ (6t_s(\Sigma))^{\frac{2}{3}}\). This paper deals with many concepts related to signed graphs: finding solutions to certain conjectures and open problems, extending a few graph theoretic results to signed graphs, rectifying and adding certain results to signed graphs, and so on. This paper widens the horizon of signed graphs to enthusiastic scholars.