Циркулянтные матрицы и спектр графов Де Брейна

V.V. Strok

V.V. Strok Ин-т математики АН Украины, Киев

Abstract

The block structure of $k$-circulant matrices $A$ of order $n(k\geq 2, k| n)$ is investigated and statements, enabling to reduce a series of problems with the matrices $A+A^T$ to analogous problems with matrices of lower order, namely the blocks of the matrices $A$ and $A^T$, 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.

Circulant matrices and the spectrum of de Bruijn graphs

Abstract

References