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

Abstract

This paper gives tight upper bounds on the number of edges and the index for ${\mathcal{K}}_{r+1}^{-}$-free unbalanced signed graphs, where ${\mathcal{K}}_{r+1}^{-}$ is the set of $r+1$-vertices unbalanced signed complete graphs. \indent We first prove that if $\Gamma$ is an $n$-vertices ${\mathcal{K}}_{r+1}^{-}$-free unbalanced signed graph, then the number of edges of $\Gamma$ is $$e(\Gamma )\le \frac{n(n-1)}{2}-(n-r).$$ \indent Let ${\Gamma }_{1,r-2}$ be a signed graph obtained by adding one negative edge and $r-2$ positive edges between a vertex and an all positive signed complete graph $K_{n-1}$. Secondly, we show that if $\Gamma$ is an $n$-vertices ${\mathcal{K}}_{r+1}^{-}$-free unbalanced signed graph, then the index of $\Gamma$ is $${\lambda }_1(\Gamma )\le {\lambda }_1({\Gamma }_{1,r-2}),$$ with equality holding if and only if $\Gamma$ is switching equivalent to ${\Gamma }_{1,r-2}$. \indent It is shown that these results are significant in extremal graph theory. Because they can be regarded as extensions of Tur{á}n's Theorem [Math. Fiz. Lapok 48 (1941) 436--452] and spectral Tur{á}n problem [Linear Algebra Appl. 428 (2008) 1492--1498] on signed graphs, respectively. Furthermore, the second result partly resolves a recent open problem raised by Wang [arXiv preprint arXiv:2309.15434 (2023)].

13 pages, 1 figure