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

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.


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


[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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.