Обобщенный граф Петерсена

Граф Дюрера G (6, 2).

В теории графов, обобщенные графы Петерсена представляют собой семейство кубических графов, образованных соединением вершин правильного многоугольника с соответствующими вершинами звезды . многоугольник. Они включают граф Петерсена и обобщают один из способов построения графа Петерсена. Семейство обобщенных графов Петерсена было введено в 1950 г. Х. SM Coxeter, названный в 1969 году Марком Уоткинсом.

• 1 Определение и обозначения
• 2 Примеры
• 3 Свойства
  • 3.1 Изоморфизмы
  • 3.2 Обхват
  • 3.3 Хроматическое число и хроматический индекс
• 4 Ссылки

В обозначениях Уоткинса G (n, k) - это граф с набором вершин

$\{u\; 0,\; u\; 1,\; \dots ,\; Un\; -\; 1,\; v\; 0,\; v\; 1,\dots ,\; vn\; -\; 1\}\; \{\backslash \; displaystyle\; \backslash \; \{u\_\; \{0\},\; u\_\; \{1\},\; \backslash \; ldots,\; u\_\; \{n-1\},\; v\_\; \{0\},\; v\_\; \{\; 1\},\; \backslash \; ldots,\; v\_\; \{n-1\}\; \backslash \}\}$

и набор ребер

$\{uiui\; +\; 1,\; uivi,\; vivi\; +\; k\; |\; 0\; \le \; я\; \le \; N\; -\; 1\}\; \{\backslash \; displaystyle\; \backslash \; \{u\_\; \{i\}\; u\_\; \{i\; +\; 1\},\; u\_\; \{i\}\; v\_\; \{i\},\; v\_\; \{i\}\; v\_\; \{i\; +\; k\}\; |\; 0\; \backslash \; leq\; i\; \backslash \; leq\; n-1\; \backslash \}\}$

где нижние индексы следует читать по модулю n и k < n/2. Some authors use the notation GPG(n, k). Coxeter's notation for the same graph would be {n} + {n/k}, a combination of the символы Шлефли для правильного n-угольника и звездообразного многоугольника, из которого граф сформирован. Сам граф Петерсена - это G (5, 2) или {5} + {5/2}.

Любой обобщенный граф Петерсена также может быть построен из графа напряжений с двумя вершинами, двумя петлями и одним другим ребром.

Среди обобщенных графов Петерсена - n-призма G (n, 1), граф Дюрера G (6, 2), граф Мёбиуса-Кантора G (8, 3), додекаэдр G (10, 2), граф Дезарга G (10, 3) и граф Науру G (12, 5).

Четыре обобщенных графа Петерсена - 3-призма, 5-призма, граф Дюрера и G (7, 2) - входят в число семи графов, которые являются кубическими, 3-вершинно-связанные и хорошо покрытые (это означает, что все их максимальные независимые множества имеют одинаковый размер).

Один из трех гамильтоновых циклов в G (9, 2). Два других гамильтонова цикла в том же графе симметричны относительно поворота чертежа на 40 °.

Это семейство графов обладает рядом интересных свойств. Например:

• G (n, k) является вершинно-транзитивным (это означает, что он имеет симметрии, которые переводят любую вершину в любую другую вершину) тогда и только тогда, когда (n, k) = (10, 2) или k ≡ ± 1 (mod n).

• G (n, k) реберно-транзитивный (имеющий симметрии, которые переводят любое ребро в любое другое ребро) только в следующих семи случаях: (n, k) = (4, 1), (5, 2), (8, 3), (10, 2), (10, 3), (12, 5), (24, 5). Таким образом, эти семь графов являются единственными симметричными обобщенными графами Петерсена.

• G (n, k) является двудольным тогда и только тогда, когда n четно, а k нечетно.

• G (n, k) является графом Кэли тогда и только тогда, когда k ≡ 1 (mod n).

• G (n, k) является гипогамильтонианом, когда n конгруэнтно 5 по модулю 6 и k = 2, n - 2 или (n ± 1) / 2 (эти четыре выбора k приводят к изоморфным графам). Он также не является гамильтонианом, когда n делится на 4, по крайней мере, равно 8, и k = n / 2. Во всех остальных случаях он имеет гамильтонов цикл. Когда n сравнимо с 3 по модулю 6, G (n, 2) имеет ровно три гамильтонова цикла. Для G (n, 2) количество гамильтоновых циклов может быть вычислено по формуле, которая зависит от класса сравнения n по модулю 6 и включает числа Фибоначчи.

• Каждый обобщенный граф Петерсена является единицей граф расстояний.

Изоморфизмы

G (n, k) изоморфен G (n, l) тогда и только тогда, когда kl ≡ 1 (mod n).

Обхват

Обхват G (n, k) не менее 3 и не более 8, в частности:

$g\; (G\; (n,\; k))\; \le \; min\; \{8,\; k\; +\; 3,\; n\; gcd\; (n,\; k)\}.\; \{\backslash \; displaystyle\; g\; (G\; (n,\; k))\; \backslash \; leq\; \backslash \; min\; \backslash \; left\; \backslash \; \{8,\; k\; +\; 3,\; \{\backslash \; frac\; \{n\}\; \{\backslash \; gcd\; (n,\; k)\}\}\; \backslash \; right\; \backslash \}.\}$

Таблица с точными значениями обхвата:

Условие	Обхват
$n\; =\; 3\; k\; \{\backslash \; displaystyle\; n\; =\; 3k\}$	3
$n\; =\; 4\; k\; \{\backslash \; displaystyle\; n\; =\; 4k\}$	4
$к\; знак\; равно\; 1\; \{\backslash \; displaystyle\; к\; =\; 1\}$
$n\; =\; 5\; к\; \{\backslash \; displaystyle\; n\; =\; 5k\}$	5
$n\; =\; 5\; k\; /\; 2\; \{\backslash \; displaystyle\; n\; =\; 5k\; /\; 2\}$
$k\; =\; 2\; \{\backslash \; displaystyle\; k\; =\; 2\}$
$n\; =\; 6\; k\; \{\backslash \; displaystyle\; n\; =\; 6k\}$	6
$k\; =\; 3\; \{\backslash \; displaystyle\; k\; =\; 3\}$
$n\; =\; 2\; k\; +\; 2\; \{\backslash \; displaystyle\; n\; =\; 2k\; +\; 2\}$
$n\; =\; 7\; к\; \{\backslash \; displaystyle\; n\; =\; 7k\}$	7
$n\; =\; 7\; k\; /\; 2\; \{\backslash \; displaystyle\; n\; =\; 7k\; /\; 2\}$
$n\; =\; 7\; k\; /\; 3\; \{\backslash \; displaystyle\; n\; =\; 7k\; /\; 3\}$
$к\; =\; 4\; \{\backslash \; displaystyle\; k\; =\; 4\}$
$n\; =\; 2\; k\; +\; 3\; \{\backslash \; displaystyle\; n\; =\; 2k\; +\; 3\}$
$n\; =\; 3\; k\; \pm \; 2\; \{\backslash \; displaystyle\; n\; =\; 3k\; \backslash \; pm\; 2\}$
иначе	8

Хроматическое число и хроматический индекс

Будучи регулярными, согласно теореме Брукса их хроматическое число не может быть больше их степени. Обобщенные графы Петерсена являются кубическими, поэтому их хроматическое число может быть 2 или 3. Точнее:

$\chi \; (G\; (n,\; k))\; =\; \{2\; 2\; \mid \; n\; \wedge \; 2\; \nmid \; k\; 3\; 2\; \nmid \; n\; \vee \; 2\; \mid \; k\; \{\backslash \; displaystyle\; \backslash \; chi\; (G\; (n,\; k))\; =\; \{\backslash \; begin\; \{cases\}\; 2\; 2\; \backslash \; mid\; n\; \backslash \; land\; 2\; \backslash \; nmid\; k\; \backslash \backslash \; 3\; 2\; \backslash \; nmid\; n\; \backslash \; lor\; 2\; \backslash \; mid\; k\; \backslash \; end\; \{cases\}\}\}$

Где $\wedge \; \{\backslash \; displaystyle\; \backslash \; land\}$обозначает логическое И, а $\vee \; \{\backslash \; displaystyle\; \backslash \; lor\}$логическое ИЛИ. Например, хроматическое число $G\; (5,\; 2)\; \{\backslash \; displaystyle\; G\; (5,2)\}$равно 3.

• 

  Трехкратная раскраска графа Петерсена или $G\; (5,\; 2)\; \{\backslash \; displaystyle\; G\; (5,2)\}$

• 

  2-раскраска графа Дезарга или $G\; (10,\; 3)\; \{\; \backslash \; displaystyle\; G\; (10,3)\}$

• 

  Трехкратная раскраска графа Дюрера или $G\; (6,\; 2)\; \{\backslash \; displaystyle\; G\; (6,2)\}$

Петерсен граф, будучи снарком, имеет хроматический индекс, равный 4. Все остальные обобщенные графы Петерсена имеют хроматический индекс 3.

Обобщенный граф Петерсена G ( 9, 2) является одним из немногих графов, которые имеют только одну 3-краевую раскраску.

• 

  4-краевую раскраску графа Петерсена или $G\; (5,\; 2)\; \{\backslash \; displaystyle\; G\; (5,2)\}$

• 

  Трехреберная раскраска графа Дюрера или $G\; (6,\; 2)\; \{\backslash \; displaystyle\; G\; (6,2)\; \}$

• 

  3-краевая раскраска додекаэдра или $G\; (10,\; 2)\; \{\backslash \; displaystyle\; G\; (10,2)\}$

• 

  3-краевая раскраска граф Дезарга или $G\; (10,\; 3)\; \{\backslash \; displaystyle\; G\; (\; 10,3)\}$

• 

  Трехреберная раскраска графа Науру или $G\; (12,\; 5)\; \{\backslash \; displaystyle\; G\; (12,5)\}$

Граф Петерсена сам по себе является единственным обобщенным графом Петерсена, который не является 3- раскрашиваемым по ребрам.