Полусимметричный граф

Полусимметричный граф — это неориентированный рёберно-транзитивный регулярный граф, не являющийся вершинно-транзитивным. Другими словами, граф полусимметричен, если каждая вершина имеет одно и то же число инцидентных рёбер и для каждой пары рёбер существует симметрия, переводящая одно ребро в другое, однако есть некоторая пара вершин, для которой нет симметрии, переводящей одну вершину в другую.

Граф Фолкмана, наименьший полусимметричный граф.

Свойства

Полусимметричный граф должен быть двудольным, а его группа автоморфизмов должна действовать транзитивно на каждой из двух долей вершин двудольного графа. Например, в показанном на диаграмме графе Фолкмана зелёные вершины нельзя отобразить в красные каким-либо автоморфизмом, но любые две вершины одного цвета симметричны относительно друг друга.

История

Полусимметричные графы первым изучал Даубер, студент Фрэнка Харари, в ныне недоступной статье с названием «On line- but not point-symmetric graphs» (О рёберно-, но не вершинно-симметричных графах). Статью увидел Джон Фолкман, статья которого, опубликованная в 1967, включала наименьший полусимметричный граф, известный ныне как Граф Фолкмана, с 20 вершинами[1]. Термин «полусимметричный» первым использовали Клин, Лаури и Зив-Ав в статье, которую они опубликовали в 1978[2].

Кубические графы

Наименьший кубический полусимметричный граф (то есть граф, в котором каждая вершина инцидентна в точности трём рёбрам) является граф Грея с 54 вершинами. Первым обнаружил, что граф полусимметричен, Боувер[3]. То, что граф наименьший среди кубических полусимметричных графов, доказали Марушич и Малнич[4].

Все кубические полусимметричные графы вплоть до 768 вершин известны. Согласно Кондеру, Малничу, Марушичу и Поточнику четырьмя наименьшими кубическими полусимметричными графами после графа Грея являются граф Иванова — Иофиновой с 110 вершинами, граф Любляны со 112 вершинами[5], граф со 120 вершинами и обхватом 8 и 12-клетка Татта[6].

Примечания

Литература

Ссылки

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.