Рассматривается вопрос о максимальном числе вершин в примитивных неориентированных регулярных графах с экспонентом, равным 3. Получена оценка сверху этого числа в зависимости от порядка графа р: np ≤ р3 - р2 - 3р + 5. Найдено точное значение максимального числа вершин в примитивных кубических графах с экспонентом, равным 3: Пз = 12. Проведён вычислительный эксперимент и найдено число примитивных регулярных графов порядка р ≤ 9 с числом вершин n ≤ 16 и экспонентом, равным 3, для всех пар (п,р).
Скачать электронную версию публикации
Загружен, раз: 13
- Title К вопросу о максимальном числе вершин в примитивных регулярных графах с экспонентом 3
- Headline К вопросу о максимальном числе вершин в примитивных регулярных графах с экспонентом 3
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 67
- Date:
- DOI 10.17223/20710410/67/5
Ключевые слова
примитивный граф, регулярный граф, максимальное число вершинАвторы
Ссылки
Смарт Н. Криптография. М.: Техносфера, 2005. 528с.
Haffman A. J. and Singletan R. R. Moore graphs with diameter 2 and 3 // IBM J. Research and Development. 1960. V. 4. P.497-504.
Meringer M. Fast generation of regular graphs and construction of cages // J. Graph Theory. 1999. V. 30. P. 137-146.
Kim B., Sang B., and Hwang W. Nonnegative primitive matrices with exponent 2 // Linear Algebra Appl. 2005. No. 407. P. 162-168.
Buena M. I. and Furtada S. On the exponent of r-regular primitive matrices // ELA. Electronic J. Linear Algebra. 2008. V. 17. P.28-47.
Jin M., Lee S. G., and Seal H. G. Exponents of r-regular primitive matrices // Inform. Center for Math. Sci. 2003. V. 6. No. 2. P.51-57.
Абросимов М. Б., Костин С. В., Лось И. В. О наибольшем числе вершин примитивных однородных графов порядка 2, 3, 4 с экспонентом, равным 2 // Прикладная дискретная математика. 2021. №52. С. 97-104.
Абросимов М. Б., Лось И. В., Костин С. В. Примитивные однородные графы с экспонентом 2 и числом вершин до 16 // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2021. T.21. Вып.2. С. 238-245.
Фомичев В. М., Авезова Я. Э. Точная формула экспонентов перемешивающих орграфов регистровых преобразований // Дискрет. анализ исслед. опер. 2020. №2(27). С. 117-135.
Фомичев В. М. Оценки экспонентов примитивных графов // Прикладная дискретная математика. 2011. №2(11). С. 101-112.
Салий В. Н. Минимальные примитивные расширения ориентированных графов // Прикладная дискретная математика. 2008. №1(1). С. 116-119.
Wielandt H. Unzerlegbare nicht negative Matrizen // Math. Zeitschr. 1950. V. 52. P. 642-648.
Сачков В. Н., Ошкин И. Б. Экспоненты классов неотрицательных матриц // Дискретная математика. 1993. Т. 5. №2. С. 150-159.
К вопросу о максимальном числе вершин в примитивных регулярных графах с экспонентом 3 | Прикладная дискретная математика. 2025. № 67. DOI: 10.17223/20710410/67/5
Скачать полнотекстовую версию
Загружен, раз: 195