On generating 4-regular integral graphs

A graph is called integral if all eigenvalues of its adjacency matrix are integers. Exact and randomized algorithms for generating 4-regular graphs and sieving integral graphs are defined. All connected 4-regular integral graphs of order 12 < n < 20 generated by a computer search are presented and some of their properties are indicated. A new algorithm for constructing 4-regular integral graphs of order n ≥ 20 based on the experimental results is proposed.

---

Graf nazywamy całkowitym, jeżeli wszystkie wartości własne jego macierzy przyległości są liczbami całkowitymi. Określono algorytmy, dokładny i zrandomizowany, generowania spójnych grafów 4-regularnych i odsiewania grafów całkowitych. Przedstawiono struktury wszystkich spójnych 4-regularnych grafów całkowitych rzędu 12 < n < 20, wygenerowanych z wykorzystaniem opracowanych algorytmów oraz zbadano ich wybrane niezmienniki liczbowe i strukturalne. Wykorzystując wyniki eksperymentów obliczeniowych zaprojektowano nowy algorytm generowania grafów tej klasy rzędu n ≥ 20.