sibsutisВестник СибГУТИThe Herald of the Siberian State University of Telecommunications and Information Science1998-6920СибГУТИ10.55648/1998-6920-2024-18-4-52-61sibsutis-897Research ArticleСтатьиРезультаты по целочисленным графамResults of Search About Integer Graphhttps://orcid.org/0000-0001-7929-1899ОвчаренкоА. Ю.OvcharenkoA. Yu.

Овчаренко Алёна Юрьевна - к.т.н., доцент кафедры высшей математики, 

630102, Новосибирск, ул. Кирова, д. 86.

Alena Y. Ovcharenko - PhD in Engineering, Assoc. Professor of the Department of Higher Mathematics,

86, Kirov St., Novosibirsk, 630102.

shmatova_aaa@mail.ruСибирский государственный университет телекоммуникаций и информатики (СибГУТИ)РоссияSiberian State University of Telecommunications and Information Science (SibSUTIS)Russian Federation202412052024184Вестник СибГУТИ5261Copyright © Овчаренко А.Ю., 20242024Овчаренко А.Ю.Ovcharenko A.Y.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestnik.sibsutis.ru/jour/article/view/897

В статье представлен обзор результатов, связанных с поиском целочисленных графов Кэли и смежные вопросы. 

The article provides an overview of the results related to the search for integer graphs and related issues.

целочисленные графыспектр графарегулярные графынерегулярные графы4-регулярные графыinteger graphsspectrum of graphregular graphsnon-regular graphs4-regular graphsReferencesHarary F, Schwenk A. J. Which graphs have integral spectra? Graphs and Combinatorics (Bari R. and Harary F., eds.), Springer-Verlag, Berlin (1974), P. 45—51.Harary F, Schwenk A. J. Which graphs have integral spectra? Graphs and Combinatorics (R. Bari and F. Harary, eds.), Springer-Verlag, Berlin (1974), pp. 45—51.Akers S., Krishnamurthy B. A group theoretic model for symmetric interconnection networks // IEEE Transactions on Computers, 1989. P. 555 - 566.Akers S., Krishnamurthy B. A group theoretic model for symmetric interconnection networks. IEEE Transactions on Computers, 1989. pp. 555 - 566.Hwang K., Jacobs M., Earl E. Swartzlander (Jr.). Proceedings of the 1986 International Conference on Parallel Processing // IEEE Computer Society Press, 1986, P 1051.Hwang K., Jacobs M., Earl E. Swartzlander (Jr.). Proceedings of the 1986 International Conference on Parallel Processing. IEEE Computer Society Press, 1986, pp. 1051.Annexstein, F., Baumslag, M., Rosenberg, A.L. Group action graphs and parallel architectures. SIAM J. Comput., 19, 1990. P. 544–569.Annexstein, F., Baumslag, M., Rosenberg, A. L. Group action graphs and parallel architectures. SIAM J. Comput., 19, 1990. pp. 544–569.Heydemann, M. Cayley graphs and interconnection networks. In: G. Hahn and G. Sabidussi (Eds), Graph Symmetry: Algebraic Methods and Applications. 1997. P. 167–224.Heydemann, M. Cayley graphs and interconnection networks. In: G. Hahn and G. Sabidussi (Eds), Graph Symmetry: Algebraic Methods and Applications. 1997. pp. 167–224.Xiao W., Parhami B. Some mathematical properties of Cayley digraphs with applications to interconnection network design. International Journal of Computer Mathematics, 2005. P. 521–528.Xiao W., Parhami B. Some mathematical properties of Cayley digraphs with applications to interconnection network design. International Journal of Computer Mathematics, 2005. pp. 521–528.Lavault C. Interconnection Networks: Graph- and Group Theoretic Modelling. 12th International Conference on Control Systems and Computer Science, 1999. P. 207-214.Lavault C. Interconnection Networks: Graph- and Group Theoretic Modelling. 12th International Conference on Control Systems and Computer Science, 1999. pp. 207-214.Godsil C. State transfer on graphs. Discrete Mathematics, 312(1): P. 129 – 147, 2012.Godsil C. State transfer on graphs. Discrete Mathematics, 312(1):129 – 147, 2012.Ekert A., Christandl M., Datta N., Landahl A. J. Perfect state transfer in quantum spin networks. Phys. Rev. Lett., 92:187902, May 2004.Ekert A., Christandl M., Datta N., Landahl A. J. Perfect state transfer in quantum spin networks. Phys. Rev. Lett., 92:187902, May 2004.Овчаренко А. Ю. Спектры и диаметры графов Кэли некоторых конечных групп // Вестник СибГУТИ. 2018. №3. С. 45—61.Ovcharenko A. Y. Spektry i diametry grafov Keli nekotorykh konechnykh grupp [Spectra and diameters of Cayley graphs of some finite groups]. Vestnik SibGUTI, 2018, no. 3, pp. 45-61.Balinska K., Cvetkovic D., Radosavljevic Z., Simic S., Stevanovic D. A survey on integral graphs, Publ ETF, 2002, № 13, P. 1-24.Balinska K., Cvetkovic D., Radosavljevic Z., Simic S., Stevanovic D. A survey on integral graphs. Publ ETF, 2002, no. 13, pp. 1-24.Cvetkovic D., Doob M., Sachs H. Spectra of graphs – Theory and application. Deutscher Verlag der Wissenschaften – Academic Press, Berlin–New York, 1980; secondedition 1982; third edition, Johann Ambrosius Barth Verlag, Heidelberg–Leipzig, 1995.Cvetkovic D., Doob M., Sachs H. Spectra of graphs – Theory and application. Deutscher Verlag der Wissenschaften – Academic Press, Berlin–New York, 1980; secondedition 1982; third edition, Johann Ambrosius Barth Verlag, Heidelberg–Leipzig, 1995.Bussemaker F. C., Cvetkoviс D. There are exactly 13 connected, cubic, integral graphs. Univ. Beograd, Publ. Elektrotehn. Fak., Ser. Mat. Fiz., Nos. 544–576 (1976), P. 43–48.Bussemaker F. C., Cvetkoviс D. There are exactly 13 connected, cubic, integral graphs. Univ. Beograd, Publ. Elektrotehn. Fak., Ser. Mat. Fiz., Nos. 544–576 (1976), pp. 43–48.Schwenk A. J. Exactly thirteen connected cubic graphs have integral spectra. Proceedings of the International Graph Theory Conference at Kalamazoo, May 1976, (Y. Alavi and D. Lick, eds.) Springer-Verlag.Schwenk A. J. Exactly thirteen connected cubic graphs have integral spectra. Proceedings of the International Graph Theory Conference at Kalamazoo, May 1976, (Y. Alavi and D. Lick, eds.) Springer-Verlag.Roitman M. An infinite family of integral graphs, Discrete Math. 52 (1984), №2-3, P. 313— 315.Roitman M. An infinite family of integral graphs. Discrete Math. 52 (1984), no.2-3, pp. 313—315.Wang L.G., Li X.L., Hoede C. Integral complete r-partite Graphs, Discrete Math. 283 (2004), № 1-3, P. 231-241.Wang L. G., Li X. L., Hoede C. Integral complete r-partite Graphs. Discrete Math. 283 (2004), no. 13, 231-241.Wang L. A survey of results on integral trees and integral graphs, Department of Applied Mathematics, Faculty of EEMCS, University of Twente The Netherlands, Memorandum № 1763 (2005), P. 1—22.Wang L. A survey of results on integral trees and integral graphs. Department of Applied Mathematics, Faculty of EEMCS, University of Twente The Netherlands, Memorandum No. 1763 (2005), pp. 1—22.Balinska K. T., Cvetkovic D., Lepovic M., Simic S. K. There are exactly 150 connected integral graphs up to 10 vertices. Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. 10 (1999), P. 95-105.Balinska K. T., Cvetkovic D., Lepovic M., Simic S. K. There are exactly 150 connected integral graphs up to 10 vertices. Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. 10 (1999), 95-105.Balinska K. T., Kupczyk M., Simic S. K., Zwierzynski K. T. On generating all integral graphs on 11 vertices. Computer Science Center Report № 469, Technical University of Poznan, (1999/2000), P. 1–53.Balinska K. T., Kupczyk M., Simic S. K., Zwierzynski K. T. On generating all integral graphs on 11 vertices. Computer Science Center Report No. 469, Technical University of Poznan, (1999/2000), pp. 1–53.Balinska K. T., Kupczyk M., Simic S. K., Zwierzynski K. T. On generating all integral graphs on 12 vertices. Computer Science Center Report № 482, Technical University of Poznan, (2001), P. 1–36.Balinska K. T., Kupczyk M., Simic S. K., Zwierzynski K. T. On generating all integral graphs on 12 vertices. Computer Science Center Report No. 482, Technical University of Poznan, (2001), pp. 1– 36.Cvetkovic D., Simic S., Stevanovic D. 4-Regular integral graphs, Univ. Beograd. Publ. Elektr. Fak, Ser. Mat. 9 (1998), P. 89–102.Cvetkovic D., Simic S., Stevanovic D. 4-Regular integral graphs, Univ. Beograd. Publ. Elektr. Fak, Ser. Mat. 9 (1998), pp. 89–102.Stevanovic D. Nonexistence of some 4-regular integral graphs, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. 10 (1999), P. 81-86.Stevanovic D. Nonexistence of some 4-regular integral graphs, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. 10 (1999), pp. 81-86.Stevanovic D. 4-Regular integral graphs avoiding ±3 in the spectrum, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. 14 (2003), P. 99-110.Stevanovic D. 4-Regular integral graphs avoiding ±3 in the spectrum, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. 14 (2003), pp. 99-110.Stevanovic D., de Abreu N.M.M., de Freitas M.A.A., Del-Vecchio R. Walks and Regular Integral Graphs, Linear Algebra Appl. 423 (2007), P. 119–135.Stevanovic D., de Abreu N. M. M., de Freitas M. A. A., Del-Vecchio R. Walks and Regular Integral Graphs. Linear Algebra Appl. 423 (2007), pp. 119–135.Stevanovic D. Some compositions of graphs and integral graphs (in Serbian), Ph.D. thesis, University of Nis, 2000.Stevanovic D. Some compositions of graphs and integral graphs (in Serbian), Ph.D. thesis, University of Nis, 2000.Minchenko M., Wanless I. M. Quartic integral Cayley graphs. // Ars Mathematica Contemporanea. – V. 8. – 2015. P. 381–408.Minchenko M., Wanless I. M. Quartic integral Cayley graphs. Ars Mathematica Contemporanea. – Vol. 8. – 2015. pp. 381–408.Balinska K. T., Simic S. K. The nonregular, bipartite, integral graphs with maximum degree 4. Part I: Basic properties, Graph theory (Kazimierz Dolny, 1997), Discrete Math. 236 (2001), №1-3, P. 13-24.Balinska K. T., Simic S. K. The nonregular, bipartite, integral graphs with maximum degree 4. Part I: Basic properties, Graph theory (Kazimierz Dolny, 1997), Discrete Math. 236 (2001), no.1-3, pp. 1324.Balinska K. T., Simic S. K. Some remarks on integral graphs with maximum degree four. XIV Conference on Applied Mathematics (Palic, 2000). Novi Sad J. Math. 31 (2001), № 1, P. 19- 25.Balinska K. T., Simic S. K. Some remarks on integral graphs with maximum degree four. XIV Conference on Applied Mathematics (Palic, 2000). Novi Sad J. Math. 31 (2001), no.1, 19- 25. pp. 13 24.Balinska K. T., Simic S. K. Zwierzynski K. T. Which non-regular bipartite integral graphs with maximum degree four do not have ±1 as eigenvalues? Discrete Math. 286 (2004), № 12, P. 15- 24.Balinska K. T., Simic S. K. Zwierzynski K. T. Which non-regular bipartite integral graphs with maximum degree four do not have ±1 as eigenvalues? Discrete Math. 286 (2004), no.1-2, pp. 15- 24.Stevanovic D. Some compositions of graphs and integral graphs (in Serbian), Ph.D. thesis, University of Nis, 2000.Stevanovic D. Some compositions of graphs and integral graphs (in Serbian), Ph.D. thesis, University of Nis, 2000.Ghasemi M. Integral pentavalent Cayley graphs on abelian or dihedral groups. Proceedings of the Indian Academy of Sciences: Mathematical Sciences. – 2017. – V. 127, № 2. – P. 219-224Ghasemi M. Integral pentavalent Cayley graphs on abelian or dihedral groups. Proceedings of the Indian Academy of Sciences: Mathematical Sciences. – 2017. – Vol. 127, no. 2. – pp. 219-224.Konstantinova E. V., Lytkina D.V. Integral Cayley Graphs over Finite Groups // Algebra Colloquium. – 2020. – V. 27, № 1. – P. 131-136.Konstantinova E. V., Lytkina D. V. Integral Cayley Graphs over Finite Groups. Algebra Colloquium. – 2020. – Vol. 27, no. 1. – pp. 131-136.Goryainov S., Zhao D., Konstantinova E. V., Li H. Integral graphs obtained by dual Seidel switching. Linear Algebra and its Applications. – 2020. – V. 604. – P. 476-489.Goryainov S., Zhao D., Konstantinova E. V., Li H. Integral graphs obtained by dual Seidel switching. Linear Algebra and its Applications. – 2020. – Vol. 604. – pp. 476-489.Lu. Lu, Huang Q., Huang X. Integral Cayley graphs over dihedral groups. Journal of Algebraic Combinatorics. – 2018. – V. 47, № 4. – P. 585-601.Lu. Lu, Huang Q., Huang X. Integral Cayley graphs over dihedral groups. Journal of Algebraic Combinatorics. – 2018. – Vol. 47, no. 4. – pp. 585-601.Huang J., Li. Sh. Integral and distance integral Cayley graphs over generalized dihedral groups. Journal of Algebraic Combinatorics. – 2021. – V. 53, № 4. – P. 921-943.Huang J., Li. Sh. Integral and distance integral Cayley graphs over generalized dihedral groups. Journal of Algebraic Combinatorics. – 2021. – Vol. 53, no. 4. – pp. 921-943.

The authors declare that there are no conflicts of interest present.