The spectrum of the hyper-star graphs and their line graphs
Subject Areas : Statistics
F. Karimi
1
(Department of Mathematics, Faculty of Sciences, Lorestan University, Khoramm-Abad, Iran)
S. M. Mirafzal
2
(Department of Mathematics, Faculty of Sciences, Lorestan University, Khoramm-Abad, Iran)
Keywords: گراف صحیح., ابرمکعب, گراف ابرستاره, گراف یالی, طیف,
Abstract :
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.
