论文标题
图形的彩虹顶点签发的进一步结果
Further results on the rainbow vertex-disconnection of graphs
论文作者
论文摘要
令$ g $为非平底连接和顶点色的图。如果$ x $中的任何两个顶点具有不同的颜色，则$ g $的顶点$ x $的子集$ x $称为彩虹。图$ g $称为\ emph {rainbow vertex-disconted}如果对于任何两个顶点$ x $和$ y $ g $的$ y $ $ g $，则存在一个顶点子集$ s $，因此，当$ x $ y $ x $ y $ n nonadjacent是$ s $ s $ is rainbow和$ x $ y $ x $ y $ y $ y $ y $ y $ y $ y $ g g g g g g g g g g g y components of $ g g-y $属于$ g g的$ g-y $；而当$ x $和$ y $相邻时，$ s+x $或$ s+y $ is是彩虹，$ x $，$ y $属于$（g-xy）-s $的不同组件。这样的顶点子集$ s $称为$ g $的\ emph {rainbow cortex-cut}。对于连接的图形$ g $，$ g $的\ emph {rainbow vertex-disconnection}，用$ rvd（g）$表示，是制造$ g $ g $ rainbow vertex-cossecontected所需的最低颜色数量。 在本文中，我们获得了图形的彩虹顶点 - 隔间数的边界，该图的最小程度和最大程度。对于$ k \ geq \ frac {n} {2} $，我们给出了图$ g $的最大尺寸的更紧密的上限。然后，我们将订单$ n $的图表与彩虹顶点交换号$ n-1 $ $ n-1 $，并获得图形$ g $的最大尺寸，$ rvd（g）= n-1 $。此外，我们获得了属性$ rvd（g（n，p））= n $的尖锐阈值函数，并证明几乎所有图形$ g $均具有$ rvd（g）= rvd（\ overline {g}）= n $。最后，我们获得了一些nordhaus-gaddum-type结果：$ n-5 \ leq rvd（g）+rvd（\ overline {g}）\ leq 2n $和$ n-1 \ leq rvd（g）\ cdot rvd（\ cdot rvd（\ edline {g}） $ g $和$ \ overline {g} $带订单$ n \ geq 24 $。
Let $G$ be a nontrivial connected and vertex-colored graph. A subset $X$ of the vertex set of $G$ is called rainbow if any two vertices in $X$ have distinct colors. The graph $G$ is called \emph{rainbow vertex-disconnected} if for any two vertices $x$ and $y$ of $G$, there exists a vertex subset $S$ such that when $x$ and $y$ are nonadjacent, $S$ is rainbow and $x$ and $y$ belong to different components of $G-S$; whereas when $x$ and $y$ are adjacent, $S+x$ or $S+y$ is rainbow and $x$ and $y$ belong to different components of $(G-xy)-S$. Such a vertex subset $S$ is called a \emph{rainbow vertex-cut} of $G$. For a connected graph $G$, the \emph{rainbow vertex-disconnection number} of $G$, denoted by $rvd(G)$, is the minimum number of colors that are needed to make $G$ rainbow vertex-disconnected. In this paper, we obtain bounds of the rainbow vertex-disconnection number of a graph in terms of the minimum degree and maximum degree of the graph. We give a tighter upper bound for the maximum size of a graph $G$ with $rvd(G)=k$ for $k\geq\frac{n}{2}$. We then characterize the graphs of order $n$ with rainbow vertex-disconnection number $n-1$ and obtain the maximum size of a graph $G$ with $rvd(G)=n-1$. Moreover, we get a sharp threshold function for the property $rvd(G(n,p))=n$ and prove that almost all graphs $G$ have $rvd(G)=rvd(\overline{G})=n$. Finally, we obtain some Nordhaus-Gaddum-type results: $n-5\leq rvd(G)+rvd(\overline{G})\leq 2n$ and $n-1\leq rvd(G)\cdot rvd(\overline{G})\leq n^2$ for the rainbow vertex-disconnection numbers of nontrivial connected graphs $G$ and $\overline{G}$ with order $n\geq 24$.
