About primitive regular graphs with exponent 2
Primitive regular graphs with exponent 2 are considered. We refine the known result that the number of edges of an undirected n-vertex graph with exponent 2 must be at least (3n - 3)/2 for odd n and (3n - 2)/2 for an even n. For regular n-vertex graph with exponent 2 and n > 4, the minimal number of edges is 2n.
Download file
Counter downloads: 169
Keywords
примитивный граф, примитивная матрица, экспонент, однородный граф, primitive graph, primitive matrix, exponent, regular graphAuthors
| Name | Organization | |
| Abrosimov M. B. | Chernyshevsky Saratov State University | mic@rambler.ru |
| Kostin S. V. | Moscow State University of Information Technologies, Radio Engineering and Electronics | kostinsv77@mail.ru |
References
Wiеlandt H. Unzerlegbare nicht negative Matrizen // Math. Zeitschr. 1950. V. 52. P. 642-648.
Jin M., Lee S. G., and Seol H. G. Exponents of r-regular primitive matrices // Inform. Center Math. Sciences. 2003. V.6. No. 2. P. 51-57.
Bueno M. I. and Furtado S. On the exponent of r-regular primitive matrices // ELA. Electronic J. Linear Algebra. 2008. V. 17. P. 28-47.
Kim B., Song B., and Hwang W. Nonnegative primitive matrices with exponent 2 // Linear Algebra and its Applications. 2005. No. 407. P. 162-168.
Meringer M. Fast generation of regular graphs and construction of cages // J. Graph Theory. 1999. No. 30. P. 137-146.
Сухов С. А. DSR Generator. Свид. о гос. регистрации программы для ЭВМ №2016610073. Зарегистрировано в Реестре программ для ЭВМ 11 января 2016 г.
Костин С. В. Об использовании задач по теории графов для интеллектуального развития учащихся // Математика в образовании: сб. статей. Вып. 10 / под ред. И. С. Емельяновой. Чебоксары: Изд-во Чуваш. ун-та. 2014. С. 68-74.
