The Rainbow Vertex-disconnection in Graphs
- PDF / 245,609 Bytes
- 13 Pages / 510.236 x 737.008 pts Page_size
- 45 Downloads / 194 Views
Acta Mathematica Sinica, English Series Springer-Verlag GmbH Germany & The Editorial Office of AMS 2020
The Rainbow Vertex-disconnection in Graphs Xu Qing BAI
You CHEN
Ping LI
Center for Combinatorics and LPMC, Nankai University, Tianjin 300071, P. R. China [email protected] E-mail : [email protected] chen [email protected]
Xue Liang LI1) Center for Combinatorics and LPMC, Nankai University, Tianjin 300071, P. R. China and School of Mathematics and Statistics, Qinghai Normal University, Xining 810008, P. R. China E-mail : [email protected]
Yin Di WENG Center for Combinatorics and LPMC, Nankai University, Tianjin 300071, P. R. China E-mail : [email protected] 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 vertexdisconnected. 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
MR(2010) Subject Classification
1
05C15, 05C40
Introduction
All graphs considered in this paper are simple, finite and undirected. Let G = (V (G), E(G)) be a nontrivial connected graph with vertex set V (G) and edge set E(G). The order of G is denoted by n = |V (G)|. For a vertex v ∈ V (G), the open neighborhood of v is the set N (v) = {u ∈ V (G) | uv ∈ E(G)} and d(v) = |N (v)| is the degree of v, and the closed neighborhood of v is the set N [v] = N (v) ∪ {v}. The minimum and maximum degree of G are denoted by δ(G) Received February 23, 2020, accepted June 5, 2020 Supported by National Natural Science Foundation of China (Grant Nos. 11871034, 11531011) and Natural Science Foundation of Qinghai (Grant No. 2017-ZJ-790) 1) Corresponding author
2
Bai X. Q. et al.
and Δ(G), respectively. Denote by Pn a path on n vertices. For a subset S of V (G), we use G[S] to denote the subgraph of G induced by S. Let V1 , V2 be two disjoint vertex subsets of G. We denote the set of edges between V1 and V2 in G by E(V1 , V2 ). We follow [2] for graph theoretical notation and terminology not defined here. The concept of rainbow connection coloring was introduced by Chartrand et al. [3] in 2008. A rainbow path is a path whose edges are colored pairwise diffe
Data Loading...
