طیف گراف های ابرستاره و گراف های یالی آن ها
محورهای موضوعی : آمارفتانه کریمی 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)) یک گراف صحیح است، یعنی گرافی است که تمام مقادیر ویژه آن اعداد صحیح هستند. در این مقاله، در مورد برخی خواص جبری گراف و گراف یالی آن تحقیق خواهیم کرد. به‌ویژه طیف این گراف‌ها را به‌طور کامل مورد بررسی قرار‌خواهیم داد.
Let n 1 be an integer. The hypercube Qn is the graph whose vertex set isf0;1gn, where two n-tuples are adjacent if they differ in precisely one coordinate. This graph has many applications in Computer sciences and other area of sciences. Inthe graph Qn, the layer Lk is the set of vertices with exactly k 1’s, namely, vertices ofweight k, 1 k n. The hyper-star graph B(n;k) is the subgraph of Qn induced bylayers Lk and Lk+1; 0 < k < n. In this paper, we determine the spectrum of the hyperstargraph B(n;k) and L(B(n;k)), where L(B(n;k)) is the line graph of the graphB(n;k). In particular, we show that the graph L(B(n;k)) is an integral graph, that is,all of its eigenvalues are integers. In this paper, we investigate some of the algebraic properties of the graph B(n;k) andits line graph L(B(n;k)). In particular, we determine the spectrum of these graphs.
[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.
