Frustration and isoperimetric inequalities for signed graphs

详细信息    查看全文

• 作者：Florian Martin ^{florian.martin@pmi.com}
• 关键词：Spectral graph theory ; Signed graphs ; Monotone systems ; Frustration index ; Signed Laplacian ; Balanced graphs
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：30 January 2017
• 年：2017
• 卷：217
• 期：part_P2
• 页码：276-285
• 全文大小：584 K
• 卷排序：217

文摘

Let Gσ=(V,E,σ)Gσ=(V,E,σ) be a connected signed graph. Using the equivalence between signed graphs and 22-lifts of graphs, we show that the frustration index of GσGσ is bounded from below and above by expressions involving another graph invariant, the smallest eigenvalue of the (signed) Laplacian of GσGσ. From the proof, stricter bounds are derived. Additionally, we show that the frustration index is the solution to a l1l1-norm optimization problem over the 22-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.