Products of graphs and Nordhaus-Gaddum type inequalities for eigenvalues

Document Type : Corrigendum


Amirkabir University of Technology


In this paper‎, ‎we obtain $\alpha$ as coefficient for the $G=K_{\alpha n} \cup \overline{K_{(1-\alpha)n}}$ and by which we discuss Nikiforov's conjecture for $\lambda_{1}$ and Aouchiche and Hansen's conjecture for $q_1$ in Nordhaus-Gaddum type inequalities‎. ‎Furthermore‎, ‎by the properties of the products of graphs we put forward a new approach to find some bounds of Nordhaus-Gaddum type inequalities‎.


Main Subjects

[1] M. Aouchiche and P. Hansen, A survey of Nordhaus-Gaddum type relations, Discrete. Appl. Math., 161 (2013) 466–546.
[2] F. Ashraf and B. Tayfeh-Rezaie, Nordhaus-Gaddum type inequalities for Laplacian and signless Laplacian eigenval-ues, Electron. J. Combin., 21 (2014).
[3] E. A. Brouwer and W. H. Haemers, Spectra of graphs, Springer Science & Business Media, 2011.
[4] D. M. Cvetkovi´c, M. Doob and H. Sachs, Spectra of graphs theory and application, 87, New York: Academic Press, 1980.
[5] M. Fiedler, Algebraic connectivity of graphs, Czechoslovak mathematical journal, 23 (1973) 298–305.
[6] X. Li, The relations between the spectral radius of the graphs and their complement, J. North China Technol. Inst., 17 (1996) 297–299.
[7] X. Liu and P. Lu, Signless Laplacian spectral characterization of some joins, Elect. J. Linear Algebra, 30 (2015) 443–454.
[8] V. Nikiforov, Eigenvalue problems of Nordhaus-Gaddum type, Discrete Math., 307 (2007) 774–780.
[9] E. A. Nordhaus and J. Gaddum, On complementary graphs, Amer. Math. Monthly, 63 (1956) 175–177.
[10] L. Shi, Bounds on the (Laplacian) spectral radius of graphs, Linear Algebra Appl., 422 (2007) 755–770.
[11] H. Sayamai, Estimation of Laplacian spectra of direct and strong product graphs, Discrete Appl. Math., 205 (2016) 160–170.
[12] T. Terpai, Proof of a conjecture of V. Nikiforov, Combinatorica, 31 (2011) 739–754.