2025/11/19 by Chen, Sirui, Li, Jiaao, Wang, Zhouningxin
Computer Science · Mathematics · #Interconnection Networks and Systems #Graph theory and applications #Advanced Graph Theory Research
paper · doi:10.48550/arxiv.2511.15226
The frustration index of a signed graph is defined as the minimum number of negative edges among all switching-equivalent signatures. This can be regarded as a generalization of the classical Max-Cut problem in graphs, as the Max-Cut problem is equivalent to determining the frustration index of signed graphs with all edges being negative signs. In this paper, we prove that the frustration index of an n-vertex signed connected simple subcubic graph, other than (K4, -), is at most (3n + 2)/(8), and we characterize the family of signed graphs for which this bound is attained. This bound can be further improved to (n)/(3) for signed 2-edge-connected simple subcubic graphs, with the exceptional signed graphs being characterized. As a corollary, every signed 2-edge-connected simple cubic graph on at least 10 vertices and with m edges has its frustration index at most (2)/(9)m, where the upper bound is tight as it is achieved by an infinite family of signed cubic graphs.