کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8898102 | 1631082 | 2017 | 22 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Equitable decompositions of graphs with symmetries
ترجمه فارسی عنوان
تقسیمات صحیح گراف ها با تقارن
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
اعداد جبر و تئوری
چکیده انگلیسی
We investigate connections between the symmetries (automorphisms) of a graph and its spectral properties. Whenever a graph has a symmetry, i.e. a nontrivial automorphism Ï, it is possible to use Ï to decompose any matrix MâCnÃn appropriately associated with the graph. The result of this decomposition is a number of strictly smaller matrices whose collective eigenvalues are the same as the eigenvalues of the original matrix M. Some of the matrices that can be decomposed are the graph's adjacency matrix, Laplacian matrix, etc. Because this decomposition has connections to the theory of equitable partitions it is referred to as an equitable decomposition. Since the graph structure of many real-world networks is quite large and has a high degree of symmetry, we discuss how equitable decompositions can be used to effectively bound both the network's spectral radius and spectral gap, which are associated with dynamic processes on the network. Moreover, we show that the techniques used to equitably decompose a graph can be used to bound the number of simple eigenvalues of undirected graphs, where we obtain sharp results of Petersdorf-Sachs type.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Linear Algebra and its Applications - Volume 513, 15 January 2017, Pages 409-434
Journal: Linear Algebra and its Applications - Volume 513, 15 January 2017, Pages 409-434
نویسندگان
Wayne Barrett, Amanda Francis, Benjamin Webb,