Доминирующие множество
в кубических графах порядка 14 степени 3
.
ФГБОУ ВПО «Кемеровский государственный университет»
*****@***ru
Одним из основных направлений современной теории графов является изучение их доминирующих множеств. Основным понятием здесь является число доминирования графа, то есть наименьшее число вершин, образующих доминирующие множества. Для нахождения числа доминирования не существует эффективных алгоритмов. В общем случае для числа доминирования известны лишь верхние и нижние границы, которые далеки от оптимальных.
В данной работе изучается доминирующие множества в кубических графах порядка 14, с верхней границей числа доминирования равного пяти. Ставиться задача, выяснить существуют ли другие кубические графы порядка 14, для которых 
, отличные от тех которые уже известны, такие как Граф Петерсена 
(рис.3) и Граф Мебиуса.
Для кубических графов точная верхняя вершина была найдена в работе Рида[3]. Пусть 
граф порядка 
Тогда
. (1)
При этом верхняя граница достигается только для двух графов порядка 8 (рис.1 и 2)
Рис.1 Рис.2
Для графов порядка больше восьми Косточка и Стодолски недавно улучшили верхнюю оценку до 
[4]. Единственный пример, в котором достигается эта верхняя граница – это граф Петорсена P(7.2) (рис.3)
Рис.3
Литература и источники
1. Теория Графов, Новосибирск:НГТУ,1998.
2. Лекции по теории графов, М.: Наука, 1990.
3. B. Reed. Paths, stars, and the number three, Combin. put. 5 (1996)
4. Kostochka A. V. , Stodolsky B. Y. On domination in connected cubic graphs, Discrete Math. 304 (2005), n. 1-3, p. 45-50.
Научный руководитель – к. ф-м. н., доцент , ФГБОУ ВПО «Кемеровский государственный университет»
