Однородный граф - степень
Cтраница 1
Однородный граф степени г. Однородным графом степени г является граф, степени всех вершин которого одинаковы и равны г. В случае ориентированных графов требуется, чтобы степени р и р были одинаковы во всех вершинах и равны друг другу. [1]
 |
Эйлеров граф и эйлеров диграф. [2] |
Каждый однородный граф степени 1 имеет четное число 2п вершин, соединенных ребрами так, что получаются п связных компонент. Каждый однородный граф степени 2 содержит элементарный цикл в каждой своей компоненте. [3]
Хроматическое число связного однородного графа степени 2 с п вершинами равно двум, если п четно; 3, если п нечетно. [4]
Однородный граф степени г. Однородным графом степени г является граф, степени всех вершин которого одинаковы и равны г. В случае ориентированных графов требуется, чтобы степени р и р были одинаковы во всех вершинах и равны друг другу. [5]
Теорема 7.5.5. Если G - однородный граф степени m, TO G имеет паросочетание), в котором не участвуют произвольно заданные m - 1 ребер. [6]
Очевидно, что если G - однородный граф степени 2, то он распадается на совокупность не связанных между собой простых циклов. Рассмотрим каждый такой простой цикл Z по отдельности. Поэтому L ( Z) представляет собой простой цикл той же длины г. Но любые два простых цикла одинаковой длины, очевидно, изоморфны. [7]
Те о ре л а 7.5.5. Если G - однородный граф степени, m, TO G имеет паросочетание1), в котором не участвуют произвольно заданные m - 1 ребер. [8]
В связи с группами автоморфизмои графов следует также упомянуть о некоторых интересных исследованиях однородных графов степени Я, которые провел Татт. Он рассмотрел задачу о нахождении таких графов, в которых любая ориентированная простая цепь длины s может быть переведена автоморфизмом в любую другую такую простую цепь. [9]
Если 8 ( v) k для всех вершин графа, то граф называется однородным графом степени k или просто k - od - нородным. [10]
Следующая теорема, которая в основном принадлежит Тейту и рассмотрена в работах [3] и [34], связывает задачу о раскраске четырьмя цветами граней плоского однородного графа степени 3 с задачей о раскраске его ребер тремя цветами. [11]
 |
Эйлеров граф и эйлеров диграф. [12] |
Каждый однородный граф степени 1 имеет четное число 2п вершин, соединенных ребрами так, что получаются п связных компонент. Каждый однородный граф степени 2 содержит элементарный цикл в каждой своей компоненте. [13]
Подграф, определяемый ребрами, окрашенными в цвета 1 и 2, является однородным степени 2, следовательно, его грани могут быть раскрашены. Подобным образом однородный граф степени 2, определенный ребрами, раскрашенными цветами 1 и 3, может быть раскрашен двумя цветами cud. Если каждой паре поставить в соответствие один определенный цвет, то G окажется правильно раскрашенным четырьмя цветами. [14]
Так как Г - однородный граф степени т ( см. [3]), окрестность Г ( г) любой вершины v составляют т вершин. [15]
Страницы: 1 2