0 Introduction

The graph coloring has a widely applications in many subject. We only consider simple, finite and undirected graph in this paper.

Let G be a graph with maximum degree Δ(G), k be a positive integer. Suppose f is an edge coloring (i.e., f is an assignment of k colors 1, 2, …, k to the edges of G). For each element z∈E(G), the color of z under f is denoted by f(z). For every vertex x, the set of colors of edges incident with x is denoted by S_f(x) (or simply S(x) if no confusion arise), and is called the color set of x under edge coloring f. If f is proper (i.e., any two adjacent edges receive the different colors) and S(u)≠S(v) for each edge uv∈E(G), then f is called a k-adjacent vertex distinguishing proper edge coloring of G(or a k-AVDPEC). The minimum number of colors required in an AVDPEC of G is called the adjacent vertex distinguishing proper edge chromatic number of G, denoted by χ′_a(G), i.e.,

$ {{{{\chi }'}}_{a}}\left( G \right)=\text{min}\{k|G~\text{has}\ \text{a}\ k-\text{AVDPEC}\}. $

Suppose g is a total coloring (i.e., g is an assignment of k colors 1, 2, …, k to the vertices and edges of G). For each element z∈V(G)∪E(G), the color of z under g is denoted by g(z). For every vertex x∈V(G), the set of colors of edges incident with x together with the color assigned to x is denoted by C_g(x) (or simply C(x) if no confusion arise), and is called the color set of x under total coloring g. If g is proper (i.e., any two adjacent or incident elements receive the different colors) and C(u)≠C(v) for each edge uv∈E(G), then g is called a k-adjacent vertex distinguishing total coloring of G(or a k-AVDTC). The minimum number of colors required in an AVDTC of G is called the adjacent vertex distinguishing total chromatic number of G, denoted by χ″_a(G), i.e.,

$ {{{{\chi }''}}_{a}}\left( G \right)=\text{min}\{k|G~\text{has}\ \text{a}\ ~k-\text{AVDTC}\}. $

The adjacent vertex distinguishing proper edge coloring of graphs is investigated in several papers^[1-6]. The adjacent vertex distinguishing total coloring of graphs is proposed in [7] and studied in several papers^[7-16]. Especially, the adjacent vertex distinguishing total chromatic number of P_mK_n is obtained in [11] and the adjacent vertex distinguishing total chromatic numbers of the Cartesian products of P_m with P_n and C_n, and the Cartesian product of C_m with C_n are given in [13]. We use the usual notation as can be found in any book on graph theory^[17].

1 Preliminaries

Lemma 1^[6-7]   Let G be a simple connected graph with order at least 3. If there are two adjacent vertices of maximum degree in G, then χ′_a(G)≥Δ(G)+1 and χ″_a(G)≥Δ(G)+2.

Lemma 2^[18]   χ″=(C_m□C_n)=5(m, n≥3).

From lemma 2, we can obtain the following lemma 3 immediately since an r-regular graph G has (equitable) total chromatic number r+1 if and only if G has adjacent vertex distinguishing proper edge chromatic number r+1.

Lemma 3   χ′_a(C_m□C_n)=5(m, n≥3).

Lemma 4^[13]   (ⅰ) ${{{{\chi }''}}_{a}}\left( {{P}_{m}}\square {{C}_{n}} \right)=\left\{ \begin{align} & 5, \text{ }m=2; \\ & 6, \text{ }m=3. \\ \end{align} \right.$

(ⅱ) χ″_a(C_m□C_n)=6, m, n≥3.

Suppose G is a graph. If a bijection σ from V(G) to V(G) preserves the adjacency relation, i.e., σ(u) is adjacent to σ(v) if and only if u is adjacent to v for any two distinct vertices u and v of G, then σ is called an automorphism of graph G.

If G has an automorphism σ, such that for any vertex v∈V(G), v and σ(v) are adjacent (and then v≠σ(v)), then we say that graph G is of property (P).

The Cartesian product of two graphs G and H, denoted by G□H, is a graph with vertex set V(G)×V(H) and edge set {(u, v)(u′, v′)|uu′∈E(G), v=v′or u=u′, vv′∈E(H)}.

Let Q_t denote t-cube, i.e.,

$ {{Q}_{t}}=\underbrace{{{K}_{2}}\square {{K}_{2}}\square \cdots \square {{K}_{2}}}_{t}. $

For two types of adjacent vertex distinguishing colorings of the Cartesian product of a graph with another graph which is of property (P), we will give some important results in section 2 and section 3.

2 The relation between AVDPEC andCartesian product of two graphs

Theorem 1   Suppose G is a graph without isolated edge and G has property (P), t is a positive integer.

(ⅰ) χ′_a(G□K₂)≤χ′_a(G)+1;

(ⅱ) χ′_a(G□Q_t)≤χ′_a(G)+t, i.e.,

χ′_a(G□$\underbrace{{{K}_{2}}\square {{K}_{2}}\square \cdots \square {{K}_{2}}}_{t}$)χ′_a(G)+t;

(ⅲ) If χ′_a(G)=Δ(G)+1, then χ′_a(G□K₂)=Δ(G)+2;

(ⅳ) If χ′_a(G)=Δ(G)+1, then χ′_a(G□Q_t)=Δ(G)+t+1;

(ⅴ) χ′_a(Q_t)=t+1, t≥3.

Proof   (ⅰ) Since G has property (P), we may suppose that σ is an automorphism of G such that σ(v) is adjacent to v for each vertex v of G. Set V(G)={u₁, u₂, …, u_n}, G⁽¹⁾ and G⁽²⁾ are two disjoint graphs which are isomorphic to G, and V(G⁽ⁱ⁾)={u₁⁽ⁱ⁾, u₂⁽ⁱ⁾, …, u_n⁽ⁱ⁾}, i=1, 2. u_j⁽ⁱ⁾ and u_k⁽ⁱ⁾ are adjacent in G⁽ⁱ⁾ if and only if u_j and u_k are adjacent in G, i=1, 2. We construct a graph (which is isomorphic to) G□K₂ from G⁽¹⁾∪G⁽²⁾ by adding n new edges u_j⁽¹⁾u_j⁽²⁾, j=1, 2, …, n. Setting s=χ′_a(G), f is an AVDPEC of G using s colors 1, 2, …, s. Now, we use colors 1, 2, …, s, s+1 to properly color edges of graph G□K₂, where the edges of G⁽¹⁾ are colored in the same way as G, i.e., for any edge u_ju_k∈E(G), we assign color f(u_ju_k) to edge u_j⁽¹⁾u_k⁽¹⁾ of G⁽¹⁾, each edge u_j⁽²⁾u_k⁽²⁾ of G⁽²⁾ is colored with the color of edge σ(u_j)σ(u_k) under f, j, k=1, 2, …, n; We assign color s+1 to all edges u_j⁽¹⁾u_j⁽²⁾, j=1, 2, …, n. The resulting (s+1)-proper edge coloring of G□K₂ is denoted by ${\tilde{f}}$. The color set of a vertex y of G□K₂ under ${\tilde{f}}$ is denoted by $\tilde{S}\left( y \right)$.

Obviously, for each j∈{1, 2, …, n}, we have ${\tilde{S}}$(u_j⁽¹⁾)=${\tilde{S}}$(u_j)∪{s+1}, ${\tilde{S}}$(u_j⁽²⁾)=${\tilde{S}}$(σ(u_j))∪{s+1}. Note that for each edge uv∈E(G), we have S(u)≠S(v). Thus ${\tilde{S}}$(u⁽¹⁾)≠${\tilde{S}}$(v⁽¹⁾) and ${\tilde{S}}$(u⁽²⁾)≠${\tilde{S}}$(v⁽²⁾) for any two adjacent vertices u and v of G. Since S(u)≠S(σ(u)) for any vertex u, ${\tilde{S}}$(u⁽¹⁾)≠${\tilde{S}}$(u⁽²⁾). Therefore, ${\tilde{f}}$ is an AVDPEC of G□K₂ using s+1 colors 1, 2, …, s, s+1.

Theorem 1 (ⅰ) follows.

(ⅱ) Since for any positive integer l, G□Q_l is of property (P) when G is of property (P), we can obtain (ⅱ) by applying (ⅰ) repeatedly.

(ⅲ) By theorem 1(ⅰ), χ′_a(G□K₂)≤Δ(G)+2. On the other hand, G□K₂ has adjacent vertices of maximum degree and Δ(G□K₂)=Δ(G)+1, so χ′_a(G□K₂)≥Δ(G)+2 by lemma 1. Therefore, χ′_a(G□K₂)=Δ(G)+2.

(ⅳ) We can obtain (ⅳ) by using (ⅲ) repeatedly.

(ⅴ) Note that χ′_a(Q₃)=4=Δ(Q₃)+1 (see fig. 1) and Q_t=Q₃$\underbrace{{{K}_{2}}\square {{K}_{2}}\square \cdots \square {{K}_{2}}}_{t-3}$(t≥4), by using (ⅳ), we will obtain (ⅴ).

Lemma 5   For any graph G, G□K₂ has property (P).

Proof   We use the notations in the proof procedure of theorem 1 (ⅰ). We easily obtain an automorphism σ of G□K₂: u_j⁽¹⁾u_j⁽²⁾, u_j⁽²⁾u_j⁽¹⁾, j=1, 2, …, n. Since σ(u_j⁽ⁱ⁾) and u_j⁽ⁱ⁾ are adjacent in G□K₂, i=1, 2, j=1, 2, …, n, G□K₂ has property (P).

From theorem 1 and lemma 5, we may obtain the following corollary 1.

Corollary 1   For any graph G with no isolated edge and integer t(≥1), we have

(ⅰ) χ′_a(G□$\underbrace{{{K}_{2}}\square {{K}_{2}}\square \cdots \square {{K}_{2}}}_{t}$)≤χ′_a(G□K₂)+t-1, i.e., χ′_a(G□Q_t)≤χ′_a(G□K₂)+t-1;

(ⅱ) If χ′_a(G□K₂)=Δ(G□K₂)+1, then χ′_a(G□Q_t)=χ′_a(G□K₂)+t-1.

Note that for any graph G and integer number r(≥3), G□C_r has property (P), so we have the following corollary 2 by theorem 1.

Corollary 2   (ⅰ) χ′_a(G□C_r□Q_t)≤χ′_a(G□C_r)+t;

(ⅱ) If χ′_a(G□C_r)=Δ(G□C_r)+1, then χ′_a(G□C_r□Q_t)=χ′_a(G□C_r)+t.

Theorem 2   Suppose that graph G has property (P) and has no isolated edge, r(≥4) is an even integer.

(ⅰ) χ′_a(G□C_r)≤χ′_a(G)+2;

(ⅱ) If χ′_a(G)=Δ(G)+1, then χ′_a(G□C_r)=Δ(G)+3.

Proof   (ⅰ) Set C_r=v₁v₂…v_rv₁, V(G)={u₁, u₂…, u_n}. Let G⁽ⁱ⁾ be a graph (which is isomorphic to G) induced by {(u, v_i)|u∈V(G)}. If we denote (u_j, v_i) by u_j⁽ⁱ⁾, then V(G⁽ⁱ⁾)={u₁⁽ⁱ⁾, u₂⁽ⁱ⁾, …, u_n⁽ⁱ⁾}, i=1, 2, …, r. Setting s=χ′_a(G), f is an AVDPEC of G using s colors, 1, 2, …, s.

We will give an edge coloring of G□C_r using s+2 colors as follows:

We assign the color f(u_ju_k) to the edge u_j⁽ⁱ⁾u_k⁽ⁱ⁾ when i is even; Each edge u_j⁽ⁱ⁾u_k⁽ⁱ⁾ of G⁽ⁱ⁾ is colored by the color of edge σ(u_j)σ(u_k) under f when i is odd; We assign color s+1 to all edges u_j⁽ⁱ⁾u_j⁽ⁱ⁺¹⁾ when i is odd; We assign color s+2 to all edges u_j⁽ⁱ⁾u_j⁽ⁱ⁺¹⁾ when i is even. Note u_j^(r+1)=u_j⁽¹⁾. So, when i is odd, for any two adjacent vertices u_j⁽ⁱ⁾ and u_k⁽ⁱ⁾ in G⁽ⁱ⁾, their color sets are S(u_j)∪{s+1, s+2} and S(u_k)∪{s+1, s+2}, respectively. Obviously, they are different; When i is even, for any two adjacent vertices u_j⁽ⁱ⁾ and u_k⁽ⁱ⁾ in G⁽ⁱ⁾, their color sets are S(σ(u_j))∪{s+1, s+2} and S(σ(u_k))∪{s+1, s+2}, respectively. Obviously, they are different. The color sets of u_j⁽ⁱ⁾ and u_j⁽ⁱ⁺¹⁾ are either S(u_j)∪{s+1, s+2} and S(σ(u_j))∪{s+1, s+2} or S(σ(u_j))∪{s+1, s+2} and S(u_j)∪{s+1, s+2}, respectively. Thus u_j⁽ⁱ⁾ and u_j⁽ⁱ⁺¹⁾ are distinguished (since u_j and σ(u_j) are distinguished under f).

(ⅱ) By theorem 2(ⅰ), χ′_a(G□C_r)≤χ′_a(G)+2=Δ(G)+3. Since Δ(G□C_r)=Δ(G)+2 and G□C_r has adjacent vertices of maximum degree, χ′_a(G□C_r)≥Δ(G)+3 by lemma 1. Thus χ′_a(G□C_r)=Δ(G)+3.

From theorem 2, we will obtain the following corollary 3 immediately.

Corollary 3   Suppose that G is of property (P) and has no isolated edge, r₁, r₂, …, r_s are even integers at least 4.

(ⅰ) χ′_a(G□C_r1□C_r2□…□C_rs)≤χ′_a(G)+2s;

(ⅱ) If χ′_a(G)=Δ(G)+1, then χ′_a(G□C_r1□C_r2□…□C_rs)=Δ(G)+2s+1.

Note that for any integers m, n≥3, we have χ′_a(C_m□C_n)=5=Δ(C_m□C_n)+1. By lemma 3, we may obtain the following corollary 4 from theorem 2.

Corollary 4   If m, n, r₁, r₂, …, r_s be integers at least 3, and each of r₁, r₂, …, r_s is even, then χ′_a(C_m□C_n□C_r1□C_r2□…□C_rs)=2s+5, especially χ′_a(C_m□C_n□C_r1)=7.

Theorem 3   If G has three AVDPEC's using χ′_a(G) colors, such that for each vertex v∈V(G), the color sets of v are different under the three colorings, then χ′_a(G□C_r)≤χ′_a(G)+3.

Proof   Similar to the proof of theorem 2(ⅰ), we can complete the proof of theorem 3.

3 The relation between AVDTC andCartesian product of two graphs

Theorem 4   Suppose G is of property (P), and t is a positive integer.

(ⅰ) χ″_a(G□K₂)≤χ″_a(G)+1;

(ⅱ) χ″_a(G□$\underbrace{{{K}_{2}}\square {{K}_{2}}\square \cdots \square {{K}_{2}}}_{t}$)=χ″_a(G□Q_t)≤χ″_a(G)+t;

(ⅲ) If χ″_a(G)=Δ(G)+2, then χ″_a(G□K₂)=Δ(G)+3;

(ⅳ) If χ″_a(G)=Δ(G)+2, then χ″_a(G□Q_t)=Δ(G)+t+2.

(ⅴ) χ″_a(Q_t)=t+2.

Proof   (ⅰ) We use the notations in the proof of theorem 4 (ⅰ). Set s=χ″_a(G), g is an AVDTC of G using s colors 1, 2, …, s. Now, we use colors 1, 2, …, s, s+1 to properly color vertices and edges of graph G□K₂, so that the vertices and edges of G⁽¹⁾ are colored in the same way as G, i.e., for any vertex u_j∈V(G) and edge u_ju_k∈E(G), we assign color g(u_j) to vertex u_j⁽¹⁾ of G⁽¹⁾ and g(u_ju_k) to edge u_j⁽¹⁾u_k⁽¹⁾ of G⁽¹⁾; Each vertex u_j⁽²⁾ of G ⁽²⁾ is colored with the color of vertex σ(u_j) under g, each edge u_j⁽²⁾u_k⁽²⁾ of G⁽²⁾ is colored with the color of edge σ(u_j)σ(u_k) under g, j, k=1, 2, …, n; We assign color s+1 to all edges u_j⁽¹⁾u_j⁽²⁾, j=1, 2, …, n. The resulting (s+1)-proper total coloring of G□K₂ is denoted by ${\tilde{g}}$. The color set of a vertex y of G□K₂ under ${\tilde{g}}$ is denoted by ${\tilde{C}}$(y).

Obviously, for each j∈{1, 2, …, n}, we have ${\tilde{C}}$(u_j⁽¹⁾)=C(u_j)∪{s+1}, ${\tilde{C}}$(u_j⁽²⁾)=C(σ(u_j))∪{s+1}. Note that for each edge uv∈E(G), we have C(u)≠C(v). Thus ${\tilde{C}}$(u⁽¹⁾)≠${\tilde{C}}$(v⁽¹⁾) and ${\tilde{C}}$(u⁽²⁾)≠${\tilde{C}}$(v⁽²⁾) for any two adjacent vertices u and v of G. Since C(u)≠C(σ(u)) for any vertex u, ${\tilde{C}}$(u⁽¹⁾)≠${\tilde{C}}$(u⁽²⁾). Therefore, ${\tilde{g}}$ is an AVDTC of G□K₂ using s+1 colors 1, 2, …, s, s+1.

The theorem 4(ⅰ) follows.

(ⅱ) Since for any positive integer l, G□Q_l is of property (P) when G is of property (P), we can obtain theorem 4(ⅱ) by applying theorem 4(ⅰ) repeatedly.

(ⅲ) By theorem 4(ⅰ), χ″_a(G□K₂)≤Δ(G)+2. On the other hand, G□K₂ has adjacent vertices of maximum degree and Δ(G□K₂)=Δ(G)+1, so χ″_a(G□K₂)≥Δ(G)+2 by lemma 1. Therefore, χ″_a(G□K₂)=Δ(G)+2.

(ⅳ) We can obtain theorem 4(ⅳ) by using theorem 4(ⅲ) repeatedly.

(ⅴ) Note that χ″_a(K₂)=χ″_a(Q₁)=3=Δ(Q₁)+2, and Q_t=Q_t-1□K₂=Q_t-2□Q₂, we have χ″_a(Q_t)=t+2 by theorem 4(ⅳ).

From theorem 4 and that G□K₂ is of property (P), we obtain the following corollary 5.

Corollary 5   Suppose t(≥2) is an integer.

(ⅰ) χ″_a(G□Q_t)≤χ″_a(G□K₂)+t-1.

(ⅱ) If χ″_a(G□K₂)=Δ(G□K₂)+2, then χ″_a(G□Q_t)=χ″_a(G□K₂)+t-1.

From theorem 4 and that G□C_r is of property (P), we obtain the following corollary 6.

Corollary 6   (ⅰ) χ″_a(G□C_r□Q_t)≤χ″_a(G□C_r)+t;

(ⅱ) If χ″_a(G□C_r)=Δ(G□C_r)+2, then χ″_a(G□C_r□Q_t)=χ″_a(G□C_r)+t.

Theorem 5   Suppose that G is of property (P), r(≥4) is even.

(ⅰ) χ″_a(G□C_r)≤χ″_a(G)+2;

(ⅱ) If χ″_a(G)=Δ(G)+2, then χ″_a(G□C_r)=Δ(G)+4.

Proof   Similar to the proof of theorem 2, we can complete the proof of theorem 5. The process is easy, so we omitted it.

By generalizing theorem 5, we have

Corollary 7   Suppose G is of property (P) and r₁, r₂, …, r_s(≥4) are even.

(ⅰ) χ″_a(G□C_r1□C_r2□…□C_rs)≤χ″_a(G)+2s;

(ⅱ) If χ″_a(G)=Δ(G)+2, then χ″_a(G□C_r1□C_r2□…□C_rs)=Δ(G)+2s+2.

From lemma 4, theorem 4(ⅳ) and corollary 7(ⅱ), we may deduce the following corollary 8.

Corollary 8   If m≥3, n≥3, t≥1, r₁, r₂, …, r_s(≥4) are even, then

(ⅰ) χ″_a(P₂□C_n□Q_t)=t+5;

(ⅱ) χ″_a(P₂□C_n□C_r1□C_r2□…□C_rs)=2s+5;

(ⅲ) χ″_a(P_m□C_n□Q_t)=t+6;

(ⅳ) χ″_a(P_m□C_n□C_r1□C_r2□…□C_rs)=2s+6;

(ⅴ) χ″_a(C_m□C_n□Q_t)=t+6;

(vi) χ″_a(C_m□C_n□C_r1□C_r2□…□C_rs)=2s+6.

Theorem 6   If G has three AVDTC's using χ″_a(G) colors, such that for each vertex v∈V(G), the color sets of v under the three colorings are different, and the colors of v under the three colorings are different, then χ″_a(G□C_r)≤χ″_a(G)+3.

Proof   Similar to the proof of theorem 5(ⅰ) or theorem 2(ⅰ), we can complete the proof of theorem 6.