Nordhaus–Gaddum-Type Theorem for Rainbow Connection Number of Graphs

An edge-colored graph G is rainbow connected if every two vertices of G are connected by a path whose edges have distinct colors. The rainbow connection number of G, denoted by rc(G), is the minimum number of colors that are needed to make G rainbow connected. In this paper we give a Nordhaus–Gaddum-type result for the rainbow connection number. We prove that if G and ${\overline{G}}$ are both connected, then ${4\leq rc(G)+rc(\overline{G})\leq n+2}$ . Examples are given to show that the upper bound is sharp for n ≥ 4, and the lower bound is sharp for n ≥ 8. Sharp lower bounds are also given for n = 4, 5, 6, 7, respectively.     

Upper Bounds for the Rainbow Connection Numbers of Line Graphs

A path in an edge-colored graph G, where adjacent edges may be colored the same, is called a rainbow path if no two edges of it are colored the same. A nontrivial connected graph G is rainbow connected if for any two vertices of G there is a rainbow path connecting them. The rainbow connection number of G, denoted rc(G), is defined as the smallest number of colors such that G is rainbow connected. In this paper, we mainly study the rainbow connection number rc(L(G)) of the line graph L(G) of a graph G which contains triangles. We get two sharp upper bounds for rc(L(G)), in terms of the number of edge-disjoint triangles of G. We also give results on the iterated line graphs.     

Rainbow Connection Number and Radius

The rainbow connection number, rc(G), of a connected graph G is the minimum number of colours needed to colour its edges, so that every pair of its vertices is connected by at least one path in which no two edges are coloured the same. In this note we show that for every bridgeless graph G with radius r, rc(G) ≤  r(r + 2). We demonstrate that this bound is the best possible for rc(G) as a function of r, not just for bridgeless graphs, but also for graphs of any stronger connectivity. It may be noted that for a general 1-connected graph G, rc(G) can be arbitrarily larger than its radius (K _1,n for instance). We further show that for every bridgeless graph G with radius r and chordality (size of a largest induced cycle) k, rc(G) ≤  rk. Hitherto, the only reported upper bound on the rainbow connection number of bridgeless graphs is 4n/5 ? 1, where n is order of the graph (Caro et al. in Electron J Comb 15(1):Research paper 57, 13, 2008). It is known that computing rc(G) is NP-Hard (Chakraborty and fischer in J Comb Optim 1–18, 2009). Here, we present a (r + 3)-factor approximation algorithm which runs in O(nm) time and a (d + 3)-factor approximation algorithm which runs in O(dm) time to rainbow colour any connected graph G on n vertices, with m edges, diameter d and radius r.     

Rainbow Connection Number of Graph Power and Graph Products

Rainbow connection number, rc(G), of a connected graph G is the minimum number of colors needed to color its edges so that every pair of vertices is connected by at least one path in which no two edges are colored the same (note that the coloring need not be proper). In this paper we study the rainbow connection number with respect to three important graph product operations (namely the Cartesian product, the lexicographic product and the strong product) and the operation of taking the power of a graph. In this direction, we show that if G is a graph obtained by applying any of the operations mentioned above on non-trivial graphs, then rc(G) ≤ 2r(G) + c, where r(G) denotes the radius of G and \({c \in \{0, 1, 2\}}\) . In general the rainbow connection number of a bridgeless graph can be as high as the square of its radius [1]. This is an attempt to identify some graph classes which have rainbow connection number very close to the obvious lower bound of diameter (and thus the radius). The bounds reported are tight up to additive constants. The proofs are constructive and hence yield polynomial time \({(2 + \frac{2}{r(G)})}\) -factor approximation algorithms.     

The rainbow connection of a graph is (at most) reciprocal to its minimum degree

An edge‐colored graph Gis rainbow edge‐connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection of a connected graph G, denoted by rc(G), is the smallest number of colors that are needed in order to make Grainbow edge‐connected. We prove that if Ghas nvertices and minimum degree δ then rc(G)<20n/δ. This solves open problems from Y. Caro, A. Lev, Y. Roditty, Z. Tuza, and R. Yuster (Electron J Combin 15 (2008), #R57) and S. Chakrborty, E. Fischer, A. Matsliah, and R. Yuster (Hardness and algorithms for rainbow connectivity, Freiburg (2009), pp. 243–254). A vertex‐colored graph Gis rainbow vertex‐connected if any two vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex‐connection of a connected graph G, denoted by rvc(G), is the smallest number of colors that are needed in order to make Grainbow vertex‐connected. One cannot upper‐bound one of these parameters in terms of the other. Nevertheless, we prove that if Ghas nvertices and minimum degree δ then rvc(G)<11n/δ. We note that the proof in this case is different from the proof for the edge‐colored case, and we cannot deduce one from the other. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 185–191, 2010     

Rainbow Connection and Graph Products

A path in an edge colored graph G is called a rainbow path if all its edges have pairwise different colors. Then G is rainbow connected if there exists a rainbow path between every pair of vertices of G and the least number of colors needed to obtain a rainbow connected graph is the rainbow connection number. If we demand that there must exist a shortest rainbow path between every pair of vertices, we speak about strongly rainbow connected graph and the strong rainbow connection number. In this paper we study the (strong) rainbow connection number on the direct, strong, and lexicographic product and present several upper bounds for these products that are attained by many graphs. Several exact results are also obtained.     

Polynomial algorithm for sharp upper bound of rainbow connection number of maximal outerplanar graphs

For a finite simple edge-colored connected graph G (the coloring may not be proper), a rainbow path in G is a path without two edges colored the same; G is rainbow connected if for any two vertices of G, there is a rainbow path connecting them. Rainbow connection number, rc(G), of G is the minimum number of colors needed to color its edges such that G is rainbow connected. Chakraborty et al. (2011) [5] proved that computing rc(G) is NP-hard and deciding if rc(G)=2 is NP-complete. When edges of G are colored with fixed number k of colors, Kratochvil [6] proposed a question: what is the complexity of deciding whether G is rainbow connected? is this an FPT problem? In this paper, we prove that any maximal outerplanar graph is k rainbow connected for suitably large k and can be given a rainbow coloring in polynomial time.     

Bounds on the 2-Rainbow Domination Number of Graphs

A 2-rainbow domination function of a graph G is a function f that assigns to each vertex a set of colors chosen from the set {1, 2}, such that for any ${v\in V(G), f(v)=\emptyset}$ implies ${\bigcup_{u\in N(v)}f(u)=\{1,2\}.}$ The 2-rainbow domination number γ _r2(G) of a graph G is the minimum ${w(f)=\Sigma_{v\in V}|f(v)|}$ over all such functions f. Let G be a connected graph of order |V(G)| = n ≥ 3. We prove that γ _r2(G) ≤ 3n/4 and we characterize the graphs achieving equality. We also prove a lower bound for 2-rainbow domination number of a tree using its domination number. Some other lower and upper bounds of γ _r2(G) in terms of diameter are also given.     

Rainbow Connection Number and Independence Number of a Graph

A path in an edge-colored graph is called rainbow if any two edges of the path have distinct colors. An edge-colored graph is called rainbow connected if there exists a rainbow path between every two vertices of the graph. For a connected graph G, the minimum number of colors that are needed to make G rainbow connected is called the rainbow connection number of G, denoted by rc(G). In this paper, we investigate the relation between the rainbow connection number and the independence number of a graph. We show that if G is a connected graph without pendant vertices, then \(\mathrm{rc}(G)\le 2\alpha (G)-1\). An example is given showing that the upper bound \(2\alpha (G)-1\) is equal to the diameter of G, and so the upper bound is sharp since the diameter of G is a lower bound of \(\mathrm{rc}(G)\).     

Neighbor Sum Distinguishing Index

We consider proper edge colorings of a graph G using colors of the set {1, . . . , k}. Such a coloring is called neighbor sum distinguishing if for any pair of adjacent vertices x and y the sum of colors taken on the edges incident to x is different from the sum of colors taken on the edges incident to y. The smallest value of k in such a coloring of G is denoted by ndi_Σ(G). In the paper we conjecture that for any connected graph G ≠ C ₅ of order n ≥ 3 we have ndi_Σ(G) ≤ Δ(G) + 2. We prove this conjecture for several classes of graphs. We also show that ndi_Σ(G) ≤ 7Δ(G)/2 for any graph G with Δ(G) ≥ 2 and ndi_Σ(G) ≤ 8 if G is cubic.     

Total Rainbow Connection Number and Complementary Graph

A vertex-colored graph G is rainbow vertex connected if any two distinct vertices are connected by a path whose internal vertices have distinct colors. The rainbow vertex connection number of G, denoted by rvc(G), is the smallest number of colors that are needed in order to make G rainbow vertex connected. In this paper, we prove that for a connected graph G, if \({{\rm diam}(\overline{G}) \geq 3}\), then \({{\rm rvc}(G) \leq 2}\), and this bound is tight. Next, we obtain that for a triangle-free graph \({\overline{G}}\) with \({{\rm diam}(\overline{G}) = 2}\), if G is connected, then \({{\rm rvc}(G) \leq 2}\), and this bound is tight. A total-colored path is total rainbow if its edges and internal vertices have distinct colors. A total-colored graph G is total rainbow connected if any two distinct vertices are connected by some total rainbow path. The total rainbow connection number of G, denoted by trc(G), is the smallest number of colors required to color the edges and vertices of G in order to make G total rainbow connected. In this paper, we prove that for a triangle-free graph \({\overline{G}}\) with \({{\rm diam}(\overline{G}) = 3}\), if G is connected, then trc\({(G) \leq 5}\), and this bound is tight. Next, a Nordhaus–Gaddum-type result for the total rainbow connection number is provided. We show that if G and \({\overline{G}}\) are both connected, then \({6 \leq {\rm trc} (G) + {\rm trc}(\overline{G}) \leq 4n - 6.}\) Examples are given to show that the lower bound is tight for \({n \geq 7}\) and n = 5. Tight lower bounds are also given for n = 4, 6.     

Upper bound involving parameter σ 2 for the rainbow connection number

Let G be a connected graph of order n. The rainbow connection number rc（G） of G was introduced by Chartrand et al. Chandran et al. used the minimum degree of G and obtained an upper bound that rc（G） 〈_ 3n/（ δ＋ 1） - 3, which is tight up to additive factors. In this paper, we use the minimum degree-sum a2 6n of G to obtain a better bound rc（G） _〈 - 8, especially when is small （constant） but a2 is large （linear in n）.     

Graphs with small total rainbow connection number

A total-colored path is total rainbow if its edges and internal vertices have distinct colors. A total-colored graph G is total rainbow connected if any two distinct vertices are connected by some total rainbow path. The total rainbow connection number of G, denoted by trc(G), is the smallest number of colors required to color the edges and vertices of G in order to make G total rainbow connected. In this paper, we investigate graphs with small total rainbow connection number. First, for a connected graph G, we prove that \({\text{trc(G) = 3 if}}\left( {\begin{array}{*{20}{c}}{n - 1} \\2\end{array}} \right) + 1 \leqslant \left| {{\text{E(G)}}} \right| \leqslant \left( {\begin{array}{*{20}{c}}n \\2\end{array}} \right) - 1\), and \({\text{trc(G)}} \leqslant {\text{6 if }}\left| {{\text{E(G)}}} \right| \geqslant \left( {\begin{array}{*{20}{c}}{n - 2} \\2\end{array}} \right) + 2\). Next, we investigate the total rainbow connection numbers of graphs G with |V(G)| = n, diam(G) ≥ 2, and clique number ω(G) = n ? s for 1 ≤ s ≤ 3. In this paper, we find Theorem 3 of [Discuss. Math. Graph Theory, 2011, 31(2): 313–320] is not completely correct, and we provide a complete result for this theorem.     

Rainbow Connection Number, Bridges and Radius

Let G be a connected graph. The notion of rainbow connection number rc(G) of a graph G was introduced by Chartrand et al. (Math Bohem 133:85–98, 2008). Basavaraju et al. (arXiv:1011.0620v1 [math.CO], 2010) proved that for every bridgeless graph G with radius r, ${rc(G)\leq r(r+2)}$ and the bound is tight. In this paper, we show that for a connected graph G with radius r and center vertex u, if we let D ^r  = {u}, then G has r?1 connected dominating sets ${ D^{r-1}, D^{r-2},\ldots, D^{1}}$ such that ${D^{r} \subset D^{r-1} \subset D^{r-2} \cdots\subset D^{1} \subset D^{0}=V(G)}$ and ${rc(G)\leq \sum_{i=1}^{r} \max \{2i+1,b_i\}}$ , where b _i is the number of bridges in E[D ⁱ , N(D ⁱ )] for ${1\leq i \leq r}$ . From the result, we can get that if ${b_i\leq 2i+1}$ for all ${1\leq i\leq r}$ , then ${rc(G)\leq \sum_{i=1}^{r}(2i+1)= r(r+2)}$ ; if b _i  > 2i + 1 for all ${1\leq i\leq r}$ , then ${rc(G)= \sum_{i=1}^{r}b_i}$ , the number of bridges of G. This generalizes the result of Basavaraju et al. In addition, an example is given to show that there exist infinitely graphs with bridges whose rc(G) is only dependent on the radius of G, and another example is given to show that there exist infinitely graphs with bridges whose rc(G) is only dependent on the number of bridges in G.     

Note on Minimally d-Rainbow Connected Graphs

An edge-colored graph G, where adjacent edges may have the same color, is rainbow connected if every two vertices of G are connected by a path whose edges have distinct colors. A graph G is d-rainbow connected if one can use d colors to make G rainbow connected. For integers n and d let t(n, d) denote the minimum size (number of edges) in d-rainbow connected graphs of order n. Schiermeyer got some exact values and upper bounds for t(n, d). However, he did not present a lower bound of t(n, d) for \({3 \leq d < \lceil\frac{n}{2}\rceil}\) . In this paper, we improve his lower bound of t(n, 2), and get a lower bound of t(n, d) for \({3 \leq d < \lceil\frac{n}{2}\rceil}\) .     

Acyclic edge coloring of subcubic graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and it is denoted by a^′(G). From a result of Burnstein it follows that all subcubic graphs are acyclically edge colorable using five colors. This result is tight since there are 3-regular graphs which require five colors. In this paper we prove that any non-regular connected graph of maximum degree 3 is acyclically edge colorable using at most four colors. This result is tight since all edge maximal non-regular connected graphs of maximum degree 3 require four colors.     

Rainbow faces in edge‐colored plane graphs

A face of an edge‐colored plane graph is called rainbow if the number of colors used on its edges is equal to its size. The maximum number of colors used in an edge coloring of a connected plane graph Gwith no rainbow face is called the edge‐rainbowness of G. In this paper we prove that the edge‐rainbowness of Gequals the maximum number of edges of a connected bridge face factor H of G, where a bridge face factor H of a plane graph Gis a spanning subgraph H of Gin which every face is incident with a bridge and the interior of any one face f∈F(G) is a subset of the interior of some face f′∈F(H). We also show upper and lower bounds on the edge‐rainbowness of graphs based on edge connectivity, girth of the dual graphs, and other basic graph invariants. Moreover, we present infinite classes of graphs where these equalities are attained. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 84–99, 2009     

On a conjecture by Plummer and Toft

The cyclic chromatic number χ_c(G) of a 2‐connected plane graph G is the minimum number of colors in an assigment of colors to the vertices of G such that, for every face‐bounding cycle f of G, the vertices of f have different colors. Plummer and Toft proved that, for a 3‐connected plane graph G, under the assumption Δ*(G) ≥ 42, where Δ*(G) is the size of a largest face of G, it holds that χ_c(G) ≤ Δ*(G) + 4. They conjectured that, if G is a 3‐connected plane graph, then χ_c>(G) ≤ Δ*(G) + 2. In the article the conjecture is proved for Δ*(G) ≥ 24. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 177–189, 1999     

Paired-Domination in Claw-Free Graphs

A paired-dominating set of a graph G is a dominating set of vertices whose induced subgraph has a perfect matching, while the paired-domination number, denoted by γ _pr (G), is the minimum cardinality of a paired-dominating set in G. In this paper we investigate the paired-domination number in claw-free graphs. Specifically, we show that γ _pr (G) ≤ (3n ? 1)/5 if G is a connected claw-free graph of order n with minimum degree at least three and that this bound is sharp.     

Some Remarks on Rainbow Connectivity

An edge (vertex) colored graph is rainbow‐connected if there is a rainbow path between any two vertices, i.e. a path all of whose edges (internal vertices) carry distinct colors. Rainbow edge (vertex) connectivity of a graph G is the smallest number of colors needed for a rainbow edge (vertex) coloring of G. In this article, we propose a very simple approach to studying rainbow connectivity in graphs. Using this idea, we give a unified proof of several known results, as well as some new ones.