This paper investigates the Turan-like problem for \(\mathcal{K}^-_{r + 1}\)-free \((r \geq 2)\) unbalanced signed graphs, where \(\mathcal{K}^-_{r + 1}\) is the set of unbalanced signed complete graphs with \(r+1\) vertices. The maximum number of edges and the maximum index for \(\mathcal{K}^-_{r + 1}\)-free unbalanced signed graphs are given. Moreover, the extremal \(\mathcal{K}^-_{r + 1}\)-free unbalanced signed graphs with the maximum index are characterized.
In this paper, write \(\dot{G} = (G, \sigma)\) for a signed graph with underlying graph \(G\) and sign function \(\sigma\) on the edge set of \(G\). Denote by \(V(\dot{G})\), \(E(\dot{G})\), \(e(\dot{G})\), and \(e^-(\dot{G})\) the vertex set, the edge set, the number of edges, and the number of negative edges of \(\dot{G}\), respectively. If two vertices \(u,v \in V(\dot{G})\) are joined by an edge, let the quantity \(a_{uv}\) be \(1\) or \(-1\) depending on whether \(uv\) is a positive or a negative edge. The \(n \times n\) adjacency matrix \(A\) \(( = A(\dot{G}) )\) of \(\dot{G}\) is then defined by \(A = (a_{uv})\). The eigenvalues of \(\dot{G}\) is that of \(A(\dot{G})\), which are denoted by \(\lambda_{1}(\dot{G}) \geq \lambda_{2}(\dot{G}) \geq \cdots \geq \lambda_{n}(\dot{G})\). In particular, the largest eigenvalue of \(\dot{G}\) is called the index. The spectral radius of \(\dot{G}\) is the largest absolute value of the eigenvalues of \(\dot{G}\), denoted by \(\rho(\dot{G})\). These two coincide when the absolute values of the eigenvalues of \(\dot{G}\) do not exceed its index.
This paper aims to investigate the Turán-like problem for \(\mathcal{K}_{r+1}^-\)-free \((r \geq 2)\) unbalanced signed graphs, where \(\mathcal{K}_{r+1}^-\) is the set of all the \(r+1\)-vertex unbalanced signed complete graphs. Before presenting new theorems, we provide an introductory discussion.
Given a graph \(F\), a graph \(G\) is called \(F\)-free, if it contains no \(F\) as a subgraph. A prime problem of extremal graph theory is to determine the maximum number of edges in an \(n\)-vertex \(F\)-free graph, known as Turán problem. Early in 1907, Mantel [10] proved that if \(G\) is an \(n\)-vertex triangle-free graph, then \(e(G)\leq \lfloor {n^2}/{4} \rfloor\), with equality holding if and only if \(G = K_{\lfloor \frac{n}{2} \rfloor, \lceil \frac{n}{2} \rceil}\), that is, \(G\) is an \(n\)-vertex complete bipartite graph with two almost equally size partitions. The study of extremal graph theory as a subject in its own right was formally initiated by Turán in 1940. Let \(r \geq 2\) be an integer and \(K_{r + 1}\) be a complete graph on \(r+1\) vertices. In his seminal papers [14,15], the maximum number of edges of a \(K_{r + 1}\)-free graph was determined, and the unique extremal graph was also characterized. Turán’s graph, denoted by \(T_r(n)\), is the complete \(r\)-partite graph on \(n\) vertices which is the result of partitioning \(n\) vertices into \(r\) almost equally sized partitions \((\lfloor n/r \rfloor , \lceil n/r \rceil)\) and taking all edges connecting two different partition classes (note that if \(n \leq r\) then \(T_r(n) = K_n\)). Denote the number of edges in Turán’s graph by \(t_r(n) = e(T_r(n))\). Using these notations, Turán’s Theorem can be stated as follows.
Turán’s Theorem is a fundamental theorem in extremal graph theory, providing insights into the structure of extremal graphs. In addition to Turán’s Theorem, extremal graph theory also encompasses many other important results and problems, such as the shortest path problems [1], graph decomposition problems [8], and so on. Research into these problems not only helps in understanding the relationship between the global and local structures of graphs, but also plays a crucial role in solving combinatorial optimization problems, network design, and information transmission. The readers can refer to [3] for a comprehensive overview.
In the past two decades, the spectral version of Turán problem is paid much attention by many researchers. Below we only mention the result raised by Nikiforov in 2007[11], which will be used for study later in this article. The readers can refer to an outstanding paper [9] to understand the current research status of such problems.
Note that Turán’s graph is both the extremal graph of number of edges and of spectral radius. Actually, the Turán problem and the spectral Turán problem are closely related. See [12] for more discussions on this topic. Different from aforementioned studies, we focus on signed graphs, and ask what are the maximum number of edges and the maximum spectral radius of an \(\mathcal{F}\)-free signed graph of order \(n\), where \(\mathcal{F}\) is a set of signed graphs. That problem were initially proposed by Wang, Hou, and Li in their recent research [16], in which they referred to such problem as the Turán-like problem in the context of signed graphs.
Denote by \(\mathcal{K}_{r+1}^-\) \((r \geq 2)\) the set of all unbalanced signed complete graphs on \(r+1\) vertices. Let \(\dot{G}^{y_1, \cdots, y_r}\) be a \(\mathcal{K}_{r+1}^-\)-free unbalanced signed graph obtained from a signed clique \(K_r^-\) on vertex set \(X = \{v_1, \cdots, v_r \}\) with one negative edge \(v_1v_2\) and an all-positive clique \(K_{n – r }\) on vertex set \(Y = \{v_{r+1}, \cdots, v_{n}\}\) by adding positive edges between each vertex of \(Y\) and all but one vertex of \(X\). The superscript \(y_i\) \((1 \leq i \leq r)\) denotes the number of vertices not adjacent to \(v_i\). It is obvious that the number of vertices in \(Y\) not adjacent to \(v_i\) \((3 \leq i \leq r)\) is not greater than \(r – 2\), that is, \(y_3 + \cdots + y_r \leq r – 2.\) In addition, \(y_1 + \cdots + y_n = n – r.\) Note that, due to the unbalance, if \(r = 2\), then \(y_1, y_2 \geq 1\), and if \(r \geq 3\), then \(y_1, \cdots, y_r \geq 0.\) Here we draw the signed graphs when \(r=2, 3\) to illustrate this structure, as shown in Fig. 1, noting that thin solid lines (resp., thin dashed lines) represent positive edges (resp., negative edges), thick solid lines between two vertex sets represent the connection of all possible positive edges, and the solid circle represents all-positive clique.
An important feature of signed graphs is the concept of switching the signature. For a signed graph \(\dot{G}\) and \(U \subset V(\dot{G})\), the operation that changes the signs of all edges between \(U\) and \(V(\dot{G}) \setminus U\) is called a switching operation. We say that the signed graphs \(\dot{G}\) and \(\widetilde{\dot{G}}\) obtained by a switching operation from \(\dot{G}\) is switching equivalent. It is important to observe that switching equivalent signed graphs have similar adjacency matrices and so have the same eigenvalues (see [22]).
Now we present some interesting results about the Turán-like problem.
In this context, for some special \(\mathcal{F}\), we reframe the Turán-like problem in signed graphs to connect it with the spectral Turán problem. Let \(\mathcal{K}^+_{r+1}\) \((r \geq 2)\) be the set of balanced signed complete graphs on \(r+1\) vertices. Note that, if \(\mathcal{F} = \mathcal{K}^+_{r+1}\), then the all-negative signed complete graph is the unique (up to switching equivalence) \(\mathcal{F}\)-free unbalanced signed graph attaining the maximum spectral radius (see [5, Theorem 3.1]). This is the trivial case. Thus, we only detect among \(\mathcal{K}^+_{r+1}\)-free balanced signed graphs those having the maximum spectral radius. Moreover, balanced signed graphs are switching equivalent to all-positive signed graphs. We can only look for the desired signed graphs in all-positive signed graphs and this problem becomes the spectral Turán problem for \(K_{r+1}\)-free graphs, when considering the spectral radius.
Recently, several researches have explored related issues (see [7,20,19,17]), and here we recall several results that will be helpful for study later. Chen and Yuan, in [7], investigated the Turán-like problem for \(\mathcal{K}_4^-\)-free signed graphs, and their results are as follows:
Now we are in a position to present our results. The following theorem concerns the maximum of the number of edges.
Below we show that the \(\mathcal{K}^-_{r + 1}\)-free unbalanced signed graph with maximum index is switching equivalent to \(\dot{G}^{n – r, 0, \cdots, 0}\).
The proposition below adds some numerical estimates to Theorem 1.10.
In particular, \(\lambda_{1}(\dot{G}^{n – r, 0, \cdots, 0}) = n – 2\) if and only if \(r = 3\).
The remainder of this article is organized as follows: in Section 2, we present some fundamental properties and conclusions that will be used in the sequel. In Section 3 , we provide the proofs of Theorems 1.9,1.10 and Proposition 1.11. In the concluding remarks, we analyze our results and provide some comments.
In this section we introduce some results which will be useful in the sequel. The lemma below concerns equitable partitions. Consider a partition \(P = \{V_1, \cdots, V_m\}\) of the set \(V = \{1, \cdots, n\}.\) The characteristic matrix \(\chi_P\) of \(P\) is the \(n \times m\) matrix whose columns are the characteristic vectors of \(V_1, \cdots, V_m.\) Consider a symmetric matrix \(M\) of order \(n\), with rows and columns are partitioned according to \(P\). The partition of \(M\) is equitable if each submatrix \(M_{i,j}\) formed by the rows of \(V_i\) and the columns of \(V_j\) has constant row sums \(q_{i,j}\). The \(m \times m\) matrix \(Q = (q_{i,j} )_{1 \leq i,j \leq m}\) is called the quotient matrix of \(M\) with respect to the equitable partition \(P\).
(i) The eigenvectors in the column space of \(\chi_P\); the corresponding eigenvalues coincide with the eigenvalues of \(Q\),
(ii) The eigenvectors orthogonal to the columns of \(\chi_P\); the corresponding eigenvalues of \(M\) remain unchanged if some scalar multiple of the all-one block \(J\) is added to block \(M_{i,j}\) for each \(i, j \in \{1, \cdots, m\}.\)
Next we present a celebrated result of signed graphs, which is an important method for determining the switching equivalence of two signed graphs with the same underlying graph.
The balanced clique number of a signed graph \(\dot{G}\), denoted by \(\omega_b(\dot{G})\), is the maximum order of a balanced clique in \(\dot{G}\). The following lemma gives an upper bound on the index of a signed graph in terms of its order and balanced clique number.
We end this section by following lemma which says that the index of a signed graph is not greater than that of its underlying graph.
This section is devoted to the proofs of Theorems 1.9, 1.10, and Proposition 1.11. For notations and concepts of signed graphs undefined here, we refer the reader to [21]. For introductory material on the matrix theory of signed graphs see the survey of Zaslavsky [22] and its references. In particular, let \(\dot{G}\) be a signed graph, and \(X\) and \(Y\) be disjoint sets of vertices of \(\dot{G}\). We write:
– \(V(\dot{G}) = \{v_1, \cdots, v_n\}\) for the set of vertices of \(\dot{G}\);
– \(\dot{G}[X]\) for the signed graph induced by \(X\), and \(e(X)\) for \(e(\dot{G}[X])\);
– \(e(X,Y)\) for the number of edges joining vertices in \(X\) to vertices in \(Y\);
– \(N_{\dot{G}}(v)\) for the set of neighbors of a vertex \(v\) in \(\dot{G}\), and \(d_{\dot{G}}(v)\) for \(|N_{\dot{G}}(v)|\);
– \(u \stackrel{+}{\sim} v\), \(u \stackrel{-}{\sim} v\), and \(u \not \sim v\) for that \(u\) is adjacent to \(v\) by a positive edge, a negative edge, and non-edge, respectively;
– \(\dot{G}^\prime \sim \dot{G}\) for that \(\dot{G}^\prime\) is switching equivalent to \(\dot{G}\).
Proof of Theorem 1.9. From Theorem 1.3, we know that our assertion holds for \(r = 2\). We will prove our result by induction on \(r\). Assume that the assertion is true for all \(r \leq t – 1\) \((2 \leq t – 1 \leq n – 2)\), and we prove it for \(t\). Let \(\dot{G}\) be a \(\mathcal{K}_{t+1}^-\)-free unbalanced signed graph with maximum possible number of edges. Note that \(\dot{G}^{y_1, \cdots, y_t}\) is \(\mathcal{K}_{t+1}^-\)-free, and so \(e(\dot{G}) \geq e(\dot{G}^{y_1, \cdots, y_t}).\)
First we claim that \(\dot{G}\) contains an unbalanced signed clique of order \(t\). Otherwise, by induction hypothesis we know \[e(\dot{G}) \leq \frac{n(n-1)}{2} – (n – t + 1) < e(\dot{G}^{y_1, \cdots, y_t}),\] a contradiction.
Let \(X\) be the vertex set of an unbalanced signed complete graph with order \(t\) and let \(Y\) be its complement. Since each vertex in \(Y\) can have at most \(t – 1\) neighbours in \(X\), the number of edges between \(X\) and \(Y\) is at most \((t – 1)(n – t)\). We see that \[e (\dot{G}) = e(X) + e(Y) + e(X,Y) \leq \tbinom{t}{2} + \tbinom{n – t}{2} + (t – 1)(n – t) = \frac{n(n – 1)}{2} – (n – t).\]
If \(e^-(\dot{G}) = 1\), then the equality holds if and only if the unbalanced \(t\)-vertex clique contains the negative edge, \(\dot{G}[Y]\) is an all-positive clique, each vertex of \(Y\) is adjacent to \(t – 1\) vertices of \(X\) by positive edges, and the number of vertices adjacent to both \(v_1\) and \(v_2\) is not great than \(t – 2\).
Thus, we have proven that the conclusion holds when \(r = t\). Based on the induction hypothesis, we complete the proof of Theorem 1.9. ◻
The approach for proving Theorem 1.9 is inspired by the proof of Turán’s Theorem, with the key difference being that we use induction on \(r\) here, whereas his proof employs induction on \(n\).
Proof of Proposition 1.11. We give a
vertex partition as \(V_1 = \{v_1 \}\),
\(V_2 = \{v_2\}\), \(V_{3} = \{v_3, \cdots, v_r\}\), and \(V_4 = \{v_{r+1}, \cdots, v_n\}\). Then the
adjacency matrix of \(\dot{G}^{n – r, 0,
\cdots, 0}\) and its quotient matrix
The eigenvalues of matrix \(A^+\) except the eigenvalues of \(Q_1^+\) are \(-1\) with multiplicity \(n-4\). Then the eigenvalues of \(\dot{G}^{n – r, 0, \cdots, 0}\) are the eigenvalues of \(Q_1\) and \(-1\) with multiplicity \(n-4\). Therefore, \(\lambda_{1}(\dot{G}^{n – r, 0, \cdots, 0}) = \lambda_1(Q_1)\). By direct calculation, the characteristic polynomial of the matrix \(Q_1\) is \[g(x) = (x+1) (x^3 + (3-n)x^2 + (3-n-r)x + (n + 4)r – (r^2 + n + 7)) = (x+1)f(x).\]
Thus \(\lambda_{1}(\dot{G}^{n – r, 0, \cdots, 0})\) is the largest root of \(f(x) = x^3 + (3-n)x^2 + (3-n-r)x + (n + 4)r – (r^2 + n + 7)\). By simple calculations \(f(n-2) = – (r – 3)^2 \leq 0\), and so the equality holds if and only if \(r = 3\). So we have \(\lambda_{1}(\dot{G}^{n – r, 0, \cdots, 0}) \geq n-2\), and \(\lambda_{1}(\dot{G}^{n – r, 0, \cdots, 0})<n-1\) from Lemma 2.4. ◻
To simplify the proof of Theorem 1.10, we shall prove several auxiliary results. First, note that according to Perron-Frobenius theory, there exists a strictly positive eigenvector corresponding to the index of a simple connected graph \(G\). Furthermore, if we add some edges in \(G\), the index of the resulting graph is larger than that of \(G\). These are incorrect for signed graphs, but we have following results.
Let \(x = (x_1, x_2, \cdots, x_n)^{'}\) be an eigenvector corresponding to the index \(\lambda_{1}(\dot{G})\) of a signed graph \(\dot{G}\). The entry \(x_i\) corresponds to the vertex \(v_i\) of \(\dot{G}\). So the eigenvalue equation for \(v_i\) reads as follows \[\begin{aligned} \lambda_{1}(\dot{G})x_{i} = & \sum_{v_j \in N_{\dot{G}}(v_i)} \sigma(v_iv_j)x_j. \end{aligned}\] The following proposition presents a crucial method investigating the maximum index in signed graphs, which can be proven based on [13, Theorem 3] or [2, Proposition 2.1]. For the sake of completeness, we provide a detailed proof here.
(i) Adding some positive edges,
(ii) Removing some negative edges,
(iii) Reversing the signs of some negative edges, resulting in a new signed graph \(\dot{G} ^ \prime\), then \(\lambda_{1}(\dot{G}^\prime) \geq \lambda_{1}(\dot{G})\). The equality holds if and only if the entries of \(x\) corresponding to the endpoints of these edges are all zeros.
And if we perform one of the following perturbations in \(\dot{G}\):
(iv) Rotating the positive edge \(v_iv_j\) to the non-edge position \(v_iv_k\), where \(x_j \leq x_k\),
(v) Reversing the sign of the positive edge \(v_iv_j\) and the negative edge \(v_iv_k\), where \(x_j \leq x_k\), resulting in a new signed graph \(\dot{G} ^ \prime\), then \(\lambda_{1}(\dot{G}^\prime) \geq \lambda_{1}(\dot{G})\). The equality holds if and only if \(x_i = 0\) and \(x_j = x_k\).
Proof. For (i), we denote by \(E_1 \subseteq E(\dot{G}^\prime)\) the set of added positive edges. By Rayleigh Principle, we have \[\begin{aligned} \lambda_1({\dot{G}^\prime}) – \lambda_1(\dot{G}) & = \max \limits_{\Vert y \Vert = 1} y^{'} A(\dot{G}^\prime) y – x^{'} A(\dot{G}) x \geq x^{'} A(\dot{G}^\prime) x – x^{'} A(\dot{G}) x = 2 \sum_{v_iv_j \in E_1 } x_{i}x_{j} \geq 0. \end{aligned}\]
If \(\lambda_{1}(\dot{G}^\prime) = \lambda_{1}(\dot{G})\), then all the equalities hold and so \(x\) is an eigenvector of \(A(\dot{G}^\prime)\) corresponding to the eigenvalue \(\lambda_1({\dot{G}^\prime})\). Take one positive edge from \(E_1\), say \(v_kv_l\). We will show \(x_l = 0\). Assume that the added positive edges with one endpoint \(v_k\) are \(v_kv_l, v_kv_{k_1}, v_kv_{k_2}, \cdots, v_kv_{k_s}\). According to the following eigenvalue equations, \[\begin{aligned} \lambda_{1}(\dot{G})x_{k} & = \sum_{v_h \in N_{\dot{G}}(v_{k})} \sigma(v_hv_{k})x_h,\\ \lambda_{1}(\dot{G}^\prime)x_{k} & = \sum_{v_h \in N_{\dot{G}}(v_{k})} \sigma(v_hv_{k})x_h + \sum_{j = 1}^{s} x_{k_j} + x_l, \end{aligned}\] we obtain \(x_l = x_{k_1} = \cdots = x_{k_j} = 0\). By similar analysis as above, the entries of \(x\) corresponding to the endpoints of added positive edges are all zeros.
The proof for (ii) is similar to that for (i).
Note that changing negative edges to positive is equivalent to deleting the negative edges and then adding positive edges, so (iii) follows easily from (i) and (ii).
For (iv), we have \[\begin{aligned} \lambda_1({\dot{G}^\prime}) – \lambda_1(\dot{G}) & \geq x^\intercal A(\dot{G}^\prime) x – x^\intercal A(\dot{G}) x = 2x_{i}( x_{k} – x_{j}) \geq 0. \end{aligned}\] If \(\lambda_{1}(\dot{G}^\prime) = \lambda_{1}(\dot{G})\), then all the equalities hold and so \(x\) is an eigenvector of \(A(\dot{G}^\prime)\) corresponding to the eigenvalue \(\lambda_1({\dot{G}^\prime})\). In view of the following eigenvalue equations, \[\begin{aligned} \lambda_{1}(\dot{G})x_{i} & = \sum_{v_h \in N_{\dot{G}}(v_{i}) \setminus v_j} \sigma(v_hv_{i})x_h + x_j,\\ \lambda_{1}(\dot{G}^\prime)x_{i} & = \sum_{v_h \in N_{\dot{G}}(v_{i}) \setminus v_j} \sigma(v_hv_{i})x_h + x_k,\\ \lambda_{1}(\dot{G})x_{j} & = \sum_{v_h \in N_{\dot{G}}(v_{j}) \setminus v_i} \sigma(v_hv_{j})x_h + x_i,\\ \lambda_{1}(\dot{G}^\prime)x_{j} & = \sum_{v_h \in N_{\dot{G}}(v_{j}) \setminus v_i} \sigma(v_hv_{j})x_h, \end{aligned}\] \[\begin{aligned} \lambda_{1}(\dot{G})x_{k} & = \sum_{v_h \in N_{\dot{G}}(v_{k})} \sigma(v_hv_{k})x_h,\\ \lambda_{1}(\dot{G}^\prime)x_{k} & = \sum_{v_h \in N_{\dot{G}}(v_{k})} \sigma(v_hv_{k})x_h + x_i, \end{aligned}\] we have \(x_i = 0\) and \(x_j = x_k\).
The proof for (v) is similar to that for (vi) and we omit it. The converse is clear. ◻
Proof. Without loss of generality, assume for a contradiction that \(x_1 = x_2 = \cdots = x_{k – 1} = 0\). Delete the corresponding vertices from \(\dot{G}\) to obtain a signed graph \(\dot{G}^\prime\). Then by Rayleigh Principle and Lemma 2.4, \[\begin{aligned} \lambda_{1}(\dot{G}) &= (x_{k}, \cdots, x_n) A(\dot{G}^\prime) (x_{k}, \cdots, x_n)^{'} \leq\lambda_{1} (\dot{G}^\prime) \leq \lambda_{1}(K_{n – k + 1}) = n – k, \end{aligned}\] a contradiction. ◻
Proof of Theorem 1.10. From Theorem 1.8 we know that our assertion holds when \(r = 3\). Now by induction on \(r\), assume the assertion is true for all \(r \leq t – 1\) \((3 \leq t – 1 \leq n – 2)\) and prove it for \(t\).
Let \(\dot{G}\) be a signed graph having the maximum index over all \(\mathcal{K}_{t+1}^-\)-free unbalanced signed graphs. In view of Lemma 3.1 and Remark 3.4 we can find \(\widetilde{\dot{G}} \sim \dot{G}\) with a positive unit eigenvector \(x = (x_1, \cdots, x_n)^{'}\) corresponding to \(\lambda_1(\widetilde{\dot{G}}) > n – 2\). Note from Lemma 2.2 that \(\widetilde{\dot{G}}\) is also a connected \(\mathcal{K}_{t+1}^-\)-free unbalanced signed graph. We will show \(\widetilde{\dot{G}} = \dot{G}^{n – t, 0, \cdots, 0}\) step by step.
First, since \(\widetilde{\dot{G}}\) is unbalanced, there exist at least one negative edge and at least one negative cycle. Take a negative cycle \(\mathcal{C} = v_1v_2 \cdots v_lv_1\) of the shortest length from \(\widetilde{\dot{G}}\). We claim \(l = 3\), otherwise \(\widetilde{\dot{G}}\) is \(\mathcal{K}_3^-\)-free, and so \(\lambda_{1}(\widetilde{\dot{G}}) \leq \frac{1}{2}(\sqrt{n^2 – 8} + n – 4) < n – 2\) by Theorem 1.4, a contradiction. Thus, \(\mathcal{C}\) is a negative triangle on vertices \(v_1\), \(v_2\), and \(v_3\).
Secondly, we say that all the negative edges of \(\widetilde{\dot{G}}\) are contained in \(\mathcal{C}\). Indeed, if there exists a negative edge not in \(\mathcal{C}\), by Proposition 3.2 we may delete it resulting in a \(\mathcal{K}_{t+1}^-\)–free unbalanced signed graph with larger index, a contradiction. Therefore, the number of negative edges of \(\widetilde{\dot{G}}\) is either \(1\) or \(3\).
We conclude that \(\widetilde{\dot{G}}\) contains only one negative edge. Actually, if not, then \(\mathcal{C}\) is a negative triangle with three negative edges and by Proposition 3.2 we may reverse signs of two of those, resulting in a \(\mathcal{K}_{t+1}^-\)-free unbalanced signed graph with larger index, which leads to a contradiction.
Next we claim that \(\widetilde{\dot{G}}\) contains an unbalanced \(t\)-vertex clique with one negative edge \(v_1v_2\), written as \(K_t^-\). If not, \(\widetilde{\dot{G}}\) is \(\mathcal{K}_t^-\)-free and by induction hypothesis and Proposition \(3.2\) we know that \(\lambda_{1}(\widetilde{\dot{G}}) \leq \lambda_{1} (\dot{G}^{n – t + 1, 0, \cdots, 0}) < \lambda_{1} (\dot{G}^{n – t, 0, \cdots, 0})\), a contradiction. Without loss of generality, suppose that \(X = V(K_t^-) = \{v_1, \cdots, v_t\}\) and \(Y = V(\widetilde{\dot{G}}) \setminus X\), and further that \(x_1 \leq x_2\) and \(x_3 \leq \cdots \leq x_t\). Let \(W_1 = N_{\widetilde{\dot{G}}}(v_1) \setminus N_{\widetilde{\dot{G}}}(v_2), W_2 = N_{\widetilde{\dot{G}}}(v_2) \setminus N_{\widetilde{\dot{G}}}(v_1)\), and \(W = N_{\widetilde{\dot{G}}}(v_1) \cap N_{\widetilde{\dot{G}}}(v_2) \setminus X\). We claim that \(W_1 = \emptyset\), otherwise there exists a vertex \(v_k\) satisfying \(v_k \stackrel{+}{\sim} v_1\) and \(v_k \not \sim v_2\), and by Proposition 3.2 we can rotate the positive edge \(v_kv_1\) to the non-edge position \(v_kv_2\), getting a \(\mathcal{K}_{t+1}^-\)-free unbalanced signed graph with larger index than \(\widetilde{\dot{G}}\), a contradiction.
We proceed with our proof and establish that \(x_2 < x_3\). Assume for a contradiction that \(x_2 \geq x_3\). If there exists \(V_1 \subseteq V(\widetilde{\dot{G}})\) such that \(\widetilde{\dot{G}}[V_1 \cup \{v_1, v_3\}]\) is all-positive clique \(K_{t+1}\), then by \(W_1 = \emptyset\) we have that each vertex in \(V_1\) is adjacent to \(v_2\) and so \(\widetilde{\dot{G}}[V_1 \cup \{v_1, v_2\}]\) is an unbalanced clique of order \(t+1\), a contradiction. So there exist no \(V_1 \subseteq V(\widetilde{\dot{G}})\) such that \(\widetilde{\dot{G}}[V_1 \cup \{v_1, v_3\}]\) is \(K_{t+1}\), and by Proposition 3.2 we may reverse the signs of \(v_1v_2\) and \(v_1v_3\), resulting in a \(\mathcal{K}_{t+1}^-\)-free unbalanced signed graph with larger index than \(\widetilde{\dot{G}}\), a contradiction. Then we know that \(x_1 \leq x_2 < x_3 \leq \cdots \leq x_t\).
Note that each vertex in \(Y\) is adjacent to at most \(t-1\) vertices in \(X\). Then we claim that \(W = \emptyset\). Otherwise, there exists a vertex \(v_i \in W\) not adjacent to a vertex \(v_j \in X \setminus \{v_1, v_2\}\), and then we can rotate the positive edge \(v_iv_1\) to the non-edge position \(v_iv_j\), resulting a signed graph with larger index than \(\widetilde{\dot{G}}\) by Proposition 3.2 and the fact \(x_j > x_1\), a contradiction.
Summing up, \(\widetilde{\dot{G}}\) must be a subgraph of \(\dot{G}^{n – t, 0, \cdots, 0}\). Furthermore, combining Proposition 3.2 and the fact that the eigenvector \(x\) is positive, \(\widetilde{\dot{G}}\) actually is \(\dot{G}^{n – t, 0, \cdots, 0}\). Thus, we have proven that the conclusion holds when \(r = t\). Based on the induction hypothesis, we complete the proof of Theorem 1.10. ◻
In this paper, we study the problems what is the maximum number of edges and what is the maximum index for \(\mathcal{K}_{r+1}^-\)-free \((r \geq 2)\) unbalanced signed graphs. The condition of unbalance is necessary, otherwise, up to switching equivalence, the all-positive complete graph \(K_n\) is the unique \(\mathcal{K}_{r+1}^-\)-free signed graph with \(e(\dot{G}) = n(n-1)/2\), and is the unique \(\mathcal{K}_{r+1}^-\)-free signed graph with \(\rho(\dot{G}) = n – 1\). In this time, this problem is trivial.
Our result partly solve the following problem, which called as the spectral Turán-like problem for \(\mathcal{K}_{r+1}^-\)-free signed graphs. To see this, we need introduce some notations and notions.
Combining Theorem 1.10 and Lemma 2.3, we can drive the following proposition. Note that the negation of \(\dot{G}\) (denoted by \(-\dot{G}\)) is obtained by reversing the sign of each edge in \(\dot{G}\). Clearly, the eigenvalues of \(-\dot{G}\) are obtained by reversing the signs of the eigenvalues of \(\dot{G}\).
Proof. The assertion holds for \(r = 3\) by Theorem 1.8. Now assume that \(4 \leq r \leq \lfloor n/2 \rfloor\) and \(\dot{G}\) has the maximum spectral radius among \(\mathcal{K}^-_{r+1}\)-free unbalanced signed graphs. Note that \(\dot{G}^{n – r, 0, \cdots, 0}\) is \(\mathcal{K}^-_{r+1}\)-free and so \(\rho(\dot{G}) \geq \rho(\dot{G}^{n – r, 0, \cdots, 0}) > n – 2\).
We claim that \(\rho(\dot{G}) = \lambda_{1}(\dot{G})\). If not, then \(\rho(\dot{G}) = -\lambda_{n}(\dot{G})\). Since \(-\dot{G}\) contains no \(r+1\)-vertex balanced clique, then \(\omega_b(-\dot{G}) \leq r\). Using Lemma 2.3, we have \[\begin{aligned} n – 2 < \rho(\dot{G}) = -\lambda_{n}(\dot{G}) &= \lambda_{1}(-\dot{G}) \leq n \cdot (1 – \frac{1}{w_b(-\dot{G})}) \leq \frac{r – 1}{r}n, \end{aligned}\] which contradicts to \(r \leq \lfloor n/2 \rfloor\).
So in this time, the problem finding the maximum spectral radius among \(\mathcal{K}^-_{r+1}\)-free \((3 \leq r \leq \lfloor n/2 \rfloor)\) unbalanced signed graphs becomes finding the maximum index among \(\mathcal{K}^-_{r+1}\)-free \((3 \leq r \leq \lfloor n/2 \rfloor)\) unbalanced signed graphs. The latter is solved by Theorem 1.10. ◻
Proposition 4.2 solves Problem 4.1 under the restriction \(3 \leq r \leq \lfloor n/2 \rfloor\). The case of \(r > \lfloor n/2 \rfloor\) is left and seems more challenging for further study.
1970-2025 CP (Manitoba, Canada) unless otherwise stated.