Серый график

Серый график
Серый график
Названный в честь	Мэрион Кэмерон Грей
Вершины	54
Края	81 год
Радиус	6
Диаметр	6
Обхват	8
Автоморфизмы	1296
Хроматическое число	2
Хроматический индекс	3
Толщина книги	3
Номер очереди	2
Характеристики	Кубический полусимметричный гамильтониан Двудольный
Таблица графиков и параметров

В математической области теории графов , то серый график представляет собой неориентированный двудольный граф с 54 вершинами и 81 ребрами . Это кубический граф : каждая вершина касается ровно трех ребер. Он был открыт Мэрион С. Грей в 1932 году (не опубликовано), а затем независимо обнаружен Бауэром в 1968 году в ответ на вопрос, заданный Джоном Фолкманом в 1967 году. Граф Грея интересен как первый известный пример кубического графа, обладающего алгебраическим свойством является ребром, но не транзитивным по вершине (см. ниже).

Граф Грея имеет хроматическое число 2, хроматический индекс 3, радиус 6 и диаметр 6. Он также является неплоским графом с 3- вершинно-связными и 3- реберно-связными .

Строительство [ править ]

График с расположенными вершинами, раскрашенными по их положению в сетке

График Грея может быть построен ( Bouwer 1972 ) из 27 точек сетки 3 × 3 × 3 и 27 линий, параллельных осям, проходящих через эти точки. Этот набор точек и линий образует проективную конфигурацию : каждая точка имеет ровно три линии, и каждая линия имеет ровно три точки на ней. Граф Грея - это граф Леви этой конфигурации; у него есть вершина для каждой точки и каждой линии конфигурации и ребро для каждой пары точки и линии, которые касаются друг друга. Эта конструкция обобщает (Bouwer 1972) на любую размерность n ≥ 3, давая n-валентный граф Леви с алгебраическими свойствами, аналогичными свойствам графа Грея. В (Monson, Pisanski, Schulte, Ivic-Weiss 2007) граф Грея появляется как другой вид графа Леви для ребер и треугольных граней некоторого локально тороидального абстрактного регулярного 4-многогранника. Таким образом, он является первым в бесконечном семействе подобных построенных кубических графов. Как и в случае с другими графами Леви, это двудольный граф , вершины которого соответствуют точкам на одной стороне двудольного раздела, а вершины соответствуют линиям на другой стороне.

Марушич и Писанский (2000) предлагают несколько альтернативных методов построения графа Грея. Как и в любом двудольном графе, здесь нет циклов нечетной длины , а также нет циклов с четырьмя или шестью вершинами, поэтому обхват графа Грея равен 8. Простейшая ориентированная поверхность, в которую можно вложить граф Грея, имеет род 7 ( Марушич, Писански и Уилсон, 2005 ).

Граф Грея является гамильтоновым и может быть построен из обозначения LCF :

${\ displaystyle [-25,7, -7,13, -13,25] ^ {9}. \}$

Как гамильтонов кубический граф, он имеет хроматический индекс три.

Алгебраические свойства [ править ]

Группа автоморфизмов графа Грея - это группа порядка 1296. Она действует транзитивно на ребрах графа, но не на его вершинах: существуют симметрии, переводящие каждое ребро в любое другое ребро, но не переводящие каждую вершину в любую другую вершину. Вершины, которые соответствуют точкам базовой конфигурации, могут быть симметричными только другим вершинам, которые соответствуют точкам, а вершины, которые соответствуют линиям, могут быть симметричными только другим вершинам, которые соответствуют линиям. Следовательно, граф Грея - это полусимметричный граф , минимально возможный кубический полусимметричный граф.

Характеристический многочлен графа Грея равен

${\ displaystyle (x-3) x ^ {16} (x + 3) (x ^ {2} -6) ^ {6} (x ^ {2} -3) ^ {12}. \}$

Ссылки [ править ]

• Bouwer, IZ (1968), "Ребро , но не вершина транзитивен кубический граф", Канадский математический вестник , 11 (4): 533-535, DOI : 10,4153 / КМФ-1968-063-0.
• Бауэр, И.З. (1972), «На ребрах, но не на вершинных транзитивных регулярных графах», Журнал комбинаторной теории, серия B , 12 : 32–40, DOI : 10.1016 / 0095-8956 (72) 90030-5.
• Фолкман, Дж. (1967), «Регулярные линейно-симметричные графы», Журнал комбинаторной теории , 3 (3): 533–535, DOI : 10.1016 / S0021-9800 (67) 80069-3.
• Марушич, Драган ; Pisanski, Tomaž (2000), "Серый граф вновь", Журнал теории графов , 35 : 1-7, DOI : 10.1002 / 1097-0118 (200009) 35: 1 <1 :: АИД-JGT1> 3.0.CO; 2-7.
• Марушич, Драган ; Писанский, Томаж ; Уилсон, Стив (2005), "род Грея графа 7", Европейский журнал Комбинаторика , 26 (3-4): 377-385, DOI : 10.1016 / j.ejc.2004.01.015.
• Monson, B .; Писанский, Т .; Schulte, E .; Ивич-Вайс, А. (2007), «Полусимметричные графы из многогранников», Журнал комбинаторной теории, серия A , 114 (3): 421–435, arXiv : math / 0606469 , doi : 10.1016 / j.jcta.2006.06. 007 , S2CID  10203794

Внешние ссылки [ править ]

• Вайсштейн, Эрик В. «Серый график» . MathWorld .
• Серый график - это самый маленький график такого рода , от MathWorld .