کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777611 | 1632967 | 2017 | 25 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Three conjectures in extremal spectral graph theory
ترجمه فارسی عنوان
سه فرضیه در نظریه گراف افقی طیفی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
شعاع طیفی، نمودار پلانار، بی نظمی نمودار نظریه گراف فوق العاده،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We prove three conjectures regarding the maximization of spectral invariants over certain families of graphs. Our most difficult result is that the join of P2 and Pnâ2 is the unique graph of maximum spectral radius over all planar graphs. This was conjectured by Boots and Royle in 1991 and independently by Cao and Vince in 1993. Similarly, we prove a conjecture of CvetkoviÄ and Rowlinson from 1990 stating that the unique outerplanar graph of maximum spectral radius is the join of a vertex and Pnâ1. Finally, we prove a conjecture of Aouchiche et al. from 2008 stating that a pineapple graph is the unique connected graph maximizing the spectral radius minus the average degree. To prove our theorems, we use the leading eigenvector of a purported extremal graph to deduce structural properties about that graph.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 126, September 2017, Pages 137-161
Journal: Journal of Combinatorial Theory, Series B - Volume 126, September 2017, Pages 137-161
نویسندگان
Michael Tait, Josh Tobin,