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

Свойства

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

История

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

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

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

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

Примечания

Литература

• Jon Folkman. Regular line-symmetric graphs // Journal of Combinatorial Theory. — 1967. — Т. 3 , вып. 3 . — doi : .
• Mikhail Klin, Josef Lauri, Matan Ziv-Av. . — 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 : .
• Bouwer I. Z. An Edge But Not Vertex Transitive Regular Graph // Bulletin of the Canadian Mathematical Society. — 1968. — Т. 111968 , вып. 12 . — doi : .
• Conder M., Malnič A., Marušič D., Pisanski T., Potočnik P. // IMFM Preprints. — Ljubljana: Institute of Mathematics, Physics and Mechanics, 2002. — Т. 40 , вып. 845 .

Ссылки

• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .