RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



ПДМ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


ПДМ, 2011, номер 2(12), страницы 101–112 (Mi pdm276)  

Эта публикация цитируется в 24 научных статьях (всего в 24 статьях)

Прикладная теория графов

Оценки экспонентов примитивных графов

В. М. Фомичев

Институт проблем информатики РАН, г. Москва, Россия

Аннотация: Уточнены оценки экспонентов для $n$-вершинных примитивных орграфов (неотрицательных матриц порядка $n$), содержащих два простых контура, длины которых взаимно просты. Получены достижимые оценки порядка $\mathrm O(\max\{l\lambda,f(l,\lambda,n)\})$, где $l$ и $\lambda$ – взаимно простые длины простых контуров в орграфе и $f(l,\lambda,n)$ – линейный полином. Описан полностью класс примитивных орграфов, на которых достигается абсолютная оценка экспонента $n^2-2n+2$ (H. Wielandt, 1950). Для экспонентов неориентированных $n$-вершинных примитивных графов доказаны уточняющие оценки. В частности, если $l$ – длина длиннейшего простого цикла нечетной длины в графе $\Gamma$, то экспонент графа $\Gamma$ не превышает $2n-l-1$. Описан полностью класс примитивных неориентированных графов, на которых достигается абсолютная оценка экспонента $2n-2$.

Ключевые слова: примитивные графы, экспонент графа.

Полный текст: PDF файл (617 kB)
Список литературы: PDF файл   HTML файл
Тип публикации: Статья
УДК: 519.6

Образец цитирования: В. М. Фомичев, “Оценки экспонентов примитивных графов”, ПДМ, 2011, № 2(12), 101–112

Цитирование в формате AMSBIB
\RBibitem{Fom11}
\by В.~М.~Фомичев
\paper Оценки экспонентов примитивных графов
\jour ПДМ
\yr 2011
\issue 2(12)
\pages 101--112
\mathnet{http://mi.mathnet.ru/pdm276}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/pdm276
  • http://mi.mathnet.ru/rus/pdm/y2011/i2/p101

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. В. М. Фомичев, “Уточнение оценок экспонентов примитивных графов”, ПДМ, 2011, приложение № 4, 98–100  mathnet
    2. С. Н. Кяжин, В. М. Фомичев, “О примитивных наборах натуральных чисел”, ПДМ, 2012, № 2(16), 5–14  mathnet
    3. А. М. Коренева, В. М. Фомичев, “Об одном обобщении блочных шифров Фейстеля”, ПДМ, 2012, № 3(17), 34–40  mathnet
    4. К. Г. Когос, В. М. Фомичев, “Положительные свойства неотрицательных матриц”, ПДМ, 2012, № 4(18), 5–13  mathnet
    5. Кяжин С.Н., Фомичев В.М., “Определяющие свойства примитивных наборов натуральных чисел”, Безопасность информационных технологий, 2012, № 1, 37–41  elib
    6. С. Н. Кяжин, “О локальной примитивности графов и неотрицательных матриц”, ПДМ. Приложение, 2013, № 6, 81–83  mathnet
    7. А. М. Дорохова, В. М. Фомичев, “Уточнённые оценки экспонентов перемешивающих графов биективных регистров сдвига над множеством двоичных векторов”, ПДМ, 2014, № 1(23), 77–83  mathnet
    8. В. М. Фомичев, “Оценка экспонента некоторых графов с помощью чисел Фробениуса для трёх аргументов”, ПДМ, 2014, № 2(24), 88–96  mathnet
    9. Я. Э. Авезова, В. М. Фомичев, “О примитивности перемешивающей матрицы генератора $(\delta,\tau)$-самоусечения”, ПДМ. Приложение, 2014, № 7, 42–43  mathnet
    10. А. М. Дорохова, “Оценки экспонентов перемешивающих графов некоторых модификаций аддитивных генераторов”, ПДМ. Приложение, 2014, № 7, 60–64  mathnet
    11. В. М. Фомичев, “Об оценках экспонентов орграфов с использованием чисел Фробениуса”, ПДМ. Приложение, 2014, № 7, 137–140  mathnet
    12. В. М. Фомичев, “Свойства минимальных примитивных орграфов”, ПДМ, 2015, № 2(28), 86–96  mathnet  crossref
    13. А. М. Дорохова, “О примитивности перемешивающих графов преобразований регистров сдвига с двумя обратными связями”, ПДМ. Приложение, 2015, № 8, 8–11  mathnet  crossref
    14. С. Н. Кяжин, Ф. В. Лебедев, “О точности матрично-графового подхода к оценке перемешивающих свойств преобразований”, ПДМ. Приложение, 2016, № 9, 57–59  mathnet  crossref
    15. В. М. Фомичев, “Новая универсальная оценка экспонентов графов”, ПДМ, 2016, № 3(33), 78–84  mathnet  crossref
    16. А. М. Коренева, В. М. Фомичёв, “Перемешивающие свойства модифицированных аддитивных генераторов”, Дискретн. анализ и исслед. опер., 24:2 (2017), 32–52  mathnet  crossref  elib; A. M. Koreneva, V. M. Fomichev, “The mixing properties of modified additive generators”, J. Appl. Industr. Math., 11:2 (2017), 215–226  crossref
    17. В. С. Григорьев, В. М. Фомичев, “О примитивности перемешивающих подстановок регистров сдвига”, ПДМ. Приложение, 2017, № 10, 14–16  mathnet  crossref
    18. А. М. Коренева, “О примитивности перемешивающих орграфов регистров сдвига с двумя обратными связями”, ПДМ, 2017, № 37, 32–51  mathnet  crossref
    19. В. М. Фомичёв, Я. Э. Авезова, А. М. Коренева, С. Н. Кяжин, “Примитивность и локальная примитивность орграфов и неотрицательных матриц”, Дискретн. анализ и исслед. опер., 25:3 (2018), 95–125  mathnet  crossref  elib; V. M. Fomichev, Ya. E. Avezova, A. M. Koreneva, S. N. Kyazhin, “Primitivity and local primitivity of digraphs and nonnegative matrices”, J. Appl. Industr. Math., 12:3 (2018), 453–469  crossref
    20. В. М. Фомичев, “Улучшенная формула универсальной оценки экспонента орграфа”, ПДМ. Приложение, 2018, № 11, 16–20  mathnet  crossref
    21. В. С. Григорьев, “О перемешивающих графах нелинейных подстановок двоичных регистров сдвига”, ПДМ. Приложение, 2018, № 11, 6–9  mathnet  crossref
    22. А. Р. Мифтахутдинова, “Анализ совершенности и сильной нелинейности алгоритмов блочного шифрования”, ПДМ. Приложение, 2018, № 11, 74–76  mathnet  crossref
    23. В. М. Фомичев, “Об улучшенной универсальной оценке экспонентов орграфов”, ПДМ, 2019, № 43, 115–123  mathnet  crossref
    24. Л. А. Карпова, И. А. Панкратова, “Перемешивающие свойства некоторых классов подстановок на $\mathbb{F}_2^n$”, ПДМ. Приложение, 2019, № 12, 47–50  mathnet  crossref
  • Прикладная дискретная математика
    Просмотров:
    Эта страница:317
    Полный текст:115
    Литература:30
    Первая стр.:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020