The Rainbow Vertex-disconnection in Graphs |
| |
Authors: | Xu Qing BAI You CHEN Ping LI Xue Liang LI Yin Di WENG |
| |
Institution: | 1. Center for Combinatorics and LPMC, Nankai University, Tianjin 300071, P. R. China;
2. School of Mathematics and Statistics, Qinghai Normal University, Xining 810008, P. R. China |
| |
Abstract: | 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 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. 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. |
| |
Keywords: | Vertex-coloring connectivity rainbow vertex-cut rainbow vertex-disconnection number |
本文献已被 CNKI 等数据库收录! |
| 点击此处可从《数学学报(英文版)》浏览原始摘要信息 |
| 点击此处可从《数学学报(英文版)》下载免费的PDF全文 |
|