Seidel Integral Complete Split Graphs

Document Type : Original Scientific Paper


1 Faculty of Education, Trnava University, Trnava, Slovakia

2 Mathematical Institute, Serbian Academy of Sciences and Arts, Kneza Mihaila 36, 11000 Belgrade, Serbia


In the paper we consider a generalized join operation, that is, the H-join on graphs where H is an arbitrary graph. In terms of Seidel matrix of graphs we determine the Seidel spectrum of the graphs obtained by this operation on regular graphs. Some additional consequences regarding S-integral complete split graphs are also obtained, which allows to exhibit many infinite families of Seidel integral complete split graphs.


[1] B. Arsic, D. Cvetkovic, S. K. Simic and M. Škaric, Graph spectral techniques in computer sciences, Appl. Anal. Discrete Math. 6 (2012) 1-30.
[2] K. Balinska, D. Cvetkovic, Z. Radosavljevic, S. K. Simic and D. Stevanovic, A survey on integral graphs, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. 13 (2002) 42-65.
[3] D. M. Cardoso, M. A. A. de Freitas, E. A. Martins and M. Robbiano, Spectra of graphs obtained by a generalization of the join graph operation, Discrete Math. 313 (2013) 733-741.
[4] D. Cvetkovic, M. Doob and H. Sachs, Spectra of Graphs - Theory and Applications, Third Edition, Johann Ambrosius Barth, Heidelberg, 1995.
[5] D. Cvetkovic and S. K. Simic, Towards a spectral theory of graphs based on the signless Laplacian. I., Publ. Inst. Math. (Beograd) (N.S.) 85 (99) (2009) 19-33.
[6] M. Fiedler, Eigenvalues of nonnegative symmetric matrices, Linear Algebra Appl. 9 (1974) 119–142.
[7] M. A. A. de Freitas, N. M. M. de Abreu, R. R. Del-Vecchio and S. Jurkiewicz, Infinite families of Q-integral graphs, Linear Algebra Appl. 432 (2010) 2352-2360.
[8] P. Hansen, H. Mélot and D. Stevanovic, Integral complete split graphs, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. 13 (2002) 89-95.
[9] F. Harary and A. J. Schwenk, Which graphs have integral spectra? In: R. A. Bari and F. Harary (Eds.) Graphs and Combinatorics, Lecture Notes in Mathematics, vol 406. Springer, Berlin, Heidelberg, 1974.
[10] P. Híc and M. Pokorný, Remarks on D-integral complete multipartite graphs, Czechoslovak Math. J. 66 (141)(2) (2016) 457-464.
[11] S. Kirkland, M. A. A. de Freitas, R. R. Del Vecchio and N. M. M. de Abreu, Split non-threshold Laplacian integral graphs, Linear Multilinear Algebra 58 (2010) 221-233.
[12] S. Lv, The Seidel polynomial and spectrum of the complete 4-partite graphs, J. Northwest Norm. Univ. Nat. Sci. 47 (2) (2011) 22-25.
[13] S. Lv, L. Wei and H. Zhao, On the Seidel integral complete multipartite graphs, Acta Math. Appl. Sin. Engl. Ser. 28 (4) (2012) 705-710.
[14] R. Merris, Split graphs, Euro. J. Combin. 24 (2003) 413-430.
[15] M. Pokorný, QLS integrality of complete r-partite graphs, Filomat 29 (5) (2015) 1043-1051.
[16] M. Pokorný, P. Híc and D. Stevanovic, Remarks on Q-integral complete multipartite graphs, Linear Algebra Appl. 439 (2013) 2029-2037.
[17] M. Pokorný, P. Híc, D. Stevanovic and M. Miloševic, On distance integral graphs, Discrete Math. 338 (10) (2015) 1784-1792.
[18] L. Wang, G. Zhao and Ke. Li, Seidel integral complete r-partite graphs, Graphs Combin. 30 (2) (2014) 479-493.
[19] B. F. Wu, Y. Y. Lou and Ch. X. He, Signless Laplacian and normalized Laplacian on the H-join operation of graphs, Discrete Math. Algorithms Appl. 6 (2014) 1450046, 13 pp.
[20] N. Zhao and T.Wu, A study of S-integral graphs of complete 5-partite graphs, Pure Appl. Math. 30 (5) (2014) 467-473.
[21] N. Zhao, T. Wu and C. Guo, The necessary and sufficient condition for the complete 6-partite graphs to be S-integral, Pure Appl. Math. 29 (2) (2013) 132-139.