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

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

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



Дискретн. анализ и исслед. опер.:
Год:
Том:
Выпуск:
Страница:
Найти






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


Дискретн. анализ и исслед. опер., сер. 1, 2002, том 9, номер 2, страницы 21–35 (Mi da173)  

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

О путевых ядрах и разбиениях в неориентированных графах

Л. С. Мельников, И. В. Петренко

Институт математики им. С. Л. Соболева СО РАН

Аннотация: Пусть $\tau(G)$ обозначает число вершин в длиннейшем пути неориентированного графа $G$. Для пары натуральных чисел $(a,b)$ таких, что $a+b=\tau(G)$, граф $G$ называется $(a,b)$-разбиваемым, если его множество вершин $V(G)$ можно разбить на два класса $A$$B$ таким образом, что $\tau(G[A])\leq a$ и $\tau(G[B])\leq b$, где $G[A]$ и $G[B]$ – индуцированные подграфы на множествах вершин $A$ и $B$ в $G$. Подмножество $K$ множества $V(G)$ называется $P_n$-ядром, если $\tau(G[K])\leq n-1$ и каждая вершина $v\in V(G-K)$ смежна с вершиной, которая является конечной в пути длины $n-1$ в графе $G$. Известно, что наличие $P_n$-ядра в графе $G$ означает, что $G$ является $(\tau(G)-n+1,n-1)$-разбиваемым. В настоящей статье доказано, что каждый граф имеет $P_8$-ядро.
Ил. 11, библиогр. 13.

Полный текст: PDF файл (695 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:
УДК: 519.177
Статья поступила: 13.11.2001

Образец цитирования: Л. С. Мельников, И. В. Петренко, “О путевых ядрах и разбиениях в неориентированных графах”, Дискретн. анализ и исслед. опер., сер. 1, 9:2 (2002), 21–35

Цитирование в формате AMSBIB
\RBibitem{MelPet02}
\by Л.~С.~Мельников, И.~В.~Петренко
\paper О путевых ядрах и разбиениях в~неориентированных графах
\jour Дискретн. анализ и исслед. опер., сер.~1
\yr 2002
\vol 9
\issue 2
\pages 21--35
\mathnet{http://mi.mathnet.ru/da173}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1929631}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/da173
  • http://mi.mathnet.ru/rus/da/v9/s1/i2/p21

    ОТПРАВИТЬ: 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. Frick M., Schiermeyer I., “An asymptotic result for the Path Partition Conjecture”, Electron J Combin, 12:1 (2005), R48  mathscinet  isi
    2. А. Н. Глебов, Д. Ж. Замбалаева, “Путевые разбиения планарных графов”, Сиб. электрон. матем. изв., 4 (2007), 450–459  mathnet  mathscinet  zmath
    3. Д. Ж. Замбалаева, “Разбиение плоского графа с обхватом 7 на два звёздных леса”, Дискретн. анализ и исслед. опер., 16:3 (2009), 20–46  mathnet  mathscinet  zmath
    4. Katrenic P., Semanisin G., “A note on the Path Kernel Conjecture”, Discrete Math, 309:8 (2009), 2551–2554  crossref  mathscinet  zmath  isi  scopus
    5. He W., Wang B., “A note on path kernels and partitions”, Discrete Math, 310:21 (2010), 3040–3042  crossref  mathscinet  zmath  isi  scopus
    6. Glebov A.N. Zhamyanovna Z.D., “Path Partitioning Planar Graphs of Girth 4 Without Adjacent Short Cycles”, Sib. Electron. Math. Rep., 15 (2018), 1040–1047  mathnet  crossref  mathscinet  zmath  isi
  • Дискретный анализ и исследование операций
    Просмотров:
    Эта страница:262
    Полный текст:81
    Литература:41
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021