On generating 4-regular integral graphs

• Autorzy: Balińska K. , Simić K. , Zwierzyński K.

Warianty tytułu

PL

O generowaniu 4-regularnych grafów całkowitych

• Języki publikacji: EN

Abstrakty

EN

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.

PL

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.

Słowa kluczowe

EN

integral graph; generating graphs

PL

graf całkowity; generowanie grafów

• Wydawca: Poznańskie Towarzystwo Przyjaciół Nauk
• Czasopismo: Studia z Automatyki i Informatyki
• Rocznik: 2006
• Tom: T. 31
• Strony: 7--16
• Opis fizyczny: Bibliogr. 12 poz., rys., tab.

Twórcy

autor

Balińska K.

autor

Simić K.

autor

Zwierzyński K.

• Technical University of Poznań, pl. M. Skłodowskiej-Curie 5, 60-965 Poznań, Poland,

Bibliografia

• [1] Balińska K. T., Kupczyk M., Zwierzyński K. T., Algorithms for Generating Integral Graphs, Miscellanea Algebraicae, WZiA AŚ Kielce, 2001, Vol. 5(1), pp. 7-21.
• [2] Balińska K. T., Kupczyk M., Simić S. K., Zwierzyński K. T., On Generating All Integral Graphs on 11 Vertices, CSC Report No 469, Techn. Univ. Poznań (1999/2000), pp. 1-53.
• [3] Balińska K. T., Kupczyk M., Simić S. K., Zwierzyński K. T., On Generating All Integral Graphs on 12 Vertices, CSC Report No 482, Techn. Univ. Poznań (2001), pp. 1-36.
• [4] Balińska K. T., Kupczyk M., Simić S. K., Zwierzyński K. T., On Generating All Integral Graphs on 13 Vertices, CSC Report No 483, Techn. Univ. Poznań (2002), pp. 1-42.
• [5] Balińska K. T., Simić S. K., Zwierzyński K. T., There Are Exactly 65 4-regular Integral Graphs of Order Less than Twenty, CSC Report No 525, Techn. Univ. Poznań (2006), pp.1-20.
• [6] Balińska K. T., Cvetković D., Radosavljević Z., Simić S. K., Stevanović D., A Survey on Integral Graphs, Univ. Beograd Publ. Elektrotehn. Fak. Ser. Mat., 2002, Vol. 13, pp. 42-65.
• [7] Cvetković D., Doob M., Sachs H., Spectra of Graphs, 3rd ed., Heidelberg-Leipzig, Johann Ambrosius Barth Verlag 1995.
• [8] Cvetković D., Simić S. K., Stevanović D., 4-regular Integral Graphs, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat., 1998, Vol. 9, pp.89-102.
• [9] Lepović M., Simić S. K., Balińska K. T., Zwierzyński K. T., There Are 93 Non-regular, Bipartite Integral Graphs with Maximum Degree Four, CSC Report No. 511, Techn. Univ. Poznań (2005), pp. 1-17.
• [10] Lubiński T., Algorytm genregTL(n, r), in: Balińska K. T., Zwierzyński K. T., Projektowanie algorytmów grafowych, 2nd ed., Poznań (in Polish), WPP 2004, p. 61.
• [11] McKay B. D., http://cs.anu.edu.au/people/bdm/index.html
• [12] Simić S. K., Radosavljević Z., The Nonregular, Nonbipartite, Integral Graphs with Maximum Degree Four, 1995, J. Combinatorics, Information and System Sciences, Vol. 20(1-4, 9-26), pp. 11-26.