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

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

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



Тр. ИММ УрО РАН:
Год:
Том:
Выпуск:
Страница:
Найти






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


Труды Института математики и механики УрО РАН, 2024, том 30, номер 4, страницы 64–76
DOI: https://doi.org/10.21538/0134-4889-2024-30-4-64-76
(Mi timm2128)
 

4-изящные деревья

В. А. Баранский, И. А. Насыров, Т. А. Сеньчонок

Уральский федеральный университет им. первого Президента России Б. Н. Ельцина, г. Екатеринбург
Список литературы:
Аннотация: Пусть $f$ — раскраска вершин связного графа $G$ в краски из множества красок $\{1, 2, \dots, k\}$. Раскраска $f$ на множестве ребер графа $G$ индуцирует функцию $f'(e) = |f(u) - f(v)|$, где $e = uv$ — произвольное ребро графа $G$. Число $f'(e)$ будем называть цветом ребра $e$, индуцированным раскраской $f$. Раскраска $f$ называется изящной $k$-раскраской графа $G$, если $f'$ является реберной раскраской этого графа. Граф будем называть $k$-изящным или, просто, изящным, если он обладает изящной $k$-раскраской. Основная цель нашей работы — дать два достаточных условия, каждое из которых гарантирует 4-изящность деревьев (см. теоремы 1 и 2). Кроме этого мы исследуем свойства 4-изящных графов для доказательства теорем 1 и 2. Найденные свойства мы также используем в следующих работах для изучения 4-изящных графов и 4-изящных деревьев в общем случае. Отметим, что 4-изящные деревья устроены достаточно сложно, а 3-изящные связные графы устроены очень просто. Они исчерпываются простыми цепями длины не более 3. Нетрудно установить, что любой 4-изящный граф не содержит вершин степени, большей 3. Поэтому мы рассматриваем деревья $T$, степени вершин которых не превосходят числа 3. Вершины степени 3 в дереве $T$ мы будем называть узлами. Будем говорить, что для двух узлов $u$ и $v$ дерева $T$ узловое расстояние между ними равно числу $t$, если существует простая цепь от $u$ до $v$, число внутренних вершин в которой равно $t\geq 1$ и все эти внутренние вершины имеют степень 2 в дереве $T$. Конечно, узловое расстояние определено не для каждой пары узлов. Среди прочих свойств 4-изящных графов установлено, что такие графы не содержат простых цепей, состоящих из трех узлов. Указанные нами достаточные условия 4-изящности деревьев состоят в запрете появления в них пар узлов, узловое расстояние между которыми равно 1 или 2.
Ключевые слова: граф, дерево, изящная раскраска графа, изящные деревья.
Поступила в редакцию: 29.09.2024
Исправленный вариант: 08.10.2024
Принята в печать: 14.10.2024
Реферативные базы данных:
Тип публикации: Статья
УДК: 519.174.7
MSC: 05C15
Образец цитирования: В. А. Баранский, И. А. Насыров, Т. А. Сеньчонок, “4-изящные деревья”, Тр. ИММ УрО РАН, 30, № 4, 2024, 64–76
Цитирование в формате AMSBIB
\RBibitem{BarNasSen24}
\by В.~А.~Баранский, И.~А.~Насыров, Т.~А.~Сеньчонок
\paper 4-изящные деревья
\serial Тр. ИММ УрО РАН
\yr 2024
\vol 30
\issue 4
\pages 64--76
\mathnet{http://mi.mathnet.ru/timm2128}
\crossref{https://doi.org/10.21538/0134-4889-2024-30-4-64-76}
\elib{https://elibrary.ru/item.asp?id=75134206}
\edn{https://elibrary.ru/lljfjo}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/timm2128
  • https://www.mathnet.ru/rus/timm/v30/i4/p64
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Труды Института математики и механики УрО РАН
    Статистика просмотров:
    Страница аннотации:49
    PDF полного текста:2
    Список литературы:7
    Первая страница:1
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025