граф Мура

Граф Мура — регулярный граф степени и диаметром , число вершин которого равно верхней границе Эквивалентное определение графа Мура — это граф диаметра с обхватом . Ещё одно эквивалентное определение графа Мура — это граф с обхватом , имеющий в точности циклов длины , где , — число вершин и рёбер графа . Графы, фактически, экстремальны по отношению к числу циклов, длина которых равна обхвату графа. Графы названы и Робертом Синглтоном именем Эдварда Мура, который поставил вопрос описания и классификации таких графов. Имея максимально возможное число вершин для заданной комбинации степени и диаметра, графы Мура имеют минимально возможное число вершин для регулярных графов с заданной степенью и обхватом. Таким образом, любой граф Мура является клеткой. Формула для числа вершин графа Мура может быть обобщена для возможности определения графов Мура с чётным обхватом, и эти графы снова являются клетками.