کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
4949799 1364257 2017 10 صفحه PDF سفارش دهید دانلود کنید
عنوان انگلیسی مقاله ISI
Frustration and isoperimetric inequalities for signed graphs
ترجمه فارسی عنوان
ناامیدی و نابرابریهای ایزوپرمتریک برای نمودارهای امضا شده
کلمات کلیدی
نظریه گراف طیفی، نمودارهای امضا شده، سیستم های مونوتونی، شاخص خستگی، لاپلاسانی امضا شد نمودارهای متعادل
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 217, Part 2, 30 January 2017, Pages 276-285
نویسندگان
,