Граф Петерсена O3 = KG5,2 вершин = ребер = диаметр = n − 1[1][2] обхват= 3 если n = 2, 5 если n = 3, 6 если n > 3[3] свойства = дистанционно-транзитивен обозначение = OnНечётный граф O4 = KG7,3
Нечётный граф On имеет одну вершину для каждого из (n − 1)-элементных подмножеств множества из (2n − 1) элементов. Две вершины связаны ребром в том и только в том случае, если соответствующие подмножества не пересекаются[4]. Так, On — это граф КнесераKG(2n − 1,n − 1), O2 — треугольник, а O3 — знакомый граф Петерсена.
Обозначение On для этих графов предложено Норманом Биггсом в 1972 году[10]. Биггс и Тони Гардинер[англ.] объясняют название нечётных графов в неопубликованной монографии 1974 года — каждому ребру нечётного графа можно сопоставить единственный элемент X, который является «odd man out» (что можно перевести как «игрок без партнёра выходит из игры»), то есть элемент не принадлежит ни одному другому подмножеству, связанному с вершинами, инцидентными данному ребру[11][12].
Свойства
Нечётный граф On является регулярным графом степени n. Он имеет вершин и рёбер. Таким образом, число вершин для n = 1, 2,… будет
Если две вершины в On соответствуют множествам одинакового размера, отличающихся k элементами, то можно получить из первого второе за 2k шагов, на каждом шаге убирая или добавляя один элемент. Если 2k < n, то это кратчайший путь. В противном случае можно найти более короткий путь этого типа, если начать с дополнительного ко второму множества, а затем получить второе множество, сделав ещё один шаг. Таким образом, диаметр графа On равен n − 1[1][2].
Любой нечётный граф 3-дужно-транзитивен — любой ориентированный трёхрёберный путь в нечётном графе может быть переведён в любой такой же путь с помощью симметрии графа[13].
Нечётные графы дистанционно-транзитивны, поскольку они дистанционно-регулярны[2]. Как дистанционно-регулярные графы, они однозначно определяются их массивом пересечений — никакой другой дистанционно-регулярный граф не может иметь те же самые параметры, что и нечётный граф[14].
Однако вопреки высокой степени симметрии, нечётные графы On для n > 2 никогда не являются Графами Кэли[15].
Нечётные графы с n ≥ 3 имеют обхват шесть. Однако, хотя они и не являются
двудольными графами, их нечётные циклы намного длиннее, а именно нечётный граф On имеет нечётный обхват 2n − 1. Если n-регулярный граф имеет диаметр n − 1, нечётный обхват 2n − 1 и только n различных собственных значений, он должен быть дистанционно-регулярным. Дистанционно-регулярные графы диаметра n − 1 и нечётного обхвата 2n − 1 известны как обобщённые нечётные графы и включают складные кубические графы[англ.] так же, как и сами нечётные графы[5].
Независимые множества и раскраска вершин
Пусть On — нечётный граф, определённый на (2n − 1)-элементных подмножествах множества X, и пусть x — элементы множества X. Тогда среди вершин On ровно вершин соответствуют множествам, которые содержат x. Поскольку все эти множества содержат x, они не являются непересекающимися, и образуют независимое множество графа On. Таким образом, On имеет 2n − 1 различных независимых множеств размера . Из теоремы Эрдёша – Ко – Радо[англ.] следует, что это максимальные независимые множеств графа On. Таким образом, число независимости графа On равно Более того, любое максимальное независимое множество должно иметь этот вид, так что On имеет в точности 2n − 1 максимальных независимых множеств[2].
Если I — максимальное независимое множество, образованное множеством содержащим элемент x, то дополнение множества I — это множество вершин, не содержащих x. Это дополнение порождаетпаросочетание в G. Каждая вершина независимого множества смежна n вершинам паросочетания, а каждая вершина паросочетания смежна n − 1 вершинам независимого множества[2]. Ввиду этого разложения и ввиду того, что нечётные графы не являются двудольными, они имеют хроматическое число равное трём — вершинам максимального независимого множества можно назначить один цвет, а два других цвета получим из паросочетания, порождённого дополнением.
Рёберная раскраска
По теореме Визинга число цветов, необходимых для раскраски рёбер нечётного графа On, равно либо n, либо n + 1, и в случае графов Петерсена O3 оно равно n + 1. Если n — степень двух, число вершин в графе нечётно, откуда опять следует, что число цветов в рёберной раскраске равно n + 1[16]. Однако O5, O6 и O7 могут быт раскрашены n цветами[2][16].
Биггс[10] объясняет эту задачу следующей историей: одиннадцать футболистов в придуманном городе Кроам хотят образовать пары команд для мини-футбола (один человек остаётся судить встречу) всеми 1386 различными способами и хотят составить расписание игр между всеми парами, при этом шесть игр каждой команды должны играться в разные дни недели, при отсутствии игр по воскресеньям. Возможно ли это? В этой истории каждая игра представляет ребро O6, все дни представлены цветами, а рёберная раскраска в 6 цветов графа O6 даёт расписание.
Нечётные графы и гамильтоновы графы
Граф Петерсена O3 — это хорошо известные негамильтоновы графы, но было показано, что графы от O4 до O14 содержат гамильтоновы циклы[8][17][18][19]. Более строго, комбинируя задачи поиска гамильтоновых циклов и рёберной раскраски, можно разбить рёбра графа On (для n = 4, 5, 6, 7) на ближайшее снизу целое от (n/2) гамильтоновых циклов. Если n нечётно, оставшиеся рёбра образуют совершенное сочетание[2][16]. Для n = 8, нечётное число вершин в On не позволяет раскрасить рёбра в 8 цветов, но не закрывает возможность разложения на четыре гамильтоновых цикла.
Гипотеза Ловаса о гамильтоновом цикле предполагает, что каждый нечётный граф имеет гамильтонов путь и что каждый нечётный граф On с n ≥ 4 имеет гамильтонов цикл.
Примечания
↑ 12Norman L. Biggs. Automorphic graphs and the Krein condition // Geometriae Dedicata. — 1976. — Вып. 5. — С. 117—127. — doi:10.1007/BF00148146.
↑ 12Edwin Van Dam, Willem H. Haemers. An Odd Characterization of the Generalized Odd Graphs. — 2010.
↑ 12A. Kowalewski. W. R. Hamilton's Dodekaederaufgabe als Buntordnungproblem // Sitzungsber. Akad. Wiss. Wien (Abt. IIa). — 1917. — Т. 126. — С. 67—90, 963—1007. Как цитировано у Биггса (Biggs 1979).
↑Alexandru T. Balaban, D. Fǎrcaşiu, R. Bǎnicǎ. Graphs of multiple 1, 2-shifts in carbonium ions and related systems // Rev. Roum. Chim.. — 1966. — Т. 11. — С. 1205.
↑ 12Alexandru T. Balaban. Chemical graphs, Part XIII: Combinatorial patterns // Rev. Roumaine Math. Pures Appl.. — 1972. — Т. 17. — С. 3—16.
↑Arif Ghafoor, Theodore R. Bashkow. A study of odd graphs as fault-tolerant interconnection networks // IEEE Transactions on Computing. — 1991. — Т. 40, вып. 2. — С. 225—232. — doi:10.1109/12.73594.
↑ 12Norman Biggs.Research Problems // American Mathematical Monthly. — 1972. — Т. 79, вып. 9. — С. 1018—1020. — JSTOR2318076.
↑Andries Brouwer, Arjeh M. Cohen, A. Neumaier. Distance-regular Graphs. — 1989. — ISBN 0-387-50619-5.
↑László Babai.Handbook of Combinatorics / Ronald L. Graham, Martin Grötschel, László Lovász. — North-Holland, 1995. — Т. I. — С. 1447—1540. Архивировано 11 июня 2010 года.
↑Aeryung Moon. Characterization of the odd graphs Ok by parameters // Discrete Mathematics. — 1982. — Т. 42, вып. 1. — С. 91—97. — doi:10.1016/0012-365X(82)90057-7.
↑C. D. Godsil. More odd graph theory // Discrete Mathematics. — 1980. — Т. 32, вып. 2. — С. 205—207. — doi:10.1016/0012-365X(80)90055-2.
↑ 123Guy H. J. Meredith, E. Keith Lloyd. The footballers of Croam // Journal of Combinatorial Theory, Series B. — 1973. — Т. 15. — С. 161—166. — doi:10.1016/0095-8956(73)90016-6.
↑Guy H. J. Meredith, E. Keith Lloyd. Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972). — Southend: Inst. Math. Appl, 1972. — С. 229—236.
↑Michael Mather. The Rugby footballers of Croam // Journal of Combinatorial Theory, Series B. — 1976. — Т. 20. — С. 62—63. — doi:10.1016/0095-8956(76)90066-6.
↑Ian Shields, Carla D. Savage. A note on Hamilton cycles in Kneser graphs // Bulletin of the Institute for Combinatorics and Its Applications. — 2004. — Т. 40. — С. 13—22.