Extremal results for ${\mathcal{K}}_{r+1}^{-}$-free unbalanced signed graphs

1. Introduction

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})\ge {\lambda }_2(\dot{G})\ge \cdots \ge {\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\ge 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)\le \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\ge 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\le 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\ge 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_1{v}_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\le i\le 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\le i\le r)$ is not greater than $r–2$, that is, $y_3+\cdots +y_r\le 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\ge 1$, and if $r\ge 3$, then $y_1,\cdots ,y_r\ge 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 $\tilde{\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\ge 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.

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.

2. Preliminaries

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\le i,j\le m}$ is called the quotient matrix of $M$ with respect to the equitable partition $P$.

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.

3. Proofs

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\nsim v$ for that $u$ is adjacent to $v$ by a positive edge, a negative edge, and non-edge, respectively;

– ${\dot{G}}^{\mathrm{\prime }}\sim \dot{G}$ for that ${\dot{G}}^{\mathrm{\prime }}$ is switching equivalent to $\dot{G}$.

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

where 0 and j represent the zero vector and the all-ones vector of appropriate dimensions, respectively, and $I$ and $J$ denote the identity matrix and all-ones matrix of appropriate orders, respectively. By Lemma 2.1, the eigenvalues of $Q_1$ are that of A and the other eigenvalues of A remain if we add some scalar multiple of $\mathbf{\text{j}}$ or $J$ from the blocks equal to $-1$, $\mathbf{\text{j}}$, $J$, and $J–I$. Then A and $Q_1$ become

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\le 0$, and so the equality holds if and only if $r=3$. So we have ${\lambda }_1({\dot{G}}^{n–r,0,\cdots ,0})\ge 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{)}^{{}^{\prime }}$ 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{array}{rl}{\lambda }_1(\dot{G})x_i=& \sum _{v_j\in N_{\dot{G}}(v_i)}\sigma (v_i{v}_j)x_j.\end{array}$$ 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.

4. Concluding remarks

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\ge 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}$.

Proposition 4.2 solves Problem 4.1 under the restriction $3\le r\le \lfloor n/2\rfloor$. The case of $r>\lfloor n/2\rfloor$ is left and seems more challenging for further study.