Граф Мура: различия между версиями

'''Теорема Хоффмана – Синглтона''' утверждает, что любой граф Мура с обхватом 5 должен имеетиметь степень 2, 3, 7 или 57. Графами Мура являются:

{{не переведено 5|Хигман, Грэм|Хигман||Graham Higman }} показал, что, в отличие от других графов Мура, неизвестный граф не может быть [[Вершинно-транзитивный граф|вершинно-транзитивным]]. Мачай и Ширан позднее показали, что порядок автоморфизмов такого графа не превосходит 375.

В обобщённом определении графов Мура, где разрешается чётный обхват, графы с чётным обхватом соответствуют графам инцидентности (возможно вырожденных) {{не переведено 5|Обобщённый многоугольник|обобщённых многоугольников||Generalized polygon}}. Несколько примеров — чётные циклы <math> C_{2n} </math>, [[Полный двудольный граф|полные двудольные графы]] <math> K_{n,n} </math> с обхватом четыре, [[граф Хивуда]] со степенью 3 и обхватом 6 и [[граф Татта — Коксетера]] со степенью 3 и обхватом 8. Известно {{sfn|Bannai, Ito|1973}} {{sfn|Damerell|1973}}), что все графы Мура, кроме перечисленных выше, должны иметь обхват 5, 6, 8 или 12. Случай чётного обхвата следует из теоремы Фейта-Хигмана о возможных значениях n для обобщённых n-угольников.