ON THE SPECTRA OF CYCLES AND PATHS

Year 2019, Volume: 9 Issue: 3, 571 - 580, 01.09.2019

F. Çelik I. N. Cangül

Abstract

Energy of a graph was dened by E. Huckel as the sum of absolute values of the eigenvalues of the adjacency matrix during the search for a method to obtain approximate solutions of Schrodinger equation which include the energy of the corresponding system for a class of molecules. The set of eigenvalues is called the spectrum of the graph and the spectral graph theory dealing with spectrums is one of the most interesting subareas of graph theory. There are a lot of results on the energy of many graph types. Two classes, cycles and paths, show serious dierences from others as the eigenvalues are trigonometric algebraic numbers. Here, we obtain the polynomials and recurrence relations for the spectral polynomials of these two graph classes. In particular, we prove that one can obtain the spectra of C2n and P2n+1 without detailed calculations just in terms of the spectra of Cn and Pn, respectively.

Keywords

Spectrum of a graph, graph energy, recurrence relation, path, cycle

References

• C. Adiga, Z. Khoshbakht, I. Gutman, (2007), More graphs whose energy exceeds the number of vertices. Iranian Journal of Mathematical Sciences and Informatics, 2 (2), (2007), 57-62.
• J. M. Aldous, R. J. Wilson, (2004), Graphs and Applications, The Open University, UK.
• R. Balakrishnan, K. Ranganathan, (2012), A Textbook of Graph Theory. (Second edn.), Springer, New York.
• C. Berge, (2001), The Theory of Graphs, Fletcher and Son Ltd., UK.
• N. L. Biggs, E. K. Lloyd, R. J. Wilson, (2001), Graph Theory, pp. 1736-1936, Oxford University Press, London.
• B. Bollobas,(1998), Graduate Texts in Mathematics, Modern Graph Theory, Springer, New York.
• J. A. Bondy, U. S. R. Murty, (1998), Graph Theory, Springer, New York.
• A. E. Brouwer, W. H. Haemers, (2012), Spectra of Graphs, Springer, New York.
• F. Celik, (2016), Graphs and Graph Energy, PhD Thesis, pp. 65, Uludag University, Bursa.
• F. Celik, I. N. Cangul, (2017), Recurrence Relations on Spectral Polynomials of Some Graphs and Graph Energy, Adv. Stud. Contemp. Maths, 27, 1, (preprint).
• W. Chen, (1976), Applied Graph Theory, North-Holland Publishing Company, New York.
• D. Cvetkovic, M. Doob, H. Sachs, (1995), Spectra of GraphsTheory and Applications, (Third edn.), Academic Press, Heidelberg.
• L. R. Foulds, (1992), Graph Theory Applications, Springer, New York.
• M. C. Golumbic, I. B. Hartman, (2012), Graph Theory, Combinatorics and Algorithms, Springer, New York.
• I. Gutman, (1978), The Energy of a Graph, Ber. Math. Statist. Sekt. Forshungsz. Graz, 103, pp. 1-22.
• F. Harary, (1994), Graph Theory, Addison-Wesley, USA.
• J. M. Harris, J. L. Hirst, M. J. Mossinghoff, (2008), Combinatorics and Graph Theory, Springer, New York.
• X. Li, Y. Shi, I. Gutman, (2012), Graph Energy, Springer, New York.
• V. Nikiforov, (2007), The energy of graphs and matrices, J. Math. Anal. Appl. 326, pp. 1472-1475.
• H. B. Walikar, H. S. Ramane, P. R. Hampiholi, On the energy of a graph in: R. Balakrishnan, H. M. Mulder, A. Vijayakumar (Eds.), (1999), Graph Connections, Allied Publishers, New Delhi, pp. 120-123.
• D. B. West, (1996), Introduction to Graph Theory, Upper Saddle River, Prentice Hall.