Circulant matrices and the spectrum of de Bruijn graphs
Abstract
The block structure of k-circulant matrices A of order n(k≥2,k|n) is investigated and statements, enabling to reduce a series of problems with the matrices A+AT to analogous problems with matrices of lower order, namely the blocks of the matrices A and AT, are proved. The spectrum and the number of spanning trees of an undirected de Bruijn graph are obtained.
References
Воеводин В. В.,Тыртышников Е. Е. Вычислительные процессы с теплицевыми матрицами. –М.: Наука, 1987.– 320 с.
Ablow С.М., Brenner J.L. Roots and canonical forms for circulant matrices // Trans. Amer. Math. Soc– 1963.–107, N 2.– P. 360–376.
Де Брейн H. Г. Одна комбинаторная задача // Киберн. сб. – 1969.–Вып. 6 – С.33–40.
Кратко М. И., Строк В. В. Последовательности де Брейна с ограничениями // Вопросы кибернетики. Комбинаторный анализ и теория графов.–М.: Наука, 1980.–С.80–84.
Цветкович Д., Дуб М., Захс X. Спектры графов. Теория и применение.– Киев: Наук. думка, 1984.–384 с.
Джоунс У ..Трон В. Непрерывные дроби.–М.: Мир, 1985.–416с.
Риордан Дж. Комбинаторные тождества.–М.: Мир, 1982.–256 с.
Gutman I. Characteristic and matching polynomials of some compound graphs // Publ. Inst. Math.–1980.–27.–P. 61–66.
Raut G. Spectrul arborilor k–ary completi // Studii si cercetari matematice.– 1983.– 35, N 3.– P. 183–188.
Хоменко H. П., Строк В. В. Т–факторизация GB–графов // Теория графов.– Киев: Ин–т математики АН УССР, 1977.–С.135–142.
Strok V., Yaworski Е. Spectrum of the binary de Bruijn graph // XVII Yugoslav. Symp. Oper. Res. (Dubrovnik–Kupari; 9–12.10.1990).–Beograd: Naucna Knjiga, 1990.–P. 165–168.
Copyright (c) 1992 V.V. Strok

This work is licensed under a Creative Commons Attribution 4.0 International License.