2023/11/26 by Xiong, Zhuang, Hou, Yaoping
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2311.15321
This paper aims to address the problem: what is the maximum index among all C-r-free unbalanced signed graphs, where C-r is the set of unbalanced cycle of length r. Let Γ1 = C3- \bullet Kn-2 be a signed graph obtained by identifying a vertex of Kn-2 with a vertex of C3- whose two incident edges in C3- are all positive, where C3- is an unbalanced triangle with one negative edge. It is shown that if Γ is an unbalanced signed graph of order n, r is an integer in \4, ⋯, \lfloor (n)/(3)\rfloor + 1 \, and λ1(Γ) ≥ λ1(Γ1), then Γ contains an unbalanced cycle of length r, unless Γ∼ Γ1. \indent It is shown that the result are significant in spectral extremal graph problems. Because they can be regarded as a extension of the spectral Turán problem for cycles [Linear Algebra Appl. 428 (2008) 1492--1498] in the context of signed graphs. Furthermore, our result partly resolved a recent open problem raised by Lin and Wang [arXiv preprint arXiv:2309.04101 (2023)].