论文标题
彩虹断开图的界限
Bounds for the rainbow disconnection number of graphs
论文作者
论文摘要
如果边缘切割中没有两个边缘的颜色相同，则边缘颜色连接的图形的边缘切割$ r $称为彩虹切割。如果对于图形的任何两个不同的顶点$ u $和$ v $，则将彩虹脱离彩虹的图形，则存在$ u $ -V $ -V $ -RAINBOW-CUT将它们分开。对于连接的图形$ g $，由RD $（g）$表示的$ G $的彩虹断开数字定义为为了使$ G $ rainbow断开连接所需的最小颜色。 在本文中，我们首先给出了RD $（G）$的一些紧密上限，此外，我们完全表征了符合我们早期获得的Nordhaus-Gaddum类型结果的图形。其次，我们提出了一个猜想，即$λ^+（g）\ leq \ textnormal {rd}（g）\leqλ^+（g）+1 $，其中$λ^+（g）$是上边缘连接性，并证明了许多图形的猜测，以支持它。最后，我们给出了图$ g $的rd $（g）$与$ g $ of line gragh $ l（g）$ of $ g $的Rainbow Vertex-Disconnnection rvd $（l（g））$之间的关系。
An edge-cut $R$ of an edge-colored connected graph is called a rainbow-cut if no two edges in the edge-cut are colored the same. An edge-colored graph is rainbow disconnected if for any two distinct vertices $u$ and $v$ of the graph, there exists a $u$-$v$-rainbow-cut separating them. For a connected graph $G$, the rainbow disconnection number of $G$, denoted by rd$(G)$, is defined as the smallest number of colors that are needed in order to make $G$ rainbow disconnected. In this paper, we first give some tight upper bounds for rd$(G)$, and moreover, we completely characterize the graphs which meet the upper bound of the Nordhaus-Gaddum type results obtained early by us. Secondly, we propose a conjecture that $λ^+(G)\leq \textnormal{rd}(G)\leq λ^+(G)+1$, where $λ^+(G)$ is the upper edge-connectivity, and prove the conjecture for many classes of graphs, to support it. Finally, we give the relationship between rd$(G)$ of a graph $G$ and the rainbow vertex-disconnection number rvd$(L(G))$ of the line graph $L(G)$ of $G$.
