Том 9, серия 1, номер 2 , 2002 г., Стр. 21-35

УДК 519.177
Л. С. Мельников, И. В. Петренко
О путевых ядрах и разбиениях в неориентированных графах

Аннотация:
Пусть $\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.

Мельников Л. С. ¹
Петренко И. В. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Статья поступила 13 ноября 2001 г.
Исправленный вариант — 20 февраля 2002 г.