2023/11/27 by Xiong, Zhuang, Hou, Yaoping
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2311.15501
This paper gives tight upper bounds on the number of edges and the index for K-r + 1-free unbalanced signed graphs, where K-r + 1 is the set of r+1-vertices unbalanced signed complete graphs. \indent We first prove that if Γ is an n-vertices K-r + 1-free unbalanced signed graph, then the number of edges of Γ is e(Γ) ≤ (n(n-1))/(2) - (n - r ). \indent Let Γ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 Kn - 1. Secondly, we show that if Γ is an n-vertices K-r + 1-free unbalanced signed graph, then the index of Γ is λ1(Γ) ≤ λ1(Γ1,r-2), with equality holding if and only if Γ is switching equivalent to Γ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)].