论文标题
图表中的强彩虹断开连接
Strong rainbow disconnection in graphs
论文作者
论文摘要
令$ g $为非平凡的边缘连接图。如果没有两个边缘的$ r $用相同的颜色颜色，则$ g $的边缘$ r $ $ r $称为{\ it rainbow edge-cut}。对于两个不同的顶点$ u $和$ g $的$ v $，如果边缘切割将它们分开，则边缘切割称为{\ it $ u $ - $ -V $ -V $ -EDGE-CUT}。 An edge-colored graph $G$ is called \emph{strong rainbow disconnected} if for every two distinct vertices $u$ and $v$ of $G$, there exists a both rainbow and minimum $u$-$v$-edge-cut ({\it rainbow minimum $u$-$v$-edge-cut} for short) in $G$, separating them, and this edge-coloring is called a {\it strong彩虹断开着色}（简称为srd- {\ it coloring} $ g $）。对于连接的图形$ g $，\ emph {strong Rainbow disnection number}（srd - {\ it number}的$ g $）的$ g $，由$ \ textnormal {srd}（g）$表示，是$ $ g $ g $ g $ g $ g $ g $ g $ gront strong strong strong strong strong strong vainbow deconnection所需的最小颜色。 在本文中，我们首先用$ m $边缘来表征图形，以使每个$ k \ in \ {1,2，m \} $分别为$ \ textnormal {srd}（g）= k $，我们还表明，非trivial Connected Graph $ g $ g $ g $ ember srd number srd number srd-number srd-number in blace srd number a $ g $其次，我们研究了完整的$ K $ - 明确图，$ k $ - 连接$ k $的$ k $ - 等级图和网格图的SRD-numbers。最后，我们表明，对于连接的图形$ g $，用于计算$ \ textnormal {srd}（g）$是np-hard。特别是，我们表明，决定连接的立方体图$ \ textNormal {srd}（g）= 3 $是否已经完成了NP完整。此外，我们表明，对于给定的边缘色（具有无限数量的颜色）连接的图形$ g $它是NP的完整组件，以决定$ g $是否强烈彩虹断开。
Let $G$ be a nontrivial edge-colored connected graph. An edge-cut $R$ of $G$ is called a {\it rainbow edge-cut} if no two edges of $R$ are colored with the same color. For two distinct vertices $u$ and $v$ of $G$, if an edge-cut separates them, then the edge-cut is called a {\it $u$-$v$-edge-cut}. An edge-colored graph $G$ is called \emph{strong rainbow disconnected} if for every two distinct vertices $u$ and $v$ of $G$, there exists a both rainbow and minimum $u$-$v$-edge-cut ({\it rainbow minimum $u$-$v$-edge-cut} for short) in $G$, separating them, and this edge-coloring is called a {\it strong rainbow disconnection coloring} (srd-{\it coloring} for short) of $G$. For a connected graph $G$, the \emph{strong rainbow disconnection number} (srd-{\it number} for short) of $G$, denoted by $\textnormal{srd}(G)$, is the smallest number of colors that are needed in order to make $G$ strong rainbow disconnected. In this paper, we first characterize the graphs with $m$ edges such that $\textnormal{srd}(G)=k$ for each $k \in \{1,2,m\}$, respectively, and we also show that the srd-number of a nontrivial connected graph $G$ equals the maximum srd-number among the blocks of $G$. Secondly, we study the srd-numbers for the complete $k$-partite graphs, $k$-edge-connected $k$-regular graphs and grid graphs. Finally, we show that for a connected graph $G$, to compute $\textnormal{srd}(G)$ is NP-hard. In particular, we show that it is already NP-complete to decide if $\textnormal{srd}(G)=3$ for a connected cubic graph. Moreover, we show that for a given edge-colored (with an unbounded number of colors) connected graph $G$ it is NP-complete to decide whether $G$ is strong rainbow disconnected.
