Аннотация:
Функция $f:E(G)\longrightarrow \mathbb{Z}_{\geq 0}$ называется реберной раскраской графа $G$. Реберная раскраска $f$ графа $G$ называется правильной, если для любых смежных ребер $e$ и $e'$ из графа $G~~f(e)\not=f(e')$. Правильная реберная раскраска называется вершинно-различающей, если для любых двух различных вершин $u,v \in V(G)$, $S(u,f) \ne S(v,f)$, где $S(v,f) = \{f(e) \ | \ e = wv \in E(G)\}$. Наименьшее количество цветов, необходимое для вершинно-различающей реберной раскраски графа $G$ называется вершинно-различающим хроматическим индексом и обозначается через $\chi'_{vd}(G)$. В этой статье представлены верхние и нижние оценки вершинно-различающего хроматического индекса соединения двух графов.
Полный текст:
PDF файл (228 kB)