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

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

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

Свойства

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

История

Полусимметричные графы первым изучал Даубер, студент Фрэнка Харари, в ныне недоступной статье с названием «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.

Ссылки

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

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

[_490f491e78281f14-1] Folkman, 1967, с. 215–232.

[_85e5fd8b67521a3b-2] Klin, Lauri, Ziv-Av, 2011.

[_f858a90779640a89-3] Bouwer, 1968.

[_41972152e36606be-4] Bouwer, 1968, с. 533–535.

[_a0952eb686d4f034-5] Conder, Malnič, Marušič, Pisanski, Potočnik, 2002.

[_6e4db9da24e04cba-6] Conder, Malnič, Marušič, Potočnik, 2006, с. 255–294.