BZPEER

preprint2020arXiv

Complexity results for two kinds of colored disconnections of graphs

The concept of rainbow disconnection number of graphs was introduced by Chartrand et al. in 2018. Inspired by this concept, we put forward the concepts of rainbow vertex-disconnection and proper disconnection in graphs. In this paper, we first show that it is $NP$ -complete to decide whether a given edge-colored graph $G$ with maximum degree $Δ(G)=4$ is proper disconnected. Then, for a graph $G$ with $Δ(G)\leq 3$ we show that $pd(G)\leq 2$ and determine the graphs with $pd(G)=1$ and $2$ , respectively. Furthermore, we show that for a general graph $G$ , deciding whether $pd(G)=1$ is $NP$ -complete, even if $G$ is bipartite. We also show that it is $NP$ -complete to decide whether a given vertex-colored graph $G$ is rainbow vertex-disconnected, even though the graph $G$ has $Δ(G)=3$ or is bipartite.

preprint2020arXiv

Further results on the rainbow vertex-disconnection of graphs

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$ .

preprint2020arXiv

The rainbow vertex-disconnection in graphs

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$ 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 \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 characterize all graphs of order $n$ with rainbow vertex-disconnection number $k$ for $k\in\{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\leq k\leq n$ .

Yindi Weng

Research overview

Is this your work?

3 publications

Complexity results for two kinds of colored disconnections of graphs

Further results on the rainbow vertex-disconnection of graphs

The rainbow vertex-disconnection in graphs

See the researcher in context

Building this map preview