- Email: [email protected]

)

–

Contents lists available at ScienceDirect

Discrete Applied Mathematics journal homepage: www.elsevier.com/locate/dam

Adjacent vertex distinguishing edge-colorings and total-colorings of the lexicographic product of graphs✩ Shuangliang Tian ∗ , Qian Wang College of Mathematics and Computer Science, Northwest University for Nationalities, Lanzhou 730030, PR China

article

info

Article history: Received 25 April 2009 Received in revised form 11 November 2014 Accepted 24 November 2014 Available online xxxx Keywords: Edge-coloring Total-coloring Adjacent vertex distinguishing edge-coloring Adjacent vertex distinguishing total-coloring Lexicographic product

abstract Let G be a simple graph with vertex set V (G) and edge set E (G). An edge-coloring f of G is called an adjacent vertex distinguishing edge-coloring of G if Cf (u) ̸= Cf (v) for any uv ∈ E (G), where Cf (u) denotes the set of colors of edges incident with u. A total-coloring g of G is called an adjacent vertex distinguishing total-coloring of G if Sg (u) ̸= Sg (v) for any uv ∈ E (G), where Sg (u) denotes the set of colors of edges incident with u together with the color assigned to u. The minimum number of colors required for an adjacent vertex distinguishing edge-coloring (resp. an adjacent vertex distinguishing total-coloring) of G is denoted by χa′ (G) (resp. χat (G)). The lexicographic product of simple graphs G and H is simple graph G[H ] with vertex set V (G) × V (H ), in which (u, v) is adjacent to (u′ , v ′ ) if and only if either uu′ ∈ E (G) or u = u′ and vv ′ ∈ E (H ). In this paper, we consider these parameters for the lexicographic product G[H ] of two graphs G and H. We give the exact values of χa′ (G[H ]) if (1) G is a complete graph of order n ≥ 3 and H is a graph of order 2m ≥ 4 with χa′ (H ) = ∆(H ); (2) G is a tree of order n ≥ 3 and H is a graph of order m ≥ 3 with χa′ (H ) = ∆(H ). We also obtain the exact values of χat (G[H ]) if (1) G is a complete graph of order n ≥ 2 and H is an empty graph of order m ≥ 2, where nm is even; (2) G is a complete graph of order n ≥ 2 and H is a bipartite graph of order m ≥ 4 with bipartition (X , Y ), where |X | and |Y | are even; (3) G is a cycle of order n ≥ 3 and H is an empty graph of order m ≥ 2, where nm is even; (4) G is a tree of order n ≥ 3 and H is an empty graph of order m ≥ 2. © 2014 Elsevier B.V. All rights reserved.

1. Introduction In this paper we consider only undirected and simple graphs. We use V (G) and E (G) to denote the vertex set and the edge set of a graph G, respectively. And Kn denotes a complete graph of order n, K n denotes an empty graph of order n (or the complement of Kn ), Cn denotes a cycle of order n, Pn denotes a path of order n, Kn,n denotes an n-regular complete bipartite graph. Let C be a finite set of colors. An edge-coloring of a graph G is a function f : E (G) → C such that no adjacent edges of G receive the same color. For every vertex v , let Cf (v) denote the set of colors of edges incident with v , and let C f (v) = C \Cf (v). The minimum number of colors required for an edge-coloring of G is denoted by χ ′ (G). A graph G is said to be Class 1 if χ ′ (G) = ∆(G) and Class 2 if χ ′ (G) = ∆(G) + 1 where ∆(G) denotes the maximum degree of G. An edge-coloring f of a graph G is said to be adjacent vertex distinguishing if Cf (u) ̸= Cf (v) for any uv ∈ E (G). Adjacent vertex distinguishing

✩ This work is supported by State Ethnic Affairs Commission of China (10XB01) and Innovative Team Subsidize of Northwest University for Nationalities.

∗

Corresponding author. E-mail address: [email protected] (S. Tian).

http://dx.doi.org/10.1016/j.dam.2014.11.028 0166-218X/© 2014 Elsevier B.V. All rights reserved.

2

S. Tian, Q. Wang / Discrete Applied Mathematics (

)

–

edge-coloring is abbreviated to avde-coloring. The minimum number of colors required for an avde-coloring of G is denoted by χa′ (G). This type of coloring has been studied in many papers (see for example [1,2,5,6,13]), where different names such as adjacent strong edge coloring [13] and 1-strong edge coloring [1] are used to refer to an avde-coloring. A total-coloring of a graph G is a function g : V (G) ∪ E (G) → C such that no two adjacent vertices or edges of G have the same color, and the color of each vertex of G is distinct from the colors of its incident edges. For every vertex v ∈ V (G), let Sg (v) denote the set of colors of edges incident with v together with the color assigned to v , and let S f (v) = C \ Sf (v). A total-coloring g of a graph G is said to be adjacent vertex distinguishing if Sg (u) ̸= Sg (v) for any uv ∈ E (G). Adjacent vertex distinguishing total-coloring is abbreviated to avdt-coloring. The minimum number of colors required for an avdtcoloring of G is denoted by χat (G). Zhang et al. [12] determined the value of χat (G) for many basic families of graphs, including cycles, complete graphs, complete bipartite graphs, and trees. Some other results about adjacent vertex distinguishing totalcoloring can be found in [4,7,10]. In [13,12], the following two conjectures related to avde-coloring and avdt-coloring were made, respectively. Conjecture 1.1. Let G ̸= C5 be a connected graph of order at least three. Then

χa′ (G) ≤ ∆(G) + 2. Conjecture 1.2. If G is a connected graph of order at least two, then

χat (G) ≤ ∆(G) + 3. Notice that χa′ (G) is greater than or equal to ∆(G) and if G has two adjacent vertices of maximum degree, then χa′ (G) ≥ ∆(G) + 1. Analogously, χat (G) is greater than or equal to ∆(G) + 1 and if G has two adjacent vertices of maximum degree, then χat (G) ≥ ∆(G) + 2. Two graphs G and H are said to be isomorphic (written G ∼ = H) if there are bijections θ : V (G) → V (H ) and φ : E (G) → E (H ) such that ψG (e) = uv if and only if ψH (φ(e)) = θ (u)θ (v), where ψG and ψH are the incidence functions of G and H respectively. The lexicographic product (or composition) of two graphs G and H is the graph G[H ] with vertex set V (G) × V (H ), in which (u, v) is adjacent to (u′ , v ′ ) if and only if either uu′ ∈ E (G), or u = u′ and vv ′ ∈ E (H ) (see [3]). We denote by wij the element (ui , vj ) of V (G) × V (H ). Let Vi = {wij |vj ∈ V (H )}, for every ui ∈ V (G); these sets are called the partite sets of G[H ]. By the definition of the lexicographic product of two graphs, a balanced complete n-partite graph K (n, m) in which each partite set has m vertices, is the lexicographic product Kn [K m ] of a complete graph Kn of order n and the complement of Km . Some of the following basic results will be used very often in this paper. Lemma 1.1 (Yap [11]). For any integer n ≥ 3, there exists an n-edge-coloring of Kn,n , such that Kn,n has a perfect matching receiving n distinct colors. Using the proof of Theorem 3.10 in [11], we can obtain the following lemma. Lemma 1.2. Let V1 , . . . , Vn be the partite sets of G = Kn [K 2m ], where n ≥ 2 and Vi = {wij |j = 1, . . . , 2m}, i = 1, . . . , n. And let Gj = G[{w1,2j−1 , w1,2j , w2,2j−1 , w2,2j , . . . , wn,2j−1 , wn,2j }],

j = 1, . . . , m.

Then the subgraph G − E (G1 ∪ · · · ∪ Gm ) of G has an edge-coloring using (n − 1)(2m − 2) colors. Lemma 1.3 (Zhang et al. [13]). Let T be a tree of order at least three. If T has two adjacent vertices of maximum degree, then χa′ (T ) = ∆(T ) + 1; otherwise, χa′ (T ) = ∆(T ). Lemma 1.4 (Zhang et al. [12]). For any integer n ≥ 2, we have

χat (Kn ) =

n+2 n+1

if n is odd; if n is even.

Lemma 1.5. For every bipartite graph G, we have χat (G) ≤ ∆(G) + 2. If G has two adjacent vertices of maximum degree, then χat (G) = ∆(G) + 2. Proof. Let (X , Y ) be a bipartition of G. To prove that χat (G) ≤ ∆(G) + 2, we first color the vertices of X using color 1 and the vertices of Y using color 2, next we color the edges of G using ∆(G) new colors. If G has two adjacent vertices of maximum degree, then χat (G) ≥ ∆(G) + 2. Thus χat (G) = ∆(G) + 2. Lemma 1.6 (Zhang et al. [12]). Let T be a tree of order at least two. If T has two adjacent vertices of maximum degree, then χat (T ) = ∆(T ) + 2; otherwise, χat (T ) = ∆(T ) + 1.

S. Tian, Q. Wang / Discrete Applied Mathematics (

)

–

3

Lemma 1.7 (Zhang et al. [12]). For every integer n ≥ 4 we have χat (Cn ) = 4. In this paper, we obtain upper bounds of two parameters χa′ (G[H ]) and χat (G[H ]). Furthermore, we determine the exact values of the parameters for some lexicographic product of graphs. 2. Adjacent vertex distinguishing edge-coloring According to the structure of lexicographic product of two graphs, we give the following upper bound of χa′ (G[H ]). Theorem 2.1. Let G and H be two graphs, where |V (G)| = n ≥ 3, |V (H )| = m ≥ 3. Then

χa′ (G[H ]) ≤ min{(m − 1)χ ′ (G) + χa′ (G) + χa′ (H ), χa′ (G[K m ]) + χa′ (H )}. Proof. We need to prove that G[H ] has two avde-colorings using (m − 1)χ ′ (G)+χa′ (G)+χa′ (H ) colors and χa′ (G[K m ])+χa′ (H ) colors, respectively. Let V1 , . . . , Vn be the partite sets of G′ = G[H ], where Vi = {wij |j = 1, . . . , m}, i = 1, . . . , n. Then Gj = G′ [{w1j , w2j , . . . , wnj }] ∼ = G, j = 1, . . . , m. We now give the following avde-coloring of G′ using (m − 1)χ ′ (G) + χa′ (G) + χa′ (H ) colors. Firstly, the graph G′ − E (G1 ∪ · · · ∪ Gm ) is edge-colored with colors 1, . . . , (m − 1)χ ′ (G). Secondly, the graph G1 ∪ · · · ∪ Gm is edge-colored with colors (m − 1)χ ′ (G) + 1, . . . , (m − 1)χ ′ (G) + χa′ (G) such that this coloring is adjacent vertex distinguishing and vertices in the same partite set Vi meet the same set of colors. Finally, the copies of H are edge-colored with colors (m − 1)χ ′ (G) + χa′ (G) + 1, . . . , (m − 1)χ ′ (G) + χa′ (G) + χa′ (H ) such that this coloring is adjacent vertex distinguishing.

We next give the following avde-coloring of G′ using χa′ (G[K m ]) + χa′ (H ) colors. Firstly, G[K m ] is edge-colored with colors 1, . . . , χa′ (G[K m ]) such that this coloring is adjacent vertex distinguishing. After that, the copies of H are edge-colored with colors χa′ (G[K m ]) + 1, . . . , χa′ (G[K m ]) + χa′ (H ) such that this coloring is adjacent vertex distinguishing. Since χa′ (Wn−1 ) = χa′ (Fn−1 ) = χa′ (Sn−1 ) = n − 1 for any n ≥ 5, by Theorem 2.1,

χa′ (Wn−1 [K m ]) = χa′ (Fn−1 [K m ]) = χa′ (Sn−1 [K m ]) = (n − 1)m, where Wn−1 , Fn−1 and Sn−1 denote a wheel, fan and star of order n ≥ 5, respectively. To determine the values of χa′ (Kn [K 2m ]), we first give the following lemma, this lemma is proved in [9]. Here we give a simpler proof of these results. Lemma 2.1. For any integer n ≥ 3 we have χa′ (Kn [K 2 ]) = 2n − 1. (j)

Proof. Let V1 , . . . , Vn be the partite sets of G = Kn [K 2 ], where Vi = {wi1 , wi2 }, i = 1, . . . , n. Let Kn be a complete graph (1) (2) with vertex set V (j) = {wij |i = 1, . . . , n}, where j = 1, 2. Then G = Kn ∪ Kn + F , where F = {wi1 wk2 |i ̸= k, i, k = ′ 1, . . . , n}. Clearly χa (G) ≥ ∆(G) + 1 ≥ 2n − 1. We need only to prove that G has an avde-coloring using 2n − 1 colors. We now consider two cases separately. Case 1. n is odd. Since χ ′ (Kn+1 ) = n, for any edge-coloring of Kn+1 using n colors, we can obtain an avde-coloring of Kn by (1) (2) deleting one vertex in Kn+1 . Thus Kn ∪ Kn can be edge-colored with colors 1, . . . , n, such that this coloring is adjacent vertex distinguishing and vertices in the same partite set Vi meet the same set of colors. Since the induced subgraph G[F ] of G is a bipartite graph with maximum degree n − 1, G[F ] can be edge-colored with colors n + 1, . . . , 2n − 1. Hence G can be edge-colored with 2n − 1 colors, and this coloring of G is denoted by f . Clearly, C f (wij ) = {i}, where i = 1, . . . , n, j = 1, 2. This implies that f is an avde-coloring of G using 2n − 1 colors. Case 2. n is even. Let F ′ = {wi1 wk2 |i, k = 1, . . . , n} and H = G[F ′ ]. Then H is an n-regular complete bipartite graph. By Lemma 1.1, there exists an n-edge-coloring of H, such that H has a perfect matching receiving n distinct colors. Without loss of generality, we may assume that {wi1 wi2 |i = 1, . . . , n} is a perfect matching of H colored with colors 1, . . . , n respectively. For the colored H, we can obtain an avde-coloring of G[F ] by deleting the perfect matching {wi1 wi2 |i = 1, . . . , n}. Since n is (1) (2) even, Kn ∪ Kn can be edge-colored with colors n + 1, . . . , 2n − 1. Hence G can be edge-colored with 2n − 1 colors, and this coloring of G is denoted by f . Clearly, C f (wij ) = {i}, where i = 1, . . . , n, j = 1, 2. This implies that f is an avde-coloring of G using 2n − 1 colors. We now determine the exact values of χa′ (Kn [K 2m ]) by Lemmas 1.2 and 2.1. Lemma 2.2. For any integers n ≥ 3 and m ≥ 2, we have χa′ (Kn [K 2m ]) = 2m(n − 1) + 1.

4

S. Tian, Q. Wang / Discrete Applied Mathematics (

)

–

Proof. Let G = Kn [K 2m ] and r = 2m. Clearly, χa′ (G) ≥ r (n − 1) + 1. We need only to prove that G has an avde-coloring using r (n − 1) + 1 colors. Let V1 , . . . , Vn be the partite sets of G, where Vi = {wij |j = 1, . . . , r }, i = 1, . . . , n. Then Gj = G[{w1,2j−1 , w1,2j , w2,2j−1 , w2,2j , . . . , wn,2j−1 , wn,2j }] ∼ = Kn [K 2 ],

j = 1, . . . , m.

By Lemma 2.1, the graph G1 ∪· · ·∪ Gm can be edge-colored with colors 1, . . . , 2n − 1 such that this coloring is adjacent vertex distinguishing and vertices in the same partite set Vi meet the same set of colors. By Lemma 1.2, the graph G − E (G1 ∪· · ·∪ Gm ) can be edge-colored with (n − 1)(r − 2) colors. Therefore, χa′ (G) ≤ 2n − 1 + (n − 1)(r − 2) = r (n − 1) + 1, and consequently, χa′ (G) = r (n − 1) + 1. Applying Lemma 2.2 and Theorem 2.1 to the graph Kn [H ], where H is a graph of even order such that χa′ (H ) = ∆(H ), we determine the following exact values of χa′ (Kn [H ]). Theorem 2.2. Let H be a graph of order 2m ≥ 4 such that χa′ (H ) = ∆(H ). Then for any integer n ≥ 3 we have χa′ (Kn [H ]) = 2m(n − 1) + ∆(H ) + 1. Proof. Clearly, χa′ (Kn [H ]) ≥ 2m(n − 1) + ∆(H ) + 1. By Theorem 2.1 and Lemma 2.2, χa′ (Kn [H ]) ≤ 2m(n − 1) + ∆(H ) + 1. Thus χa′ (Kn [H ]) = 2m(n − 1) + ∆(H ) + 1. We apply Theorem 2.2 to obtain the following conclusions: for any integers n ≥ 3 and m ≥ 2,

χa′ (Kn [W2m−1 ]) = χa′ (Kn [F2m−1 ]) = χa′ (Kn [S2m−1 ]) = 2nm, χa′ (Kn [T ]) = 2m(n − 1) + ∆(T ) + 1, where T is a tree of order 2m in which there are no two adjacent vertices of maximum degree. For the lexicographic product G[H ] of graphs G and H, if G is a tree and H satisfying the condition χa′ (H ) = ∆(H ), then by Lemma 1.3 and Theorem 2.1, we get the following theorem. Theorem 2.3. Let T be a tree of order n ≥ 3 and let H be a graph of order m ≥ 3 such that χa′ (H ) = ∆(H ). If T has two adjacent vertices of maximum degree, then χa′ (T [H ]) = m∆(T ) + ∆(H ) + 1; otherwise, χa′ (T [H ]) = m∆(T ) + ∆(H ). Proof. Since T is Class 1, by Lemma 1.3 and Theorem 2.1, we can easily prove that the result is true.

Theorem 2.4. For any integers n ≥ 2 and m ≥ 2 we have m+2 χa′ (Pn [K m ]) = 2m 2m + 1

if n = 2; if n = 3; if n ≥ 4.

Proof. Suppose that n = 2. We have χa′ (P2 [K m ]) = χa′ (Km,m ) = m + 2 (see [13]). Now assume that n ≥ 3. Since any path is a tree, by Theorem 2.3, the result is true. 3. Adjacent vertex distinguishing total-coloring Using the similar method in the proof of Theorem 2.1, we give an upper bound of χat (G[K m ]). Theorem 3.1. Let G be a graph of order n ≥ 2. For any integer m ≥ 2,

χat (G[K m ]) ≤ (m − 1)χ ′ (G) + χat (G). Proof. Let V1 , . . . , Vn be the partite sets of G′ = G[K m ], where Vi = {wij |j = 1, . . . , m}, i = 1, . . . , n. Then Gj = G′ [{w1j , w2j , . . . , wnj }] ∼ = G, j = 1, . . . , m. To prove that χat (G′ ) ≤ (m − 1)χ ′ (G) + χat (G), we give the following avdt′ coloring of G using (m − 1)χ ′ (G) + χat (G) colors. Firstly, the graph G′ − E (G1 ∪ · · · ∪ Gm ) is edge-colored with colors 1, . . . , (m−1)χ ′ (G). After that, the graph G1 ∪· · ·∪Gm is total-colored with colors (m−1)χ ′ (G)+1, . . . , (m−1)χ ′ (G)+χat (G) such that this coloring is adjacent vertex distinguishing, and vertices in the same partite set Vi receive the same color and meet the same set of colors. Since χat (Wn−1 ) = χat (Fn−1 ) = χat (Sn−1 ) = n for any n ≥ 5, by Theorem 3.1, we immediately obtain the following conclusion: for any integer m ≥ 1,

χat (Wn−1 [K m ]) = χat (Fn−1 [K m ]) = χat (Sn−1 [K m ]) = (n − 1)m + 1. In order to determine the values of χat (Kn [K m ]), where nm is even, we first give the following lemma, this lemma is proved in [8]. Here we give a simpler proof of these results. Lemma 3.1. For any integer n ≥ 2 we have χat (Kn [K 2 ]) = 2n.

S. Tian, Q. Wang / Discrete Applied Mathematics (

)

–

5

(1)

(2)

Proof. Let V1 , . . . , Vn be the partite sets of G = Kn [K 2 ], where Vi = {wi1 , wi2 }, i = 1, . . . , n. Clearly G = Kn ∪ Kn + F (j) (the meaning of symbols Kn and F see the proof of Lemma 2.1). Since χat (G) ≥ 2n, we need only to give an avdt-coloring of G using 2n colors. We consider two cases separately. Case 1. n is odd. Let F ′ = {wi1 wk2 |i, k = 1, . . . , n} and H = G[F ′ ]. By the similar proof of Lemma 2.1, the graph H has an n-edge-coloring such that {wi1 wi2 |i = 1, . . . , n} is a perfect matching of H colored with colors 0, . . . , n − 1 respectively, (1) (2) and we can obtain an avde-coloring of G[F ] by deleting this perfect matching. Since n is odd, Kn ∪ Kn can be total-colored with colors n, . . . , 2n − 1 such that vertices in the same partite set Vi receive the same color. Hence G can be total-colored with 2n colors, and this coloring of G is denoted by g. Clearly, S g (wij ) = {i − 1}, where i = 1, . . . , n, j = 1, 2. This implies that g is an avdt-coloring of G using 2n colors. Case 2. n is even. For each j = 1, 2, we color edges wij wkj (here i ̸= k) using color i + k − 1 and color vertices wij using color (j)

2i − 1 in Kn , where i + k − 1 and 2i − 1 are taken modulo n + 1, i, k = 1, . . . , n. Since G[F ] is an (n − 1)-regular bipartite graph, G[F ] can be edge-colored with colors n + 1, . . . , 2n − 1. Hence G can be total-colored with 2n colors, and this coloring of G is denoted by g. Clearly, S g (wij ) = {i − 1}, where i = 1, . . . , n, j = 1, 2. This implies that g is an avdt-coloring of G using 2n colors. For every graph Kn [K m ] of even order, by Theorem 3.1 and Lemma 3.1, we can get the exact values of χat (Kn [K m ]). Theorem 3.2. For any integers n, m ≥ 2, if nm is even, then χat (Kn [K m ]) = m(n − 1) + 2. Proof. Let G = Kn [K m ]. Clearly, χat (G) ≥ m(n − 1) + 2. We now consider two cases separately. Case 1. n is even. Since Kn is Class 1, by Lemma 1.4 and Theorem 3.1, χat (G) ≤ m(n − 1) + 2, and thus χat (G) = m(n − 1) + 2. Case 2. n is odd. Then m is even. Let V1 , . . . , Vn be the partite sets of G, where Vi = {wij |j = 1, . . . , m}, i = 1, . . . , n. Then Gj = G[{w1,2j−1 , w1,2j , w2,2j−1 , w2,2j , . . . , wn,2j−1 , wn,2j }] ∼ = Kn [K 2 ],

j = 1, . . . , m/2,

and thus, by Lemma 3.1, the graph G1 ∪ · · · ∪ Gm/2 can be total-colored with colors 0, . . . , 2n − 1, such that this coloring is adjacent vertex distinguishing, and vertices in the same partite set Vi receive the same color and meet the same set of colors. By Lemma 1.2, the graph G − E (G1 ∪ · · · ∪ Gm/2 ) can be edge-colored with (n − 1)(m − 2) colors. Therefore, χat (G) ≤ 2n + (n − 1)(m − 2) = m(n − 1) + 2, and consequently, χat (G) = m(n − 1) + 2. For any bipartite graph H with bipartition (X , Y ) such that |X | and |Y | are even, using the similar method of the proof of Theorem 3.2, we can obtain the exact values of χat (Kn [H ]). Theorem 3.3. Let H be a bipartite graph with bipartition (X , Y ), where |X | = 2s and |Y | = 2t. For any integer n ≥ 2 we have

χat (Kn [H ]) = 2(s + t )(n − 1) + ∆(H ) + 2.

Proof. Let p = 2s, q = 2t and G = Kn [H ]. Clearly, χat (G) ≥ (p + q)(n − 1) + ∆(H ) + 2. We need only to show that G has an avdt-coloring using (p + q)(n − 1) + ∆(H ) + 2 colors. Let V1 , . . . , Vn be the partite sets of G and let (Xi , Yi ) be a bipartition of the induced subgraph G[Vi ] of G, where Vi = Xi ∪ Yi , Xi = {xij |j = 1, . . . , p}, Yi = {yij |j = 1, . . . , q}, i = 1, . . . , n. Then Gk = G[{x1,2k−1 , x1,2k , x2,2k−1 , x2,2k , . . . , xn,2k−1 , xn,2k }] ∼ = Kn [K 2 ], G∗l = G[{y1,2l−1 , y1,2l , y2,2l−1 , y2,2l , . . . , yn,2l−1 , yn,2l }] ∼ = Kn [K 2 ],

k = 1, . . . , s, l = 1, . . . , t .

We now give the following total-coloring g of G using (p + q)(n − 1) + ∆(H ) + 2 colors. Firstly, by Lemma 3.1, for k = 1, . . . , s and l = 1, . . . , t, both Gk and G∗l can be total-colored with colors 0, . . . , 2n − 1 such that these colorings are all adjacent vertex distinguishing, and vertices in the same partite set Vi receive the same color and meet the same set of colors. The coloring of each G∗l is denoted by f . Secondly, for each colored G∗l , let Z0 , Z1 , . . . , Z2n−1 be the color classes of f such that all elements of Zj receive color j, where j = 0, . . . , 2n − 1. And we recolor all elements of Zj by color j + n, where j + n is taken modulo 2n and j = 0, . . . , 2n − 1. Thirdly, by Lemma 1.2, the graph G − E (G1 ∪ · · · ∪ Gs ∪ G∗1 ∪ · · · ∪ G∗t ) can be edge-colored with (n − 1)(p + q − 2) colors. Finally, since G[Vi ] ∼ = H and H is a bipartite graph, each G[Vi ] can be edge-colored with ∆(H ) colors. Notice that for i = 1, 2, . . . , n, S g (xij1 ) ∩ {0, . . . , 2n − 1} = {i − 1},

j1 = 1, 2, . . . , p,

S g (yij2 ) ∩ {0, . . . , 2n − 1} = {n + i − 1},

j2 = 1, 2, . . . , q.

It is clear that g is an avdt-coloring of G using (p + q)(n − 1) + ∆(H ) + 2 colors. By Theorem 3.3, we can obtain the following result directly. Corollary 3.1. For any integers m ≥ 1 and n ≥ 2 we have

χat (Kn [C4m ]) = χat (Kn [P4m ]) = 4m(n − 1) + 4.

6

S. Tian, Q. Wang / Discrete Applied Mathematics (

)

–

Fig. 1. Two edge-disjoint Hamilton cycles in C7∗ [K 2 ] (heavy lines denote the edges of C 1 and dashed lines denote the edges of C 2 ).

For the lexicographic product G[K m ] of graphs G and K m , if G is a tree, then by Lemma 1.6 and Theorem 3.1, we get the following theorem. Theorem 3.4. Let T be a tree of order n ≥ 3. For any integer m ≥ 2, if T has two adjacent vertices of maximum degree, then χat (T [K m ]) = m∆(T ) + 2; otherwise, χat (T [K m ]) = m∆(T ) + 1. Proof. Since T is Class 1, the result follows from Lemma 1.6 and Theorem 3.1.

For the graph Cn [K m ] of even order, we get the exact values of χat (Cn [K m ]). Theorem 3.5. For any integers n ≥ 3 and m ≥ 2, if nm is even, then

χat (Cn [K m ]) = 2m + 2. Proof. Let Cn = u0 u1 . . . un−1 u0 , and let V0 , . . . , Vn−1 be the partite sets of G = Cn [K m ], where Vi = {wij |j = 1, . . . , m}, i = 0, . . . , n − 1. Then Gj = G[{w0j , w1j , . . . , wn−1,j }] ∼ = Cn , j = 1, . . . , m. First assume that n = 3. Then G ∼ = K3 [K m ] and m is even. By Theorem 3.2, χat (G) = 2m + 2. Now assume that n ≥ 4. We consider two cases separately.

Case 1. n is even. Then G is a 2m-regular bipartite graph. By Lemma 1.5, χat (G) = ∆(G) + 2 = 2m + 2. Case 2. n is odd. Clearly, χat (G) ≥ 2m + 2 and m is even. We need only to show that G has an avdt-coloring using 2m + 2 colors. By Lemma 1.7, the graph G1 ∪ · · · ∪ Gm can be total-colored with 4 colors in a way such that this coloring is adjacent vertex distinguishing, and vertices in the same partite set Vi receive the same color and meet the same set of colors. Let E ′ be the set of edges of the graph G1 ∪ · · · ∪ Gm and let G′ = G − E ′ . Then G′ is a 2(m − 1)-regular graph. We need to prove that G′ can be edge-colored with 2(m − 1) colors. Let D = A1 ∪ A2 ∪ B1 ∪ B2 be a set of 2(m − 1) colors such that |A1 | = |A2 | = m/2 − 1 and |B1 | = |B2 | = m/2, and let b2 be an element of B2 . Let Xi = {wij |j = 1, . . . , m/2} and Yi = {wij |j = m/2 + 1, . . . , m}, where i = 0, . . . , n − 1. And let {X0 , Y0 }, . . . , {Xn−1 , Yn−1 } (each Xi or Yi is considered as a vertex) be the partition sets of Cn∗ [K 2 ], where Cn∗ denotes a cycle of order n. Then Cn∗ [K 2 ] is an edge-disjoint union of the following two Hamilton cycles of order 2n: C 1 = X0 X1 . . . Xn−1 Yn−2 Yn−3 . . . Y0 Yn−1 X0 ,

C 2 = Cn∗ [K 2 ] − E (C 1 ).

For example, C7∗ [K 2 ] is an edge-disjoint union of two edge-disjoint Hamilton cycles of order 14, see Fig. 1. We first give an edge-coloring f1 of the induced subgraphs of G′ corresponding to the edges of C 1 as follows. For i = 0, . . . , n − 2, both graphs G′ [Xi ∪ Xi+1 ] and G′ [Yi−1 ∪ Yi ], where i − 1 is taken modulo n, are edge-colored with m/2 − 1 colors from A1 if i is even, and these graphs are edge-colored with m/2 − 1 colors from A2 if i is odd. After that, the graph G′ [Yn−2 ∪ Xn−1 ] is edge-colored with m/2 colors from A1 ∪ {b2 } and the graph G′ [Yn−1 ∪ X0 ] is edge-colored with m/2 colors from A2 ∪ {b2 }. We next give an edge-coloring f2 of the induced subgraphs of G′ corresponding to the edges of C 2 as follows. For i = 0, . . . , n − 1, the graph G′ [Xi ∪ Yi+1 ], where i + 1 is taken modulo n, is edge-colored with m/2 colors from B1 , and for j = 0, . . . , n − 3, the graph G′ [Yj ∪ Xj+1 ] is edge-colored with m/2 colors from B2 . After that, both graphs G′ [Yn−2 ∪ Yn−1 ] and G′ [Xn−1 ∪ X0 ] are edge-colored with m/2 − 1 colors from B2 \ {b2 }. It is clear that the colorings f1 and f2 can be combined to yield an edge-coloring of G′ using 2(m − 1) colors (see Fig. 2). Therefore, χat (G) ≤ 4 + 2(m − 1) = 2m + 2, and consequently, χat (G) = 2m + 2.

S. Tian, Q. Wang / Discrete Applied Mathematics (

)

–

Fig. 2. A 2(m − 1)-edge-coloring of graph G′ for n = 7 (every line denotes the edges of the induced subgraphs G′ [Xi the heavy lines correspond to the edges of C 1 and the dashed lines correspond to the edges of C 2 ).

7

Xj ], G′ [Yi

Yj ] or G′ [Xi

Yj ], where

Acknowledgments We gratefully acknowledge the Editor and reviewers for their valuable comments and constructive suggestions. References [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13]

S. Akbari, H. Bidkhori, N. Nosrati, r-Strong edge colorings of graphs, Discrete Math. 306 (2006) 3005–3010. P.N. Balister, E. Győri, J. Lehel, R.H. Schelp, Adjacent vertex distinguishing edge-colorings, SIAM J. Discrete Math. 21 (1) (2007) 237–250. J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, American Elsevier, New York, 1976. M. Chen, X. Guo, Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes, Inform. Process. Lett. 109 (2009) 599–602. K. Edwards, M. Horňák, M. Woźniak, On the neighbor-distinguishing index of a graph, Graphs Combin. 22 (2006) 341–350. H. Hatami, ∆ + 300 is a bound on the adjacent vertex distinguishing edge chromatic number, J. Combin. Theory Ser. B 95 (2005) 246–256. S. Tian, P. Chen, On adjacent vertex-distinguishing total coloring of two classes of product graphs, J. Math. Res. Exposition 27 (4) (2007) 733–737. S. Tian, P. Chen, On the adjacent vertex-distinguishing total coloring of K (r , 2m), J. Zhejiang Normal Univ. Natur. Sci. 31 (1) (2008) 23–25. S. Tian, J. Li, Z. Zhang, et al., The adjacent strong edge chromatic number of K (r , 2), Math. Econ. 22 (1) (2005) 105–107. H. Wang, On the adjacent vertex-distinguishing total chromatic numbers of the graphs with ∆(G) = 3, J. Comb. Optim. 14 (2007) 87–109. H.P. Yap, Total Coloring of Graph, Springer Verlag, New York, 1996. Z. Zhang, X. Chen, J. Li, B. Yao, X. Lu, J. Wang, On adjacent-vertex-distinguishing total coloring of graphs, Sci. China Ser. A 48 (3) (2005) 289–299. Z. Zhang, L. Liu, J. Wang, Adjacent strong edge coloring of graphs, Appl. Math. Lett. 15 (2002) 623–626.