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

فرض کنید ‏n ≥ 1‎، عددی صحیح باشد. گراف ابرمکعب ‏Qn‏ گرافی است با مجموعه رئوس ‏‎{0,1}n، که در آن دو ‏‎ n‏- تایی باهم مجاور ‏هستند اگر و تنها اگر در یک درآیه باهم اختلاف داشته باشند. این نوع از گراف کاربردهای زیادی در علوم کامپیوتر و سایر علوم دارد. در گراف ‏Qn، لایه ‏k‏ ام را با ‏Lk‏ نشان می دهیم که مجموعه رئوسی است با ‏دقیقا ‏k‏ درآیه ‏‎1‎، به عبارت دیگر رئوسی با وزن ‏k، که در آن ‏‎1 ≤ k ≤ n‏ است. برای هر ‏k ∈{1,...,n-1}‎، گراف ابرستاره ‏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))‎‏ یک گراف صحیح است، یعنی گرافی است که تمام مقادیر ویژه آن اعداد صحیح هستند.‏ در این مقاله، در مورد برخی خواص جبری گراف ‏ ‏ و گراف یالی آن تحقیق خواهیم کرد. ‏به ویژه طیف این گراف ها را به طور کامل مورد بررسی ‏قرار خواهیم داد.‏