Geodesic
A Few Examples and Counterexamples in Spectral Graph Theory
Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 2, pp. 637-662.

Voir la notice de l'article provenant de la source Library of Science

We present a small collection of examples and counterexamples for selected problems, mostly in spectral graph theory, that have occupied our minds over a number of years without being completely resolved.
Keywords: communicability distance, spectral radius, integral graph, second Zagreb index, Wiener index, estrada index, almost cospectral graphs, NEPS of graphs 
@article{DMGT_2020_40_2_a17,
     author = {Stevanovi\'c, Dragan and Milosavljevi\'c, Nikola and Vuki\v{c}evi\'c, Damir},
     title = {A {Few} {Examples} and {Counterexamples} in {Spectral} {Graph} {Theory}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {637--662},
     publisher = {mathdoc},
     volume = {40},
     number = {2},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a17/}
}
TY  - JOUR
AU  - Stevanović, Dragan
AU  - Milosavljević, Nikola
AU  - Vukičević, Damir
TI  - A Few Examples and Counterexamples in Spectral Graph Theory
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2020
SP  - 637
EP  - 662
VL  - 40
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a17/
LA  - en
ID  - DMGT_2020_40_2_a17
ER  - 
%0 Journal Article
%A Stevanović, Dragan
%A Milosavljević, Nikola
%A Vukičević, Damir
%T A Few Examples and Counterexamples in Spectral Graph Theory
%J Discussiones Mathematicae. Graph Theory
%D 2020
%P 637-662
%V 40
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a17/
%G en
%F DMGT_2020_40_2_a17
Stevanović, Dragan; Milosavljević, Nikola; Vukičević, Damir. A Few Examples and Counterexamples in Spectral Graph Theory. Discussiones Mathematicae. Graph Theory, Tome 40 (2020) no. 2, pp. 637-662. http://geodesic.mathdoc.fr/item/DMGT_2020_40_2_a17/

[1] R. Askey, Evaluation of Sylvester type determinants using orthogonal polynomials, in: Proceedings of the 4th International ISAAC Congress, Toronto, Canada, August 11–16, 2003, Advances in Analysis, H.G.W. Begehr et al. (Ed(s)), (World Scientific, 2005) 1–16. doi:10.1142/9789812701732 0001

[2] V. Brankov, P. Hansen and D. Stevanović, Automated conjectures on upper bounds for the largest Laplacian eigenvalue of graphs, Linear Algebra Appl. 414 (2006) 407–424. doi:10.1016/j.laa.2005.10.017

[3] L. Chen and Q. Huang, The existence of the graphs that have exactly two main eigenvalues (2016). arXiv:1609.05347

[4] S.M. Cioaba and D.A. Gregory, Principal eigenvectors of irregular graphs, Electron. J. Linear Algebra 16 (2007) 366–379. doi:10.13001/1081-3810.1208

[5] D.M. Cvetković, The main part of the spectrum, divisors and switching of graphs, Publ. Inst. Math. (Beograd) (N.S.) 23(37) (1978) 31–38.

[6] D. Cvetković, Discussing graph theory with a computer II. Theorems suggested by the computer, Publ. Inst. Math. (Beograd) (N.S.) 33(47) (1983) 29–33.

[7] D. Cvetković, On the 2-sum of three graphs. Variations on the graph product disconnectedness theme, Bull. Cl. Sci. Math. Nat. Sci. Math. 24 (1999) 107–117.

[8] D. Cvetković, M. Doob and H. Sachs, Spectra of Graphs—Theory and Application (Academic Press, New York, 1980).

[9] D. Cvetković and R. Lučić, A new generalization of the concept of the p-sum of graphs, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz. 302–319 (1970) 67–71.

[10] D. Cvetković, P. Rowlinson and S. Simić, An Introduction to the Theory of Graph Spectra (Cambridge University Press, Cambridge, 2009). doi:10.1017/CBO9780511801518

[11] K.Ch. Das and M.J. Nadjafi-Arani, On maximum Wiener index of trees and graphs with given radius, J. Comb. Optim. 34 (2017) 574–587. doi:10.1007/s10878-016-0092-y

[12] C. Elphick and T. Réti, On the relations between the Zagreb indices, clique numbers and walks in graphs, MATCH Commun. Math. Comput. Chem. 74 (2015) 19–34.

[13] E. Estrada, The communicability distance in graphs, Linear Algebra Appl. 436 (2012) 4317–4328. doi:10.1016/j.laa.2012.01.017

[14] X. Fan, Y. Luo and X. Gao, Tricyclic graphs with exactly two main eigenvalues, Open Math. 11 (2013) 1800–1816. doi:10.2478/s11533-013-0283-z

[15] M. Ghebleh, A. Kanso and D. Stevanović, Graph 6 Java: a researcher-friendly Java framework for testing conjectures in chemical graph theory, MATCH Commun. Math. Comput. Chem. 81 (2019) 737–770.

[16] E.M. Hagos, Some results on graph spectra, Linear Algebra Appl. 356 (2002) 103–111. doi:10.1016/S0024-3795(02)00324-5

[17] S. Hayat, J.H. Koolen, F. Liu and Z. Qiao, A note on graphs with exactly two main eigenvalues, Linear Algebra Appl. 511 (2016) 318–327. doi:10.1016/j.laa.2016.09.019

[18] O. Holtz, Evaluation of Sylvester type determinants using block-triangularization, in: Proceedings of the 4th international ISAAC congress, Toronto, Canada, August 11–16, 2003, Advances in Analysis, H.G.W. Begehr et al. (Ed(s)), (World Scientific, 2005) 395–405. doi:10.1142/9789812701732 0036

[19] Y. Hou, Z. Tang and W.C. Shiu, Some results on graphs with exactly two main eigenvalues, Appl. Math. Lett. 25 (2012) 1274–1278. doi:10.1016/j.aml.2011.11.025

[20] Y. Hou and F. Tian, Unicyclic graphs with exactly two main eigenvalues, Appl. Math. Lett. 19 (2006) 1143–1147. doi:10.1016/j.aml.2005.11.025

[21] Z. Hu, S. Li and C. Zhu, Bicyclic graphs with exactly two main eigenvalues, Linear Algebra Appl. 431 (2009) 1848–1857. doi:10.1016/j.laa.2009.06.022

[22] X. Huang, Q. Huang and L. Lu, Construction of graphs with exactly k main eigenvalues, Linear Algebra Appl. 486 (2015) 204–218. doi:10.1016/j.laa.2015.08.013

[23] T. Muir, The Theory of Determinants in the Historical Order of Development, 2nd Edition (Macmillan and Co., London, 1906).

[24] S. Mukwembi and T. Vetrík, Wiener index of trees of given order and diameter at most 6, Bull. Austral. Math. Soc. 89 (2014) 379–396. doi:10.1017/S0004972713000816

[25] V. Nikiforov, Walks and the spectral radius of graphs, Linear Algebra Appl. 418 (2006) 257–268. doi:10.1016/j.laa.2006.02.003

[26] J. Plesnik, On the sum of all distances in graph or diagraph, J. Graph Theory 8 (1984) 1–21. doi:10.1002/jgt.3190080102

[27] P. Rowlinson, The main eigenvalues of a graph: A survey, Appl. Anal. Discrete Math. 1 (2007) 445–471. doi:10.2298/AADM0702445R

[28] S. Simić, I. Gutman and V. Baltić, Some graphs with extremal Szeged index, Math. Slovaca 50 (2000) 1–15.

[29] L. Shi, On graphs with given main eigenvalues, Appl. Math. Lett. 22 (2009) 1870–1874. doi:10.1016/j.aml.2009.06.027

[30] W. So, Integral circulant graphs, Discrete Math. 306 (2006) 153–158. doi:10.1016/j.disc.2005.11.006

[31] D. Stevanović, When can the components of NEPS of connected bipartite graphs be almost cospectral?, Linear Algebra Appl. 311 (2000) 35–44. doi:10.1016/S0024-3795(00)00061-6

[32] D. Stevanović, On the components of NEPS of connected bipartite graphs, Linear Algebra Appl. 356 (2002) 67–78. doi:10.1016/S0024-3795(02)00322-1

[33] Z. Tang and Y. Hou, The integral graphs with index 3 and exactly two main eigenvalues, Linear Algebra Appl. 433 (2010) 984–993. doi:10.1016/j.laa.2010.04.025

[34] H. Täubig, Matrix Inequalities for Iterative Systems (CRC Press, Boca Raton, 2017). doi:10.1201/9781315166131