|
Дискретн. анализ и исслед. опер., сер. 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
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
Frick M., Schiermeyer I., “An asymptotic result for the Path Partition Conjecture”, Electron J Combin, 12:1 (2005), R48
-
А. Н. Глебов, Д. Ж. Замбалаева, “Путевые разбиения планарных графов”, Сиб. электрон. матем. изв., 4 (2007), 450–459
-
Д. Ж. Замбалаева, “Разбиение плоского графа с обхватом 7 на два звёздных леса”, Дискретн. анализ и исслед. опер., 16:3 (2009), 20–46
-
Katrenic P., Semanisin G., “A note on the Path Kernel Conjecture”, Discrete Math, 309:8 (2009), 2551–2554
-
He W., Wang B., “A note on path kernels and partitions”, Discrete Math, 310:21 (2010), 3040–3042
-
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
|
Просмотров: |
Эта страница: | 262 | Полный текст: | 81 | Литература: | 41 |
|