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

В.В. Строк

В.В. Строк Ин-т математики АН Украины, Киев

Анотація

Вивчається блочна структура $k$-циркулянтних матриць $A$ порядку $n(k\geq 2, k| n)$ та доведено твердження, що дозволяють ряд задач з матрицями $A+A^T$ зводити до аналогічних задач з матрицями меншого порядку — блоками матриць $A$ і $A^T$. Одержано спектр та число фактор-дерев неорієнтованого графа де Брьойна.

Посилання

Воеводин В. В.,Тыртышников Е. Е. Вычислительные процессы с теплицевыми матрицами. –М.: Наука, 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.