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

الموضوعات :

فتانه کریمی ¹ (گروه ریاضی، دانشکده علوم پایه، دانشگاه لرستان، خرم‌آباد، لرستان، ایران)
سید مرتضی میرافضل ² (گروه ریاضی، دانشکده علوم پایه، دانشگاه لرستان، خرم‌آباد، لرستان، ایران)

تاريخ الإرسال : 04 الثلاثاء , شعبان, 1440 تاريخ التأكيد : 20 الثلاثاء , ذو القعدة, 1440 تاريخ الإصدار : 25 الأحد , ربيع الثاني, 1441

الکلمات المفتاحية: Spectrum, Line graph, Hyper-star graph, Integral graph, Hypercube,

ملخص المقالة :

فرض کنید ‏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))‎‏ یک گراف صحیح است، یعنی گرافی است که تمام مقادیر ویژه آن اعداد صحیح هستند.‏ در این مقاله، در مورد برخی خواص جبری گراف ‏ ‏ و گراف یالی آن تحقیق خواهیم کرد. ‏به‌ویژه طیف این گراف‌ها را به‌طور کامل مورد بررسی ‏قرار‌خواهیم داد.‏

المصادر:

 

‎[1] R. B. Bapat. Graphs and ‎Matrices. Springer‏-‏verlag, London (‎‎2010).‎

 

‎[2] N. L. Biggs. Algebraic Graph ‎Theory (Second edition). ‎Cambridge Mathematical Library (Cambridge University Press, ‎Cambridge) (1993).‎

 

‎[3] J. A. Bondy, U. S. R. Murty. ‎Graph Theory. Springer Verlage (2008).‎

 

‎[4] A. E. Brouwer, W. H. Haemers. ‎Spectra of Graphs. Springer Verlage (2012).‎

 

‎[5] D. Cvetkovic, P. Rowlinson, S. Simic. An introduction to the theory ‎of graph spectra. Cambridge ‎University Press (2010).‎

 

‎[6] D. Cvetkovic, Z. Rodosavljevic, ‎S. K. Simic. A survey on integral ‎graphs. Univ. Beograde, Publ. ‎Elektrotehn. Fak. Ser. Mat. 15 (2004).‎

 

‎[7] C. Godsil, G. Royle. Algebraic ‎Graph Theory. Springer Verlage (2001).‎

 

‎[8] F. Harary, A. J. Schwenk. ‎Which graphs have integral spectra? ‎In Graphs and Combinatorics, (eds. ‎R. Bari and F. Harary), (Proc. ‎Capital Conf., George Washington ‎Univ., Washington, D.C., 1973) ‎Lecture Notes in Mathematics 406, ‎Springer-Verlag, Berlin 45-51, (‎‎1974).‎

 

‎[9] L. Lovasz. Problem 11 in: ‎Combinatorial structures and their ‎applications. (Proc. Calgary ‎Internat. Conf, Calgary, Alberta, ‎‎1969), Gordon and Breach, New ‎York 243-246 (1970).‎

 

‎[10] S. M. Mirafzal. On the ‎automorphism groups of regular ‎hyperstars and folded hyperstars. ‎Ars Comb. 123, 75-86 (2015).‎

 

‎[11] S. M. Mirafzal. The ‎automorphism group of the bipartite ‎Kneser graph. Proc. Indian Acad. Sci. Math. Sci. 129 no. 3, Art. 34, 8 pp (2019).

 

‎[12] S. M. Mirafzal. Cayley ‎properties of the line graphs ‎induced by consecutive layers of ‎the hypercube. Arxive: ‎‎1711. 02701v3, submitted.‎

 

‎[13] M. Watkins. Connectivity of ‎transitive graphs. J. Combin. Theory ‎‎8: 23-29 (1970).‎

 

‎[14] S. Wolfram, Wolfram ‎Mathematica 8.‎