# Oriented diameter and rainbow connection number of a graph.

1 IntroductionAll graphs in this paper are undirected, finite and simple. We refer to the book [2] for notation and terminology not described here. A path u = [u.sub.1], [u.sub.2], ..., [u.sub.k] = v is called a [P.sub.u,v] path. Denote by [u.sub.i][Pu.sub.j] the subpath [u.sub.i], [u.sub.i+1], ..., [u.sub.j] for i [greater than or equal to] j. The length l(P) of a path P is the number of edges in P. The distance between two vertices x and y in G, denoted by [d.sub.G](x, y), is the length of a shortest path between them. The eccentricity of a vertex x in G is [ecc.sub.G](x) = [max.sub.y[member of]V(G)]d(x,y). The radius and diameter of G are rad(G) = [min.sub.x[member of]y(G)] ecc(x) and diam(G) = [max.sub.x[member of]y(G)] ecc(x), respectively. A vertex u is a center of a graph G if ecc(u) = rad(G). The oriented diameter of a bridgeless graph G is min{diam(H)|H is an orientation of G}, and the oriented radius of a bridgeless graph G is min{rad(H)|H is an orientation of G}. For any graph G with edge-connectivity [lambda](G) = 0,1, G has oriented radius (resp. diameter) [infinity].

In 1939, Robbins solved the One-Way Street Problem and proved that a graph G admits a strongly connected orientation if and only if G is bridgeless, that is, G does not have any cut-edge. Naturally, one hopes that the oriented diameter of a bridgeless graph is as small as possible. Bondy and Murty suggested to study the quantitative variations on Robbins' theorem. In particular, they conjectured that there exists a function f such that every bridgeless graph with diameter d admits an orientation of diameter at most f (d).

In 1978, Chvatal and Thomassen [5] obtained some general bounds.

Theorem 1 (Chvatal and Thomassen 1978 [5]) For every bridgeless graph G, there exists an orientation H ofG such that

ra d(H) [greater than or equal to] rad[(G).sup.2] + rad(G),

diam(H) [greater than or equal to] 2rad[(G).sup.2] + 2rad(G).

Moreover, the above bounds are optimal.

There exists a minor error when they constructed the graph [G.sub.d] which arrives at the upper bound when d is odd. Kwok, Liu and West gave a slight correction in [11].

They also showed that determining whether an arbitrary graph can be oriented so that its diameter is at most 2 is NP-complete. Bounds for the oriented diameter of graphs have also been studied in terms of other parameters, for example, radius, dominating number [5, 6,11, 18], etc. Some classes of graphs have also been studied in [6, 7, 8, 9, 14].

Let [eta](G) be the smallest integer such that every edge of G belongs to a cycle of length at most [eta](G). In this paper, we show the following result.

Theorem 2 For every bridgeless graph G, there exists an orientation H of G such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Note that [[summation].sup.rad(G).sub.i=1] min{2i, [eta](G) - 1} [greater than or equal to] rad[(G).sup.2] + rad(G) and diam(H) [greater than or equal to] 2rad(H). So our result implies Chvatal and Thomassen's Theorem 1.

A path in an edge-colored graph G, where adjacent edges may have the same color, is called rainbow if no two edges of the path are colored the same. An edge-coloring of a graph G is a rainbow edge-coloring if every two distinct vertices of the graph G are connected by a rainbow path. The rainbow connection number rc(G) of G is the minimum integer k for which there exists a rainbow k-edge-coloring of G. It is easy to see that diam(G) [greater than or equal to] rc(G) for any connected graph G. The rainbow connection number was introduced by Chartrand et al. in [4]. It is of great use in transferring information of high security in multicomputer networks. We refer the readers to [3] for details.

Chakraborty et al. [3] investigated the hardness and algorithms for the rainbow connection number, and showed that given a graph G, deciding if rc(G) = 2 is NP-complete. Bounds for the rainbow connection number of a graph have also been studies in terms of other graph parameters, for example, radius, dominating number, minimum degree, connectivity, etc. [1, 4, 10]. Cayley graphs and line graphs were studied in [12] and [13], respectively.

A subgraph H of a graph G is called isometric if the distance between any two distinct vertices in H is the same as their distance in G. The size of a largest isometric cycle in G is denoted by [zeta](G). Clearly, every isometric cycle is an induced cycle and thus [zeta](G) is not larger than the chordality, where chordality is the length of a largest induced cycle in G. In [1], Basavaraju, Chandran, Rajendraprasad and Ramaswamy got the the following sharp upper bound for the rainbow connection number of a bridgeless graph G in terms of rad(G) and [zeta](G).

Theorem 3 (Basavaraju et al. [1]) For every bridgeless graph G,

rc(G) [greater than or equal to] [rad(G).summation over (i=1)] min{2i + 1, [zeta](G)} [greater than or equal to] rad(G)[zeta](G).

In this paper, we show the following result.

Theorem 4 For every bridgeless graph G,

rc(G) [greater than or equal to] [rad(G).summation over (i=1)] min{2i + 1, [eta](G)} [greater than or equal to] rad(G)[eta](G).

From Lemma 2 of Section 2, we will see that [eta](G) [greater than or equal to] [zeta](G). Thus our result implies Theorem 3.

This paper is organized as follows: in Section 2, we introduce some new definitions and show several lemmas. In Section 3, we prove Theorem 2 and study upper bounds for the oriented radius (resp. diameter) of plane graphs, edge-transitive graphs and general (bipartite) graphs. In Section 4, we prove Theorem 4 and study upper for the rainbow connection number of plane graphs, edge-transitive graphs and general (bipartite) graphs.

2 Preliminaries

In this section, we introduce some definitions and show several lemmas.

Definition 1 For any x [member of] V(G) and k [less than or equal to] 0, the k-step open neighborhood is {y|d(x, y) = k} and denoted by [N.sub.k](x), the k-step closed neighborhood is {y|d(x, y) [greater than or equal to] k} and denoted by [N.sub.k][x]. If k = 1, we simply write N(x) and N[x] for [N.sub.1](x) and [N.sub.1][x], respectively.

Definition 2 Let G be a graph and H be a subset of V(G) (or a subgraph of G). The edges between H and G\H are called legs of H. An H-ear is a path P = ([u.sub.0], [u.sub.1], ..., [u.sub.k]) in G such that V(H) [intersection] V (P) = {[u.sub.0], [u.sub.k]}. The vertices [u.sub.0], [u.sub.k] are called the feet of P in H and [u.sub.0][u.sub.1], [u.sub.k-1][u.sub.k] are called the legs of P. The length of an H-ear is the length of the corresponding path. If [u.sub.0] = [u.sub.k], then P is called a closed H ear. For any leg e of H, denote by 1(e) the smallest number such that there exists an H-ear of length 1(e) containing e, and such an H-ear is called an optimal (H, e)-ear.

Note that for any optimal (H, e)-ear P and every pair (x, y) [not equal to] ([u.sub.0], [u.sub.k]) of distinct vertices of P, x and y are adjacent on P if and only if x and y are adjacent in G.

Definition 3 For any two paths P and Q, the joint of P and Q are the common vertex and edge of P and Q. Paths P and Q have k continuous common segments if the common vertex and edge are k disjoint paths.

A common segment is trivial if it has only one vertex.

Definition 4 Let P and Q be two paths in G. Call P and Q independent if they has no common internal vertex.

Lemma 1 Let n [less than or equal to] 1 be an integer, and let G be a graph, H be a subgraph of G and [e.sub.i] = [u.sub.i][v.sub.i] be a leg of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be an optimal (G, [e.sub.i])-ear, where 1 [greater than or equal to] i [greater than or equal to] n and [u.sub.i], [w.sub.i] are the foot of [P.sub.i]. Then for any leg [e.sub.j] = [u.sub.j][v.sub.j] such that [e.sub.j] [not equal to] [e.sub.i] and [e.sub.j] [not member of] E([P.sub.i]), where i [member of] {1, 2, ..., n}, there exists an optimal [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that either [P.sub.i] and [P.sub.j] are independent for any [P.sub.i], 1 [greater than or equal to] i [greater than or equal to] n, or [P.sub.i] and [P.sub.j] have only one continuous common segment containing [w.sub.j] for some [P.sub.i].

Proof: Let [P.sub.j] be an optimal (H, [e.sub.j])-ear. If [P.sub.i] and [P.sub.j] are independent for any i, then we are done. Suppose that [P.sub.i] and [P.sub.j] have m continuous common segments for some i, where m [less than or equal to] 1. When m [less than or equal to] 2, we first construct an optimal (H, [e.sub.j])-ear [P.sup.*.sub.j] such that [P.sub.i] and [P.sup.*.sub.j] has only one continuous common segment. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be the m continuous common segments of [P.sub.i] and [P.sub.j] and they appear in [P.sub.i] in that order. See Figure 1 for details. Furthermore, suppose that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are the two ends of the path [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and they appear in [P.sub.i] successively. We say that the following claim holds.

Claim 1: l([y.sub.k][P.sub.i][x.sub.k+1]) = l([y.sub.k][P.sub.j][x.sub.k+1]) for any 1 [greater than or equal to] k [greater than or equal to] m - 1.

If not, that is, there exists an integer k such that l([y.sub.k][P.sub.i][x.sub.k+1]) [not equal to] l([y.sub.k][P.sub.j][x.sub.k+1]). Without loss of generality, we assume l([y.sub.k][P.sub.i][x.sub.k+1]) < l([y.sub.k][P.sub.j][x.sub.k+1]). Then we shall get a more shorter path H- ear containing [e.sub.j] by replacing [y.sub.k][P.sub.j][x.sub.k+1] with [y.sub.k][P.sub.i][x.sub.k+1], a contradiction. Thus l([y.sub.k][P.sub.j][x.sub.k+1]) = l([y.sub.k][P.sub.j][x.sub.k+1]) for any k.

Let [P.sup.*.sub.j] be the path obtained from [P.sub.j] by replacing [y.sub.k][P.sub.j][x.sub.k+1] with [y.sub.k][P.sub.i][x.sub.k+1], and let [P.sub.j] = [P.sup.*.sub.j]. If the continuous common segment of [P.sub.i] and [P.sub.j] does not contain [w.sub.j]. Suppose x and y are the two ends of the common segment such that x and y appeared on P starting from [u.sub.i] to [w.sub.i] successively. Similar to Claim 1, l(y[P.sub.i][w.sub.i]) = l(y[P.sub.j][w.sub.j]). Let [P.sup.*.sub.j] be the path obtained from [P.sub.j] by replacing y[P.sub.j][w.sub.j] with y[P.sub.i][w.sub.i]. Clearly, [P.sup.*.sub.j] is our desired optimal (H, [u.sub.j] [v.sub.j])-ear.

Lemma 2 For every bridgeless graph G, [eta](G) [greater than or equal to] [zeta](G).

Proof: Suppose that there exists an edge e such that the length l(C) of the smallest cycle C containing e is larger than [zeta](G). Then, C is not an isometric cycle since the length of a largest isometric cycle is [zeta](G). Thus there exist two vertices u and v on C such that [d.sub.G](u, v) < [d.sub.C](u, v). Let P be a shortest path between u and v in G. Then a closed trial C' containing e is obtained from the segment of C containing e between u and v by adding P. Clearly, the length l(C') is less than l(C). We can get a cycle C" containing e from C'. Thus there exists a cycle C" containing e with length less than l(C), a contradiction. Therefore [eta](G) [greater than or equal to] [zeta](G).

Lemma 3 Let G be a bridgeless graph and u be a center of G. For any i [greater than or equal to] rad(G) - 1 and every leg e of [N.sub.i](u), there exists an optimal ([N.sub.i][u], e)-ear with length at most min{2(rad(G) - i) + 1, [eta](G)}.

Proof: Let P be an optimal ([N.sub.i][u], e)-ear. Since e belongs to a cycle with length at most [eta](G), l(P) [greater than or equal to] [eta](G). On the other hand, if l(P) [less than or equal to] 2(rad(G) - i) + 1, then the middle vertex of P has distance at least rad(G) - i + 1 from [N.sub.i][u], a contradiction.

3 Oriented diameter

At first, we have the following observation.

Observation 1 Let G be a bridgeless graph and H be a bridgeless spanning subgraph of G. Then the oriented radius (resp. diameter) ofG is not larger than the oriented radius (resp. diameter) of H.

Proof of Theorem 2: We only need to show that G has an orientation H such that

rad(H) [greater than or equal to] [rad(G).summation over (i=1)] min{2i, [eta](G) - 1} [greater than or equal to] rad(G)([eta](G) - 1).

Let u be a center of G and let [H.sub.0] be the trivial graph with vertex set {u}. We assert that there exists a subgraph [G.sub.i] of G such that [N.sub.i][u] [subset or equal to] V ([G.sub.i]) and [G.sub.i] has an orientation [H.sub.i] satisfying that rad([H.sub.i]) [greater than or equal to] [ecc.sub.Hi](u) [greater than or equal to] [[summation].sup.i.sub.(j=1)] min{2(rad(G) - j), [eta](G) - 1}.

Basic step: When i = 1, we omit the proof since the proof of this step is similar to that of the following induction step.

Induction step: Assume that the above assertion holds for i - 1. Next we show that the above assertion also holds for i. For any v [member of] [N.sub.i](u), either v [member of] V([H.sub.i-1]) or v [member of] [N.sub.G](V([H.sub.i-1])) since [N.sub.i-1][u] [subset or equal to] V([H.sub.i-1]). If [N.sub.i](u) [subset or equal to] V([H.sub.i-1]), then let [H.sub.i] = [H.sub.i-1] and we are done. Thus, we suppose [N.sub.i](u) [not subset or equal to] V([H.sub.i-1]) in the following.

Let X = [N.sub.i](u)\V([H.sub.i-1]). Pick [x.sub.1] [member of] X, let [y.sub.1] be a neighbor of [x.sub.1] in [H.sub.i-1] and let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be an optimal ([H.sub.i-1], [x.sub.1][y.sub.1])-ear. We orient P such that [P.sub.1] is a directed path. Pick [x.sub.2] [member of] X satisfying that all incident edges of [x.sub.2] are not oriented. Let [y.sub.2] be a neighbor of [x.sub.2] in [H.sub.i-1]. If there exists an optimal ([H.sub.i-1], [x.sub.2][y.sub.2])-ear [P.sub.2] such that [P.sub.1] and [P.sub.2] are independent, then we can orient [P.sub.2] such that [P.sub.2] is a directed path. Otherwise, by Lemma 1 there exists an optimal [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that [P.sub.1] and [P.sub.2] has only one continuous common segment containing [z.sub.2]. Clearly, we can orient the edges in E([P.sub.2])\E([P.sub.1]) such that [P.sub.2] is a directed path. We can pick the vertices of X and oriented optimal H- ears similar to the above method until that for any x [member of] X, at least two incident edges of x are oriented. Let Hi be the graph obtained from [H.sub.i-1] by adding vertices in V(G)\V([H.sub.i-1]), which has at least two new oriented incident edges, and adding the new oriented edges. Clearly, [N.sub.i][u] [subset or equal to] V([H.sub.i]) = V([G.sub.i]).

Now we show that rad([H.sub.i]) [greater than or equal to] [[summation].sup.i.sub.j=1] min{2(rad(G) - i), [eta](G) - 1}. It suffices to show that for every vertex x of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then the assertion holds by inductive hypothesis. If x [not member of] V([H.sub.i-1]). Let P be a directed optimal ([H.sub.i], e)-ear containing x, where e is some leg of [H.sub.i-1] (such a leg and such an ear exists by the definition of [H.sub.i]. By Lemma 3, l(P) [greater than or equal to] min{2(rad(G) - i) + 1, [eta](G)}. Thus, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Therefore, rad([H.sub.i]) [greater than or equal to] [[summation].sup.i.sub.j=1] min{2(rad(G) - j), [eta](G) - 1}.

Remark 1 The above theorem is optimal since it implies Chvatal and Thomassen's optimal Theorem 1. Readers can see [5, 11] for optimal examples.

The following example shows that our result is better than that of Theorem 1.

Example 1 Let [F.sub.3] be a triangle with one of its vertices designated as a root. In order to construct [F.sub.r], take two copies of [F.sub.r-1]. Let [H.sub.r] be the graph obtained from the triangle [u.sub.0], [u.sub.1], [u.sub.2] by identifying the root of first (resp. second) copy of [F.sub.r-1] with [u.sub.1](resp. [u.sub.2]), and [u.sub.0] be the root of [F.sub.r]. Let [G.sub.r] be the graph obtained by taking two copies of [F.sub.r] and identifying their roots. See Figure 2 for details. It is easy to check that [G.sub.r] has radius r and every edge belongs to a cycle of length [eta](G) = 3. By Theorem 1, [G.sub.r] has an orientation [H.sub.r] such that rad([H.sub.r]) [greater than or equal to] [r.sup.2] + r and diam([H.sub.r]) [greater than or equal to] 2[r.sup.2] + 2r. But, by Theorem 2, [G.sub.r] has an orientation [H.sub.r] such that rad(G) [greater than or equal to] 2r and diam(G) [greater than or equal to] 4r. On the other hand, it is easy to check that all the strong orientations of [G.sub.r] has radius 2r and diameter 4r.

We have the following result for plane graphs.

Theorem 5 Let G be a plane graph. If the length of the boundary of every face is at most k, then G has an oriented H such that rad(H) [greater than or equal to] rad(G)(k - 1) and diam(H) [greater than or equal to] 2rad(G)(k - 1).

Since every edge of a maximal plane (resp. outerplane) graph belongs to a cycle with length 3, the following corollary holds.

Corollary 1 Let G be a maximal plane (resp. outerplane) graph. Then there exists an orientation H of G such that rad(H) [greater than or equal to] 2rad(G) and rad(H) [greater than or equal to] 4rad(G).

A graph G is edge-transitive if for any [e.sub.1], [e.sub.2] [member of] E(G), there exists an automorphism g such that g([e.sub.1]) = [e.sub.2]. We have the following result for edge-transitive graphs.

Theorem 6 Let G be a bridgeless edge-transitive graph. Then G has an orientation H such that rad(H) [greater than or equal to] rad(G)(g(G) - 1) and diam(H) [greater than or equal to] 2rad(G)(g(G) - 1), where g(G) is the girth of G, that is, the length of a smallest induced cycle.

For general bipartite graphs, the following theorem holds.

Theorem7 Let G = ([V.sub.1] [union] [V.sub.2], E) be a bipartite graph with [absolute value of [V.sub.1]] = n and [absolute value of [V.sub.2]] = m. If d(x) [less than or equal to] k > [m/2] for any x [member of] [V.sub.1], d(y) [less than or equal to] r > [n/2] for any y [member of] [V.sub.2], then there exists an orientation H of G such that rad(H) [greater than or equal to] 9.

Proof: It suffices to show that rad(G) [greater than or equal to] 3 and [eta](G) [greater than or equal to] 4 by Theorem 2.

First, we show that rad(G) [greater than or equal to] 3. Fix a vertex x in G, and let y be any vertex different from x in G. If x and y belong to the same part, without loss of generality, say x, y [member of] [V.sub.1]. Let X and Y be neighborhoods of x and y in [V.sub.2], respectively. If X [intersection] Y = [empty set], then [absolute value of [V.sub.2]] [less than or equal to] [absolute value of X] + [absolute value of Y] [less than or equal to] 2k > m, a contradiction. Thus X [intersection] Y [not equal to] [empty set], that is, there exists a path between x and y of length two. If x and y belong to different parts, without loss of generality, say x [member of] [V.sub.1], y [member of] [V.sub.2]. Suppose x and y are nonadjacent, otherwise there is nothing to prove. Let X and Y be the neighborhoods of x and y in G, and let X ' be the set of neighbors of X except for x in G. If X' [intersection] Y = [empty set], then [absolute value of [V.sub.1]] [less than or equal to] 1 + [absolute value of Y] + [absolute value of X'] [less than or equal to] 1 + r + (r - 1) = 2r > n, a contradiction (Note that [absolute value of X'] > r - 1). Thus X' [intersection] Y [not equal to] 0, that is, there exists a path between x and y of length three in G.

Next we show that [eta](G) [greater than or equal to] 4. Let xy be any edge in G. Let X be the set of neighbors of x except for y in G, let Y be the set of neighbors of y except for x in G, let X' be the set of neighbors of X except for x in G. If X' [intersection] Y = [empty set], then [absolute value of [V.sub.1]] [less than or equal to] 1 + [absolute value of Y] + [absolute value of X'] [less than or equal to] 1 + (r - 1) + (r - 1) = 2r - 1 > n, a contradiction (Note that [absolute value of X'] [less than or equal to] r - 1). Thus X' [intersection] Y [not equal to] [empty set], that is, there exists a cycle containing xy of length four in G.

Remark 2 The degree condition is optimal. Let m, n be two even numbers with n, m [less than or equal to] 2. Since [K.sub.n/2,m/2] [uniob] [K.sub.n/2m/2] is disconnected, the oriented radius (resp. diameter) of [K.sub.n/2,m/2] [union] [K.sub.n/2,m/2] is [infinity].

For equal bipartition k-regular graph, the following corollary holds.

Corollary 2 Let G = ([V.sub.1] [union] [V.sub.2], E) be a k-regular bipartite graph with [absolute value of [V.sub.1]] = [absolute value of [V.sub.2]] = n. If k > n/2, then there exists an orientation H of G such that rad(H) [greater than or equal to] 9.

The following theorem holds for general graphs.

Theorem 8 Let G be a graph of order n.

(i) If there exists an integer k [less than or equal to] 2 such that [absolute value of [N.sub.k](u)] > n/2 - 1 for every vertex u in G, then G has an orientation H such that rad(H) [greater than or equal to] 4[k.sup.2] and diam(H) [greater than or equal to] 8[k.sup.2].

(ii) If [delta](G) > n/2, then G has an orientation H such that rad(H) [greater than or equal to] 4 and diam(H) [greater than or equal to] 8.

Proof: Since methods of the proofs of (i) and (ii) are similar, we only prove (i). For (i), it suffices to show that rad(G) [greater than or equal to] 2k and [eta](G) < 2k +1 by Theorem 2.

We first show rad(G) [greater than or equal to] 2k. Fix u in G, for every v [member of] V(G), if v [member of] [N.sub.k][u], then d(u, v) [greater than or equal to] k. Suppose v [not member of] [N.sub.k][u], we have [N.sub.k](u) [intersection] [N.sub.k](v) [not equal to] [empty set]. If not, that is, [N.sub.k](u) [intersection] N (v) = [empty set], then [absolute value of [N.sub.k](u)] + [absolute value of [N.sub.k] (v)] + 2 > n (a contradiction). Thus d(u, v) [greater than or equal to] 2k.

Next we show [eta](G) [greater than or equal to] 2k + 1. Let e = uv be any edge in G. If [N.sub.k](u) [intersection] [N.sub.k](v) = [empty set], then [absolute value of V(G)] [less than or equal to] [absolute value of [N.sub.k](u)] + [absolute value of [N.sub.k](v)] + 2 > n, a contradiction. Thus [N.sub.k](u) [intersection] [N.sub.k](v) = [empty set]. Pick w [member of] [N.sub.k](u) [intersection] [N.sub.k](v),and let P (resp. Q) be a path between u and w (resp. between v and w). Then e belongs a close trial uPwQvu of length 2k + 1. Therefore, e belongs a cycle of length at most 2k + 1.

Remark 3 The above condition is almost optimal since [K.sub.n/2] [union] [K.sub.n/2] is disconnected for even n.

Corollary 3 Let G be a graph with minimum degree [delta](G) and girth g(G). If there exists an integer k such that k [greater than or equal to] g(G)/2 and [delta](G)[([delta](G) - 1).sup.k-1] > n/2 - 1, then G has an orientation H such that rad(H) [greater than or equal to] 4[k.sup.2].

Proof: Let k be an integer such that k [greater than or equal to] g(G)/2 and [delta](G)[([delta](G) - 1).sup.k-1] > n/2 - 1. For any vertex u of G, let 1 [greater than or equal to] i < k be any integer and x, y [member of] [N.sub.i](u). If x and y have a common neighbor z in [N.sub.i+1](u), then G has a cycle of length at most 2i < 2k [greater than or equal to] g(G)/2, a contradiction. Thus x and y has no common neighbor in [N.sub.i+1](u). Therefore, [absolute value of [N.sub.k](u)] [less than or equal to] [delta](G)([delta](G) - > n/2 - 1. By Theorem 2, G has an orientation H such that rad(H) [greater than or equal to] 4[k.sup.2].

4 Upper bound for rainbow connection number

At first, we have the following observation.

Observation 2 Let G be a graph and H be a spanning subgraph of G. Then rc(G) [greater than or equal to] rc(H).

Proof of Theorem 4: Let u be a center of G and let [H.sub.0] be the trivial graph with vertex set {u}. We assert that there exists a subgraph [H.sub.i] of G such that [N.sub.i][u] [subset or equal to] V([H.sub.i]) and rc([H.sub.i]) < [[summation].sup.i.sub.j=1] min{2(rad(G) - j) + 1,[eta](G)}.

Basic step: When i = 1, we omit the proof since the proof of this step is similar to that of the following induction step.

Induction step: Assume that the above assertion holds for i - 1 and c is a rc([H.sub.i-1])-rainbow coloring of [H.sub.i-1]. Next we show that the above assertion holds for i. For any v [member of] [N.sub.i](u), either v [member of] V([H.sub.i-1]) or v [member of] [N.sub.G](V([H.sub.i-1]) since [N.sub.i-1][u] [subset or equal to] V([H.sub.i-1]). If [N.sub.i](u) [subset or equal to] V([H.sub.i-1]), then let [H.sub.i] = [H.sub.i-1] and we are done. Thus, we suppose [N.sub.i](u) [subset or equal to] V([H.sub.i-1]) in the following.

Let [C.sub.1] = {[[alpha].sub.1], [[alpha].sub.2], ...} and [C.sub.2] = {[[beta].sub.1], [[beta].sub.2], ...} be two pools of colors, none of which are used to color [H.sub.i-1], and there exists no common color in [C.sub.1] and [C.sub.2]. An edge-coloring of an H-ear P = ([u.sub.0], [u.sub.1], ..., [u.sub.k]) is a symmetrical coloring if its edges are colored by [[alpha].sub.1], [[alpha].sub.2], ..., [[alpha].sub.[k/2]], [[beta].sub.[k/2]], ..., [[beta].sub.2], [[beta].sub.1] in that order or [[beta].sub.1], [[beta].sub.2], ..., [[beta].sub.[k/2]], ..., [[alpha].sub.2], [[alpha].sub.1] in that order.

Let X = [N.sub.i](u)\V([H.sub.i-1]) and m = min{2(rad(G) - i) + 1,[eta](G)}. Pick [x.sub.1] [member of] X, Let [y.sub.1] be a neighbor of [x.sub.1] in [H.sub.i-1] and [P.sub.1] be an optimal ([H.sub.i-1], [x.sub.1][y.sub.1])-ear. We can color P symmetrically with colors [[alpha].sub.1], [[alpha].sub.2], ..., [[alpha].sub.[l(P)/2]], [[beta].sub.[l(P)/2]], ..., [[beta].sub.2], [[beta].sub.1]. Pick [x.sub.2] [member of] X satisfying that all the incident edges of [x.sub.2] are not colored. Let [y.sub.2] be a neighbor of [x.sub.2] in [H.sub.i-1]. If there exists an optimal ([H.sub.i-]1, [x.sub.2][y.sub.2])-ear [P.sub.2] such that [P.sub.1] and [P.sub.2] are independent, then we can color [P.sub.2] symmetrically with colors [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], Otherwise, by Lemma 1, there exists an optimal ([H.sub.i-1], [x.sub.2][y.sub.2])-ear [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that [P.sub.1] and [P.sub.2] have only one continuous common segment containing [z.sub.2], where [z.sub.2] is the other foot of [P.sub.2]. Thus we can color P2 symmetrically with colors [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by preserving the coloring of [P.sub.1]. We can pick the vertices of X and color optimal [H.sub.i]-ears until that for any x [member of] X, at least two incident edges of x are colored. Since for any leg e of [H.sub.i-1], l(e) [greater than or equal to] m by Lemma 3, we use at most m coloring in the above coloring process.

Let [H.sub.i] be the graph obtained from [H.sub.i-1] by adding all the vertices in V(G)\V([H.sub.i-1]), which have at least two new colored incident edges, and adding the new colored edges. Clearly, [N.sub.i][u] [subset or equal to] V([H.sub.i]). It is suffices to show that [H.sub.i] is rainbow connected. Let x and y be two distinct vertices in [H.sub.i]. If x, y [member of] V([H.sub.i-1]), then there exists a rainbow path between x and y by inductive hypothesis. If exactly one of x and y belongs to V([H.sub.i-1]), say x. Let P be a symmetrical colored [H.sub.i-1]-ear containing y, and y' be a foot of P. There exists a rainbow path Q between x and y' in [H.sub.i-1] by inductive hypothesis. Thus, xQy'Py is a rainbow path between x and y in [H.sub.i].

Suppose none of x and y belongs to [H.sub.i-1]. Let P and Q be symmetrical colored [H.sub.i-1]-ear containing x and y, respectively. Furthermore, let x', x" be the feet of P and y', y" be the feet of Q. Without loss of generality, assume that P is colored from x' to x" by [[alpha].sub.1], [[alpha].sub.2], ..., [[alpha].sub.[l(P)/2]], [[beta].sub.[l(P)/2]], ..., [[beta].sub.2], [[beta].sub.1] in that order, and Q is colored from y' to y" by [[alpha].sub.1], [[alpha].sub.2], ..., [[alpha].sub.[l(Q)/2]], [[beta].sub.[l(P)/2]], ..., [[beta].sub.1], [[beta].sub.1] in that order. If l(x'Px) [greater than or equal to] l(y'Qy), let R be a rainbow path between x' and y" in [H.sub.i-1]. Then x P x' R y" Q y is a rainbow path between x and y in [H.sub.i]. Otherwise, l(x'Px) > l(y'Qy). Let R be a rainbow path between y' and x" in [H.sub.i-1]. Then y Q y' R x" P x is a rainbow path between x and y in [H.sub.i]. Thus, there exists a rainbow path between any two distinct vertices in [H.sub.i], that is, [H.sub.i] is ([[summation].sup.i.sub.j=1] min{2(rad(G) - j) + 1, [eta](G)})-rainbow connected. ? Readers can see [1] for an optimal example. The following example shows that our result is better than that of Theorem 3.

Example 2 Let r [less than or equal to] 3, k [less than or equal to] 2r be two integers, and [W.sub.k] = [C.sub.k] [disjunction] [K.sub.1] be an wheel, where V([C.sub.k]) = {[u.sub.1], [u.sub.2], ..., [u.sub.k]} and V([K.sub.1]) = {u}. Let H be the graph obtained from [W.sub.k] by inserting r - 1 vertices between every edge [uu.sub.i], 1 [greater than or equal to] i [greater than or equal to] k. For every edge e = xy of H, add a new vertex ve and new edges [v.sub.e]x, [v.sub.e]y. Denote by G the resulting graph. It is easy to check that rad(G) = r, diam(G) = 2r, [eta](G) = 3 and [zeta](G) = 2r - 1. By Theorem 3, we have rc(G) [greater than or equal to] [[summation].sup.r.sub.i=1] min{2i + 1, [zeta](G)} [greater than or equal to] [r.sup.2] + 2r - 2. But, by Theorem 4 we have rc(G) [greater than or equal to] 3r. On the other hand, rc(G) [less than or equal to] 2r since diam(G) = 2r.

The remaining results are similar to those in Section 3.

Theorem 9 Let G be a plane graph. If the length of the boundary of every face is at most k, then rc(G) [greater than or equal to] krad(G).

Corollary 4 Let G be a maximal plane (resp. outerplane) graph. Then rc(G) [greater than or equal to] 3rad(G).

Theorem 10 Let G be a bridgeless edge-transitive graph. Then rc(G) [greater than or equal to] rad(G)g(G), where g(G) is the girth of G.

Theorem 11 Let G = ([V.sub.1] [union] [V.sub.2], E) be a bipartite graph with [absolute value of [V.sub.1]] = n and [absolute value of [V.sub.2]] = m. If d(x) [less than or equal to] k > [m/2] for any x [member of] [V.sub.1], d(y) [less than or equal to] r > [n/2] for any y [member of] [V.sub.2], then rc(G) [greater than or equal to] 12.

Remark 4 The degree condition is optimal. Let m, n be two even numbers with n, m [less than or equal to] 2. Since [K.sub.n/2,m/2] [union] [K.sub.n/2,m/2] is disconnected, rc([K.sub.n/2,m/2] [union] [K.sub.n/2,m/2]) = [infinity].

Corollary 5 Let G = ([V.sub.1] [union] [V.sub.2], E) be a k-regular bipartite graph with [absolute value of [V.sub.1]] = [absolute value of [V.sub.2]] = n. If k > [n/2], then rc(G) [greater than or equal to] 12.

The following theorem holds for general graphs.

Theorem 12 Let G be a graph.

(i) If there exists an integer k [less than or equal to] 2 such that [absolute value of [N.sub.k](u)] > n/2 - 1 for every vertex u in G, then rc(G) [greater than or equal to] 4[k.sup.2] + 2k.

(ii) If [delta](G) > n/2, then rc(G) [greater than or equal to] 6.

Remark 5 The above condition is almost optimal since [K.sub.n/2] [union] [K.sub.n/2] is disconnected for even n.

Corollary 6 Let G be a graph with minimum degree [delta](G) and girth g(G). If there exists an integer k such that k < g(G)/2 and [delta](G)[([delta](G) - 1).sup.k-1] > n/2 - 1, then then rc(G) [greater than or equal to] 4[k.sup.2] + 2k.

Acknowledgments

The authors are very grateful to the referees for their helpful comments and suggestions.

References

[1] M. Basavaraju, L.S. Chandran, D. Rajendraprasad, A. Ramaswamy, Rainbow connection number and radius, Graphs & Combin. 30(2014), 275-285.

[2] J.A. Bondy, U.S.R. Murty, Graph Theory, GTM 244, Springer, 2008.

[3] S. Chakraborty, E. Fischer, A. Matsliah, R. Yuster, Hardness and algorithms for rainbow connectivity, J. Combin. Optim. 21(2011), 330-347.

[4] G. Chartrand, G.L. Johns, K.A. McKeon, P. Zhang, Rainbow connection in graphs, Math. Bohem. 133(2008), 85-98.

[5] V. Chvatal, C. Thomassen, Distances in orientations of graphs, J. Combin. Theory, Ser.B, 24(1978), 61-75.

[6] F.V. Fomin, M. Matamala, E. Prisner, I. Rapaport, AT-free graphs: Linear bounds for the oriented diameter, Discrete Appl. Math. 141(2004), 135-148.

[7] K.M. Koh, B.P. Tan, The minimum diameter of orientations of complete multipartite graphs, Graphs & Combin. 12(1996), 333-339.

[8] K.M. Koh, E.G. Tay, Optimal orientations of products of paths and cycles, Discrete Appl. Math. 78(1997), 163-174.

[9] J.C. Konig, D.W. Krumme, E. Lazard, Diameter-preserving orientations of the torus, Networks 32(1998), 1-11.

[10] M. Krivelevich, R. Yuster, The rainbow connection of a graph is (at most) reciprocal to its minimum degree, J. Graph Theory 63(2010), 185-91.

[11] P.K. Kwok, Q. Liu, D.B. West, Oriented diameter of graphs with diameter 3, J. Combin. Theory, Ser. B, 100(2010), 265-274.

[12] H. Li, X. Li, S. Liu, The (strong) rainbow connection numbers of Cayley graphs on Abelian groups, Comput. Math. Appl. 62(11)(2011), 4082-4088.

[13] X. Li, Y. Sun, Upper bounds for the rainbow connection number of line graphs, Graphs & Combin. (28) 2012, 251-263.

[14] J.E. Mccanna, Orientations of the n-cube with minimum diameter, Discrete Math. 68(1988), 309-310.

[15] J. Plesnlk, Remarks on diameters of orientations of graphs, Acta Math. Univ. Comenian. 46/47(1985), 225-236.

[16] H. Robbins, A theorem on graphs with an application to a problem of traffic control, Amer. Math. Monthly 46(1939), 281-283.

[17] I. Schiermeyer, Rainbow connection in graphs with minimum degree three, In J. Fiala, J. Kratochvl, M. Miller, editors, Combinatorial Algorithms, Lecture Notes in Computer Science Vol.5874 (2009), 432-437. Springer Berlin/Heidelberg.

[18] L. Soltes, Orientations of graphs minimizing the radius or the diameter, Math. Slovaca 36(1986), 289-296.

Xiaolong Huang

Hengzhe Li ([dagger])

Xueliang Li

Yuefang Sun

Center for Combinatorics and LPMC-TJKLC, Nankai University, Tianjin, China

received 23rd Dec. 2012, accepted 28th May 2014.

* Supported by NSFC No. 11071130, and "the Fundamental Research Funds for the Central Universities".

([dagger]) Email: lhz2010@mail.nankai.edu.cn,lhz@htu.cn

Printer friendly Cite/link Email Feedback | |

Author: | Huang, Xiaolong; Li, Hengzhe; Li, Xueliang; Sun, Yuefang |
---|---|

Publication: | Discrete Mathematics and Theoretical Computer Science |

Article Type: | Report |

Date: | Nov 1, 2014 |

Words: | 7047 |

Previous Article: | A four-sweep LBFS recognition algorithm for interval graphs. |

Next Article: | Complexity of conditional colouring with given template. |

Topics: |