Spectral measures of balance for signed graphs
A signed graph is a graph in which each edge is assigned either a positive or a negative sign. Several invariants have been introduced to measure how far a signed graph is from being balanced. In this paper, particular attention is given to the frustration index \(f(\Sigma)\), defined as the minimum number of edges whose removal results in a balanced signed graph. Clearly, a signed graph \(\Sigma\) is balanced if and only if \(f(\Sigma)=0\).\N\NThe authors compute these measures for signed cycles and signed complete graphs. They also establish several lower and upper bounds for the invariants under consideration, emphasizing their relationship with the frustration index.\N\NReferring to \textit{T. Zaslavsky}'s work [Discrete Appl. Math. 4, 47--74 (1982; Zbl 0476.05080)], it is noted that there are exactly six equivalence classes of signatures of the Petersen graph under the combined operations of switching and graph isomorphism.\N\NFor each signed graph \(\Sigma\) whose underlying graph is the Petersen graph, the parameters \(\beta_A(\Sigma)\) and \(\gamma_A(\Sigma)\) are computed, serving as an illustrative example of the general theory. Furthermore, it is shown that\N\[\N\beta_A(\Sigma) = \beta_L(\Sigma) \quad \text{and} \quad \gamma_A(\Sigma) = \gamma_L(\Sigma)\N\]\Nhold for every regular signed graph \(\Sigma\).\N\NIn addition, spectral measures are analyzed for signed cycles and signed complete graphs. Section~3 is devoted to deriving bounds expressed in terms of certain structural invariants, including the frustration index.\N\NOverall, the paper presents interesting results supported by clear and illustrative examples. The findings are impressive and will be valuable to researchers working in the area of signed graphs and related topics.
- An introduction to the theory of graph spectra
- Bounding the largest eigenvalue of signed graphs
- Distance between spectra of graphs
- Estimating distance between an eigenvalue of a signed graph and the spectrum of an induced subgraph
- Frustration and isoperimetric inequalities for signed graphs
- Integral regular net-balanced signed graphs with vertex degree at most four
- Matrices in the theory of signed simple graphs
- Note on the Fundamental Theorem on Irreducible Non-Negative Matrices
- On the Laplacian Eigenvalues of Signed Graphs
- Polynomial reconstruction of signed graphs
- Research problems from the Aveiro workshop on graph spectra
- Revisiting two classical results on graph spectra
- Signed graphs
- Six signed Petersen graphs, and their automorphisms
- Spectral criterion for cycle balance in networks
- Unbalanced signed graphs with extremal spectral radius or index
This page was built for publication: Spectral measures of balance for signed graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6858820)
