Printer Friendly

Oriented diameter and rainbow connection number of a graph.

1 Introduction

All 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
COPYRIGHT 2014 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2014 Gale, Cengage Learning. All rights reserved.

Article Details
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:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters