About one family of exact 2-extensions of tournaments.pdf Граф H называется точным (вершинным) к-расширением графа G, если граф Gизоморфен каждому подграфу H , получающемуся путем удаления любых его к вершини всех связанных с ними дуг (ребер). Основные определения в работе используютсяв соответствии с [1].Циркулянтом называется n-вершинный граф G, такой, что, если его вершинамприписать метки от 0 до n - 1, то из вершины i в вершину j будет идти дуга тогдаи только тогда, когда (i - j ) mod n E S , где S - это некоторое подмножество множества Zn \ {0}. Группа автоморфизмов циркулянта G = (V, а) транзитивна, то естьVv,u Е V 3^ Е Aut(G) : 1. Это семейство вполне несвязных и полных неориентированных графов [2],а также семейство транзитивных турниров для случая диграфов [3].Кроме того, особый интерес представляют графы, имеющие точное 1- и 2-расширение,но не имеющие точного 3-расширения, приведенные в работе [4]. Удалось показать,что графы с таким свойством обязательно должны быть турнирами. Опишемсемейство турниров, к которому подходят все указанные в работе [4] представителис таким свойством.Рассмотрим р-вершинный граф G = (V, а), где p - простое и больше 2. Из вершиныVi в вершину Vj есть дуга только в том случае, когда (j - i) - квадратичныйвычет по модулю р, то есть по теореме Эйлера (j - i)(p-1)/2 = 1 (mod р). Обозначимпостроенный граф через Tp.Рассмотрим отображение на множестве вершин графа Tp, при котором v переходитв V(i+1) mod p. Пусть в исходном графе есть дуга из v в Vj; после отображениябудем иметь Vj ^ V(j+1) mod p, v ^ V(i+1) modp. В полученном графе существует дуга(v(i+1) modp, V(j+1) mod p), если выполняется соотношение(j + 1 - (i + 1))(p-1)/2 = (j - i)(p-1)/2 = 1 (mod p).Таким образом, очевидно, что данное отображение является автоморфизмом графаTn. Рассматриваемый граф является вершинно-симметрическим графом с цикли-чески-симметричной (циркулянтной) матрицей отношения смежности. Известно, чтотакие графы являются точными 1-расширениями [4].Из работы [5] известно, что при р = 4n + 3 граф такого вида всегда являетсятурниром.Удалось доказать следующее утверждение.Теорема 1. Построенные по описанной схеме турниры Tn являются точными вершинными1- и 2-расширениями для подходящих турниров.С помощью компьютерного поиска удалось установить, что для n = 7, 11, 19, 23,31, 43, 47, 59 турнир Tn не является точным вершинным 3-расширением ни для какогоорграфа.

Скачать электронную версию публикации