Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFurther results on the rainbow vertex-disconnection of graphs
114
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic 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 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 $kgeqfrac{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-5leq rvd(G)+rvd(overline{G})leq 2n$ and $n-1leq 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 $ngeq 24$.
rate research
Read More
Let $G$ be a nontrivial edge-colored connected graph. An edge-cut $R$ of $G$ is called a {it rainbow edge-cut} if no two edges of $R$ are colored with the same color. For two distinct vertices $u$ and $v$ of $G$, if an edge-cut separates them, then the edge-cut is called a {it $u$-$v$-edge-cut}. An edge-colored graph $G$ is called emph{strong rainbow disconnected} if for every two distinct vertices $u$ and $v$ of $G$, there exists a both rainbow and minimum $u$-$v$-edge-cut ({it rainbow minimum $u$-$v$-edge-cut} for short) in $G$, separating them, and this edge-coloring is called a {it strong rainbow disconnection coloring} (srd-{it coloring} for short) of $G$. For a connected graph $G$, the emph{strong rainbow disconnection number} (srd-{it number} for short) of $G$, denoted by $textnormal{srd}(G)$, is the smallest number of colors that are needed in order to make $G$ strong rainbow disconnected. In this paper, we first characterize the graphs with $m$ edges such that $textnormal{srd}(G)=k$ for each $k in {1,2,m}$, respectively, and we also show that the srd-number of a nontrivial connected graph $G$ equals the maximum srd-number among the blocks of $G$. Secondly, we study the srd-numbers for the complete $k$-partite graphs, $k$-edge-connected $k$-regular graphs and grid graphs. Finally, we show that for a connected graph $G$, to compute $textnormal{srd}(G)$ is NP-hard. In particular, we show that it is already NP-complete to decide if $textnormal{srd}(G)=3$ for a connected cubic graph. Moreover, we show that for a given edge-colored (with an unbounded number of colors) connected graph $G$ it is NP-complete to decide whether $G$ is strong rainbow disconnected.
An edge-cut $R$ of an edge-colored connected graph is called a rainbow-cut if no two edges in the edge-cut are colored the same. An edge-colored graph is rainbow disconnected if for any two distinct vertices $u$ and $v$ of the graph, there exists a $u$-$v$-rainbow-cut separating them. For a connected graph $G$, the rainbow disconnection number of $G$, denoted by rd$(G)$, is defined as the smallest number of colors that are needed in order to make $G$ rainbow disconnected. In this paper, we first give some tight upper bounds for rd$(G)$, and moreover, we completely characterize the graphs which meet the upper bound of the Nordhaus-Gaddum type results obtained early by us. Secondly, we propose a conjecture that $lambda^+(G)leq textnormal{rd}(G)leq lambda^+(G)+1$, where $lambda^+(G)$ is the upper edge-connectivity, and prove the conjecture for many classes of graphs, to support it. Finally, we give the relationship between rd$(G)$ of a graph $G$ and the rainbow vertex-disconnection number rvd$(L(G))$ of the line graph $L(G)$ of $G$.
A emph{proper $t$-edge-coloring} of a graph $G$ is a mapping $alpha: E(G)rightarrow {1,ldots,t}$ such that all colors are used, and $alpha(e) eq alpha(e^{prime})$ for every pair of adjacent edges $e,e^{prime}in E(G)$. If $alpha $ is a proper edge-coloring of a graph $G$ and $vin V(G)$, then emph{the spectrum of a vertex $v$}, denoted by $Sleft(v,alpha right)$, is the set of all colors appearing on edges incident to $v$. emph{The deficiency of $alpha$ at vertex $vin V(G)$}, denoted by $def(v,alpha)$, is the minimum number of integers which must be added to $Sleft(v,alpha right)$ to form an interval, and emph{the deficiency $defleft(G,alpharight)$ of a proper edge-coloring $alpha$ of $G$} is defined as the sum $sum_{vin V(G)}def(v,alpha)$. emph{The deficiency of a graph $G$}, denoted by $def(G)$, is defined as follows: $def(G)=min_{alpha}defleft(G,alpharight)$, where minimum is taken over all possible proper edge-colorings of $G$. For a graph $G$, the smallest and the largest values of $t$ for which it has a proper $t$-edge-coloring $alpha$ with deficiency $def(G,alpha)=def(G)$ are denoted by $w_{def}(G)$ and $W_{def}(G)$, respectively. In this paper, we obtain some bounds on $w_{def}(G)$ and $W_{def}(G)$. In particular, we show that for any $lin mathbb{N}$, there exists a graph $G$ such that $def(G)>0$ and $W_{def}(G)-w_{def}(G)geq l$. It is known that for the complete graph $K_{2n+1}$, $def(K_{2n+1})=n$ ($nin mathbb{N}$). Recently, Borowiecka-Olszewska, Drgas-Burchardt and Ha{l}uszczak posed the following conjecture on the deficiency of near-complete graphs: if $nin mathbb{N}$, then $def(K_{2n+1}-e)=n-1$. In this paper, we confirm this conjecture.
We provide precise asymptotic estimates for the number of several classes of labelled cubic planar graphs, and we analyze properties of such random graphs under the uniform distribution. This model was first analyzed by Bodirsky et al. (Random Structures Algorithms 2007). We revisit their work and obtain new results on the enumeration of cubic planar graphs and on random cubic planar graphs. In particular, we determine the exact probability of a random cubic planar graph being connected, and we show that the distribution of the number of triangles in random cubic planar graphs is asymptotically normal with linear expectation and variance. To the best of our knowledge, this is the first time one is able to determine the asymptotic distribution for the number of copies of a fixed graph containing a cycle in classes of random planar graphs arising from planar maps.
A close relation between hitting times of the simple random walk on a graph, the Kirchhoff index, resistance-centrality, and related invariants of unicyclic graphs is displayed. Combining with the graph transformations and some other techniques, sharp upper and lower bounds on the cover cost (resp. reverse cover cost) of a vertex in an $n$-vertex unicyclic graph are determined. All the corresponding extremal graphs are identified, respectively.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
