Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949799 | Discrete Applied Mathematics | 2017 | 10 Pages |
Abstract
Let GÏ=(V,E,Ï) be a connected signed graph. Using the equivalence between signed graphs and 2-lifts of graphs, we show that the frustration index of GÏ is bounded from below and above by expressions involving another graph invariant, the smallest eigenvalue of the (signed) Laplacian of GÏ. From the proof, stricter bounds are derived. Additionally, we show that the frustration index is the solution to a l1-norm optimization problem over the 2-lift of the signed graph. This leads to a practical implementation to compute the frustration index. Also, leveraging the 2-lifts representation of signed graphs, a straightforward proof of Harary's theorem on balanced graphs is derived. Finally, real world examples are considered.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Florian Martin,