BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Yindi Weng

Yindi Weng appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COComputational Complexity

Catalog footprint

What is connected

3works
2topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

3 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access
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$.

0 citations0 reviewsNo code linkedOpen access