کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4600413 1336849 2012 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Minimum vertex covers and the spectrum of the normalized Laplacian on trees
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات اعداد جبر و تئوری
پیش نمایش صفحه اول مقاله
Minimum vertex covers and the spectrum of the normalized Laplacian on trees
چکیده انگلیسی

We show that, in the graph spectrum of the normalized graph Laplacian on trees, the eigenvalue 1 and eigenvalues near 1 are strongly related to minimum vertex covers.In particular, for the eigenvalue 1, its multiplicity is related to the size of a minimum vertex cover, and zero entries of its eigenvectors correspond to vertices in minimum vertex covers; while for eigenvalues near 1, their distance to 1 can be estimated from minimum vertex covers; and for the largest eigenvalue smaller than 1, the sign graphs of its eigenvectors take vertices in a minimum vertex cover as representatives.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Linear Algebra and its Applications - Volume 437, Issue 4, 15 August 2012, Pages 1089-1101