The Rainbow Vertex-disconnection in Graphs

• 作者: Xu Qing BAI You CHEN Ping LI Xue Liang LI Yin Di WENG
• 来源期刊: 数学学报（英文版）
• 年，卷（期）: 2021,（2）
• 页码范围: 249-261
• 页数: 13页
• 语种: 英文

摘要

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 rainbow vertex-disconnected if for any two vertices x and y of G, there exists a vertex subset S of G such that when x and y are nonadjacent, S is rainbow and x and y belong to diff erent components of G?S;whereas when x and y are adjacent, S+x or S+y is rainbow and x and y belong to diff erent components of (G?xy)?S. For a connected graph G, the 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 characterize all graphs of order n with rainbow vertex-disconnection number k for k ∈ {1, 2, n}, and determine the rainbow vertex-disconnection numbers of some special graphs. Moreover, we study the extremal problems on the number of edges of a connected graph G with order n and rvd(G)=k for given integers k and n with 1≤k≤n.