Нулесимметричный граф
- Нулесимметричный граф — связный граф с ровно тремя падающими ребрами и уникальной симметрией для каждой пары вершин.
- Такой граф является вершинно-транзитивным, но не может быть реберно-транзитивным.
- Название для этого класса графов было придумано Р. M. Фостером в письме 1966 года.
- Нулесимметричные графы также называются графическими регулярными представлениями их групп симметрии.
- Примеры нулесимметричных графов включают неплоский граф с 18 вершинами и усеченные кубооктаэдрические и икосидодекаэдрические графы.
- Существуют более крупные примеры нулесимметричных графов, которые не являются двудольными.
- Каждый конечный нулесимметричный граф является графом Кэли, что помогает в решении задач комбинаторного перечисления.
- Существует 97687 нулесимметричных графов с числом вершин до 1280, которые образуют 89% кубических графов Кэли и 88% всех связанных вершинно-транзитивных кубических графов с одинаковым числом вершин.
- Неизвестно, обязательно ли каждый конечносвязный нулесимметричный граф является гамильтоновым.
Полный текст статьи: