Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn various (strong) rainbow connection numbers of graphs
158
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
An edge-coloured path is emph{rainbow} if all the edges have distinct colours. For a connected graph $G$, the emph{rainbow connection number} $rc(G)$ is the minimum number of colours in an edge-colouring of $G$ such that, any two vertices are connected by a rainbow path. Similarly, the emph{strong rainbow connection number} $src(G)$ is the minimum number of colours in an edge-colouring of $G$ such that, any two vertices are connected by a rainbow geodesic (i.e., a path of shortest length). These two concepts of connectivity in graphs were introduced by Chartrand et al.~in 2008. Subsequently, vertex-colour
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.
Let $k$ be a positive integer, and $G$ be a $k$-connected graph. An edge-coloured path is emph{rainbow} if all of its edges have distinct colours. The emph{rainbow $k$-connection number} of $G$, denoted by $rc_k(G)$, is the minimum number of colours in an edge-colouring of $G$ such that, any two vertices are connected by $k$ internally vertex-disjoint rainbow paths. The function $rc_k(G)$ was introduced by Chartrand, Johns, McKeon and Zhang in 2009, and has since attracted significant interest. Let $t_k(n,r)$ denote the minimum number of edges in a $k$-connected graph $G$ on $n$ vertices with $rc_k(G)le r$. Let $s_k(n,r)$ denote the maximum number of edges in a $k$-connected graph $G$ on $n$ vertices with $rc_k(G)ge r$. The functions $t_1(n,r)$ and $s_1(n,r)$ have previously been studied by various authors. In this paper, we study the functions $t_2(n,r)$ and $s_2(n,r)$. We determine bounds for $t_2(n,r)$ which imply that $t_2(n,2)=(1+o(1))nlog_2 n$, and $t_2(n,r)$ is linear in $n$ for $rge 3$. We also provide some remarks about the function $s_2(n,r)$.
A path in an(a) edge(vertex)-colored graph is called a conflict-free path if there exists a color used on only one of its edges(vertices). An(A) edge(vertex)-colored graph is called conflict-free (vertex-)connected if for each pair of distinct vertices, there is a conflict-free path connecting them. For a connected graph $G$, the conflict-free (vertex-)connection number of $G$, denoted by $cfc(G)(text{or}~vcfc(G))$, is defined as the smallest number of colors that are required to make $G$ conflict-free (vertex-)connected. In this paper, we first give the exact value $cfc(T)$ for any tree $T$ with diameters $2,3$ and $4$. Based on this result, the conflict-free connection number is determined for any graph $G$ with $diam(G)leq 4$ except for those graphs $G$ with diameter $4$ and $h(G)=2$. In this case, we give some graphs with conflict-free connection number $2$ and $3$, respectively. For the conflict-free vertex-connection number, the exact value $vcfc(G)$ is determined for any graph $G$ with $diam(G)leq 4$.
Given graphs $G$ and $H$ and a positive integer $k$, the emph{Gallai-Ramsey number}, denoted by $gr_{k}(G : H)$ is defined to be the minimum integer $n$ such that every coloring of $K_{n}$ using at most $k$ colors will contain either a rainbow copy of $G$ or a monochromatic copy of $H$. We consider this question in the cases where $G in {P_{4}, P_{5}}$. In the case where $G = P_{4}$, we completely solve the Gallai-Ramsey question by reducing to the $2$-color Ramsey numbers. In the case where $G = P_{5}$, we conjecture that the problem reduces to the $3$-color Ramsey numbers and provide several results in support of this conjecture.
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$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
