Полусимметричный граф
Полусимметричный граф — неориентированный рёберно-транзитивный регулярный граф, не являющийся вершинно-транзитивным. Другими словами, граф полусимметричен, если каждая вершина имеет одно и то же число инцидентных рёбер и для каждой пары рёбер существует симметрия, переводящая одно ребро в другое, однако есть некоторая пара вершин, для которой нет симметрии, переводящей одну вершину в другую.
Свойства[править | править код]
Полусимметричный граф должен быть двудольным, а его группа автоморфизмов должна действовать транзитивно на каждой из двух долей вершин двудольного графа. Например, в показанном на диаграмме графе Фолкмана зелёные вершины нельзя отобразить в красные каким-либо автоморфизмом, но любые две вершины одного цвета симметричны относительно друг друга.
История[править | править код]
Полусимметричные графы первым изучал Даубер, студент Фрэнка Харари, в ныне недоступной статье с названием «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.
 |
|---|
