Graf regularny stopnia to graf, w którym wszystkie wierzchołki są stopnia czyli z każdego wierzchołka grafu regularnego wychodzi krawędzi. Graf regularny stopnia określa się dla wygody mianem grafu -regularnego. Szczególnym przypadkiem grafów regularnych są grafy kubiczne (grafy -regularne)[1].
Graf silnie regularny to graf regularny w którym wszystkie pary sąsiadujących ze sobą wierzchołków mają tyle samo wspólnych sąsiednich wierzchołków, i wszystkie pary niesąsiadujących ze sobą wierzchołków też mają tyle samo wspólnych wierzchołków sąsiednich.