solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看13312次
Hardness results for rainbow disconnection of graphs. (arXiv:1811.11939v1 [math.CO])
来源于:arXiv
Let $G$ be a nontrivial connected, edge-colored graph. An edge-cut $S$ of $G$
is called a rainbow cut if no two edges in $S$ are colored with a same color.
An edge-coloring of $G$ is a rainbow disconnection coloring if for every two
distinct vertices $s$ and $t$ of $G$, there exists a rainbow cut $S$ in $G$
such that $s$ and $t$ belong to different components of $G\setminus S$. For a
connected graph $G$, the {\it rainbow disconnection number} of $G$, denoted by
$rd(G)$, is defined as the smallest number of colors such that $G$ has a
rainbow disconnection coloring by using this number of colors. In this paper,
we show that for a connected graph $G$, computing $rd(G)$ is NP-hard. In
particular, it is already NP-complete to decide if $rd(G)=3$ for a connected
cubic graph. Moreover, we prove that for a given edge-colored (with an
unbounded number of colors) connected graph $G$ it is NP-complete to decide
whether $G$ is rainbow disconnected. 查看全文>>