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)
[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-

[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, European Journal of Combinatorics 24 (2003) 413-
[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)

Volume 4, Issue 2
Special Issue: Spectral Graph Theory and Mathematical Chemistry with Connection to Computer Science
Autumn 2019
Pages 137-150