طیف گراف های ابرستاره و گراف های یالی آن ها
الموضوعات :فتانه کریمی 1 , سید مرتضی میرافضل 2
1 - گروه ریاضی، دانشکده علوم پایه، دانشگاه لرستان، خرم‌آباد، لرستان، ایران
2 - گروه ریاضی، دانشکده علوم پایه، دانشگاه لرستان، خرم‌آباد، لرستان، ایران
الکلمات المفتاحية: 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.
