طیف گراف های ابرستاره و گراف های یالی آن ها

فرض کنید ‏n ≥ 1‎، عددی صحیح باشد. گراف ابرمکعب ‏qn‏ گرافی است با مجموعه رئوس ‏‎{0,1}n، که در آن دو ‏‎ n‏ تایی باهم مجاور ‏هستند اگر و تنها اگر در یک درآیه باهم اختلاف داشته باشند. این نوع از گراف کاربردهای زیادی در علوم کامپیوتر و سایر علوم دارد. در گراف ‏qn، لایه ‏k‏‌‌اُم را با ‏lk‏ نشان می‌دهیم که مجموعه رئوسی است با ‏دقیقا ‏k‏ درآیه ‏‎1‎، به‌عبارت دیگر رئوسی با وزن ‏k، که در آن ‏‎1 ≤ k ≤ n‏ است. برای هر ‏k ∈{1,…,n1}‎، گراف ابرستاره ‏b(n,k)‎‏ زیرگرافی از ‏qn‏ است که توسط دو لایه ‏lk‏ و ‏lk+1‎‏ القا می‌شود. در این مقاله، ما قصد ‌داریم طیف گراف ابرستاره ‏b(n,k)‎‏ و ‏l(b(n,k))‎‏ را به‌طور کامل مشخص کنیم، که در آن ‏l(b(n,k))‎‏ نشان دهنده گراف یالی ‏b(n,k)‎‏ است. به‌ویژه نشان خواهیم داد که ‏گراف ‏l(b(n,k))‎‏ یک گراف صحیح است، یعنی گرافی است که تمام مقادیر ویژه آن اعداد صحیح هستند.‏ در این مقاله، در مورد برخی خواص جبری گراف ‏ ‏ و گراف یالی آن تحقیق خواهیم کرد. ‏به‌ویژه طیف این گراف‌ها را به‌طور کامل مورد بررسی ‏قرار‌خواهیم داد.‏