Том 7, серия 2, номер 2, 2000 г., Стр. 60-73

УДК 519.17
Л. С. Мельников, А. А. Добрынин
Построение трехсвязных графов с совпадающими цепными матрицами слоев

Аннотация:
Цепная матрица слоев (цепная степенная последовательность) $\tau(G)$ содержит количественную информацию о цепях, начинающихся в вершинах обыкновенного связного неориентированного графа $G$. Под длиной цепи графа понимается число ее ребер. Элемент $\tau_{ij}$ матрицы равен количеству всех простых цепей длины $j$, начинающихся в вершине $v_i$. Предлагается метод для построения пар неизоморфных графов без точек сочленения с совпадающими цепными матрицами слоев. Построены бесконечные семейства таких графов, в том числе наименьшие известные графы, обладающие различными свойствами. Показано, что для любого $p\geqslant 18$ существуют как планарные, так и непланарные двусвязные и трехсвязные $p$-вершинные графы с совпадающими цепными матрицами слоев. Сформулированы аналогичные утверждения для $r$-регулярных графов. Например, для любого $p\geqslant 26(p\geqslant 30)$ существуют неизоморфные трехсвязные непланарные (планарные) $p$-вершинные кубические графы с совпадающими цепными матрицами слоев. Приводится несколько открытых вопросов.
Ил. 6, библиогр. 20.

Мельников Л. С. ¹
Добрынин А. А. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: omeln@math.nsc.ru, dobr@math.nsc.ru

Статья поступила 30 июня 2000 г.