Граф - петерсено
Cтраница 2
Имеется взаимно однозначное отображение П из Р2 в PI, инвариантное относительно действия указанной выше группы, такое, что Р % U ПРа индуцирует граф Петерсена Р, такой, что три вершины из Р ] С имеют единственного соседа. [16]
Правило 1 является как раз тем, с которым мы встретились в примерах 1 и 2, и, таким образом, мы можем предположить существование связи между графом Петерсена и реакционным графом ГЛ гомотетраэдранильного катиона. Отображая каждую вершину i jk графа, показанного на рис. 14, в вершину jk графа, изображенного на рис. 5, мы устанавливаем гомоморфизм между двумя этими графами. [17]
Имеется 105 таких специальных графов Петерсена, причем каждый может быть представлен в виде PI U Р2 шестью способами. Каждый из графов Петерсена содержит 6 паросо-четаний, и, таким образом, мы находим требуемые 630 прямых. [18]
Снарком будем называть связный кубический граф, который не имеет реберной раскраски и бонда, содержащего меньше четырех ребер. Простейшим примером снарка является граф Петерсена. Если граф не допускает реберной раскраски, но имеет бонд В из двух или трех ребер, то этот граф легко редуцируется к меньшему, являющемуся остаточным графом бонда В. Указанный случай очень прост и мы его детально не рассматриваем. [19]
Примером реберно-симметрического графа, который также вершинно-симметричен и двудолен, служит многоугольник с шестью вершинами. Икосаэдр, додекаэдр и граф Петерсена дают примеры реберно-симметрических графов, которые являются вершинно-симметрическими, но не двудольными. Наконец, как показал Фолкман [1], не все регулярные реберно-симметрические графы вершинно-симметричны. [20]
Замечательная спорадическая частичная геометрия была построена Хэмерсом в [35] с использованием графа Хоффмана - Синглтона. Этот граф содержит 525 графов Петерсена в качестве индуцированных подграфов. Пусть ребра графа Хоффмана - Синглтона будут точками геометрии и определим прямые как 1-факторы в специальных подграфах Петерсена. [21]
Замечательная спорадическая частичная геометрия была построена Хэме. Этот граф содержит 525 графов Петерсена в качестве индуцированных подграфов. Определяется специальный класс из 105 таких графов. Пусть ребра графа Хоффмана - Синглтона будут точками геометрии и определим прямые как 1-факторы в специальных подграфах Петерсена. [22]
Для 2) известно много примеров. Имеется единственный пример с s 1 - граф Петерсена. [23]
 |
Возможные варианты для непланарных подграфов. [24] |
Граф G называется стягиваемым к графу Я, если Н можно получить из G с помощью некоторой последовательности элементарных стягиваний. Например, как показано на рис. 11.12, аи б, граф Петерсена стягивается к / С5 в результате стягивания в новую вершину ш - любого из пяти ребер - уг, соединяющих пятиугольник с пентаграммой. [25]
Более сложный пример показан на рис. IV. Результирующий граф, изображенный на этом рисунке, известен под названием графа Петерсена. [26]
Коллинеации конфигурации D на себя образуют группу. Очевидно, исследование этой группы может производиться в терминах группы автоморфизмов графа Петерсена. Мы утверждаем, что имеется 12 таких циклов, составляющих 6 пар по два не пересекающихся между собой цикла. Вершины этих непересекающихся циклив попарно соединены ( непересекающимися) ребрами. [27]
Сначала мы приводим очень простую границу для 0 ( G), которая применима к любым регулярным графам. Затем вычисляем границу Ловаса для двух бесконечных семейств графов: циклических графов CN и квадратично-вычет-ных графов Qp, которые являются двумя различными обобщениями графа Сб - Нам не удалось вычислить емкости графов С для нечетных Л /, N 7, но для любого простого р, р гэ 1 mod 4, мы покажем, что 0 ( QP) д / Р - Далее рассматриваются три специальных графа: граф Петерсена, графы икосаэдра и додекаэдра. Мы также рассматриваем очень интересный регулярный граф на 7 вершинах. [28]
Наиболее значительным вкладом в теорию графов, который был сделан в этой статье, было, несомненно, описание кубического непланарного графа, не имеющего мостов, который нельзя разложить на три непересекающихся совершенных паросочетания. Этот граф, заслуженно называемый графом Петерсена, является, возможно, одним из наиболее знаменитых реально существующих ( или наиболее пресловутых - это зависит от мнения читателя. [29]
Очевидно, что целочисленная разрешимость системы (7.4.4) является необходимым условием для реберной r - раскрашиваемости графа G. С другой стороны, Сеймор доказал, что если граф G является 3-регулярным, реберно 3-связным и не содержит никакого подразбиения графа Петерсена, то соответствующая ему система (7.4.4) имеет целочисленное решение. [30]
Страницы: 1 2 3