On the distance spectrum of a cycle. (English) Zbl 0605.05029

Graovac, Ante; Jashari, Gani; Strunje, Mate

Apl. Mat. 30, 286-290 (1985).

For a graph G with n vertices the distance matrix \(D=D(G)\) is a square matrix of order n whose elements are defined by: \(d_{rr}=0\) and \(d_{rs}\) \(=\) the length of the shortest path between vertices r and s. The collection of the eigenvalues \(x_ j\), \(j=1,2,...,n\), of D is called the distance spectrum of G. The full treatment of the distance spectrum of a cycle \(C_ n\) is given in the paper.
In the case of an even cycle, \(C_{2k}\), among 2k eigenvalues of \(D(C_{2k})\) there are k negative eigenvalues, the zero eigenvalue whose degeneracy equals (k-1), and only one positive eigenvalue which is equal to \(k^ 2\). Among k negative eigenvalues there are [k/2] mutually distinct, doubly degenerate eigenvalues, and in addition, for k being an odd number, there is also a single negative eigenvalue which is equal to -1.
In the case of an odd cycle, \(C_{2k+1}\), among \(2k+1\) eigenvalues of \(D(C_{2k+1})\) there are k mutually distinct, doubly degenerate negative eigenvalues and only one positive eigenvalue which is equal to \(k(k+1)\). The explicit formulae for the distance spectrum of cycle are also presented.

MSC:

05C50	Graphs and linear algebra (matrices, eigenvalues, etc.)
05C38	Paths and cycles

Keywords:

cycle graph; eigenvalues; distance spectrum; even cycle; odd cycle

References:

[1]	P. Křivka N. Trinajstič: On the distance polynomial of a graph. Aplikace matematiky 28 (1983), 357-363.
[2]	O. E. Polanský N. N. Tyutyulkov: Structural graphs of regular polymers and their properties. Match (Mülheim/Ruhr) 3 (1977), 149-223. · Zbl 0389.05053
[3]	A. Graovac I. Gutman M. Randič N. Trinajstič: On structural features characterizing conductivity in polymeric conjugated hydrocarbons. Colloid & Polymer Sci. 255 (1977), 480-487.
[4]	O. E. Polansky: Über ungesättige Monocyclen mit durchlaufender Konjugation, 2. Mitt.: Berechnung der Elektronenstruktur mit Hilfe der einfachen LCAO - MO Methode und allgemeine gruppentheoretische Betrachtungen. Mh. Chem. 91 (1960), 916 - 962.