کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6416017 | 1631091 | 2016 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Sharp spectral bounds of several graph parameters using eigenvector norms
ترجمه فارسی عنوان
محدوده طیفی شارپ از چندین پارامتر گراف با استفاده از هنجارهای مخصوص
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
اعداد جبر و تئوری
چکیده انگلیسی
We investigate the role of the 1- and â-norms of eigenvectors in spectral graph theory. In particular, we produce several randomized algorithms which show that various graph-theoretic parameters can be tightly bounded by the eigenvalues as well as norms of the corresponding eigenvectors. Further, in some cases, these inequalities can determine the parameters exactly. Our results include: a spectral bound for the densest subgraph problem, an adapted “converse” to the Expander Mixing Lemma, and an adapted spectral approach to the maximum cut problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Linear Algebra and its Applications - Volume 504, 1 September 2016, Pages 48-63
Journal: Linear Algebra and its Applications - Volume 504, 1 September 2016, Pages 48-63
نویسندگان
Franklin H.J. Kenter,