Введение
Граф, являющийся краем транзитивным и регулярным, но не вершиной транзитивным. В математической области теории графов, полусимметричный граф — это неориентированный граф, который является краем транзитивным и регулярным, но не вершиной транзитивным. Иными словами, граф является полусимметричным, если у каждой вершины одинаковое количество инцидентных рёбер и существует симметрия, переводящая любое ребро графа в любое другое его ребро, но при этом существует пара вершин, для которой нет симметрии, переводящей первую вершину во вторую.
In the mathematical field of graph theory, a semi symmetric graph is an undirected graph that is edge transitive and regular, but not vertex transitive. In other words, a graph is semi symmetric if each vertex has the same number of incident edges, and there is a symmetry taking any of the graph's edges to any other of its edges, but there is some pair of vertices such that no symmetry maps the first into the second.
Свойства
Полусимметричный граф должен быть двудольным, а его группа автоморфизмов должна действовать транзитивно на каждом из двух множеств вершин двудольного разбиения (при этом регулярность не требуется для выполнения этого свойства). Например, на диаграмме графика Фолкмана, представленной здесь, зелёные вершины нельзя отобразить на красные ни одним автоморфизмом, но любые две вершины одного цвета симметричны относительно друг друга.
История
Полусимметричные графы впервые были изучены Э. Даубером, учеником Ф. Харари, в статье, которая в настоящее время недоступна, под названием «О графах, симметричных по рёбрам, но не по вершинам». Эту работу увидел Джон Фолкман, в статье которого, опубликованной в 1967 году, представлен наименьший полусимметричный граф, ныне известный как граф Фолкмана, состоящий из 20 вершин. Термин «полусимметричный» впервые был использован Клином и соавторами в статье, опубликованной в 1978 году.
Кубические графики
Самый маленький кубический полусимметричный граф (то есть граф, в котором каждая вершина инцидентна ровно трём рёбрам) — это граф Грея на 54 вершинах. Впервые его полусимметричность была отмечена. Доказательство того, что это наименьший кубический полусимметричный граф, было получено Драганом Марушичем и Александром Мальничем. Известны все кубические полусимметричные графы на вершинах до 10000. Согласно Кондеру, Мальничу, Марушичу и Поточнику, четыре наименьших кубических полусимметричных графа после графа Грея — это граф Иофиновой–Иванова на 110 вершин, граф Любляны на 112 вершин, граф на 120 вершин с длиной окружности 8 и клетка Тутте 12.