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

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

Свойства

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

История

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

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

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

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

Примечания

↑ Folkman, 1967, с. 215–232.
↑ Klin, Lauri, Ziv-Av, 2011.
↑ Bouwer, 1968.
↑ Bouwer, 1968, с. 533–535.
↑ Conder, Malnič, Marušič, Pisanski, Potočnik, 2002.
↑ Conder, Malnič, Marušič, Potočnik, 2006, с. 255–294.

Литература

Jon Folkman. Regular line-symmetric graphs // Journal of Combinatorial Theory. — 1967. — Т. 3, вып. 3. — doi:10.1016/S0021-9800(67)80069-3.
Mikhail Klin, Josef Lauri, Matan Ziv-Av. Links between two semisymmetric graphs on 112 vertices through the lens of association schemes. — 2011.
Marston Conder, Aleksander Malnič, Dragan Marušič, Primož Potočnik. A census of semisymmetric cubic graphs on up to 768 vertices // Journal of Algebraic Combinatorics. — 2006. — Т. 23. — С. 255–294. — doi:10.1007/s10801-006-7397-3.
Bouwer I. Z. An Edge But Not Vertex Transitive Regular Graph // Bulletin of the Canadian Mathematical Society. — 1968. — Т. 111968, вып. 12. — doi:10.4153/CMB-1968-063-0.
Conder M., Malnič A., Marušič D., Pisanski T., Potočnik P. The Ljubljana Graph // IMFM Preprints. — Ljubljana: Institute of Mathematics, Physics and Mechanics, 2002. — Т. 40, вып. 845.