The spectrum of the hyper-star graphs and their line graphs

Document Type : research paper


Department of Mathematics, Faculty of Sciences, Lorestan University, Khoramm-Abad, Iran


Let n  1 be an integer. The hypercube Qn is the graph whose vertex set is
f0;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. In
the graph Qn, the layer Lk is the set of vertices with exactly k 1’s, namely, vertices of
weight k, 1  k  n. The hyper-star graph B(n;k) is the subgraph of Qn induced by
layers Lk and Lk+1; 0 < k < n. In this paper, we determine the spectrum of the hyperstar
graph B(n;k) and L(B(n;k)), where L(B(n;k)) is the line graph of the graph
B(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) and
its line graph L(B(n;k)). In particular, we determine the spectrum of these graphs.


Article Title [فارسی]

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

Authors [فارسی]

  • فتانه کریمی
  • سید مرتضی میرافضل
گروه ریاضی، دانشکده علوم پایه، دانشگاه لرستان، خرم‌آباد، لرستان، ایران
Abstract [فارسی]

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

Keywords [فارسی]

  • ‏ ابرمکعب
  • گراف ابرستاره
  • طیف
  • گراف یالی
  • گراف صحیح.‏
‎[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.‎