AVD proper edge-coloring of some families of graphs

1. Introduction

For the terminology and notations, we refer to Ref. 1. Let $G$ be a finite, simple, undirected and connected graph. Let $\mathrm{\Delta }(G)$ denote the maximum degree of $G$. A proper edge-coloring $\sigma$ is a mapping from $E(G)$ to the set of colors such that any two adjacent edges receive distinct colors. For any vertex $v$ of $G$, let $S_{\sigma }(v)$ denote the set of colors of all edges incident to $v$. A proper edge-coloring $\sigma$ is said to be adjacent vertex-distinguishing (AVD) if $S_{\sigma }(u)\ne S_{\sigma }(v)$ for every adjacent vertices $u$ and $v$. The minimum number of colors required for an adjacent vertex-distinguishing proper edge-coloring of $G$, denoted by ${\chi }_{as}^{\prime }(G)$, is called the adjacent vertex-distinguishing proper edge-chromatic index (AVD proper edge-chromatic index) of $G$. Thus, ${\chi }_{as}^{\prime }(G)\ge {\chi }^{\prime }(G)$.

Conjecture 1.1 (Ref. 2). For any connected graph $G(|V(G)|\ge 6)$, ${\chi }_{as}^{\prime }(G)\le \mathrm{\Delta }(G)+2$.

If $H$ is a subgraph of $G$, it is interesting that ${\chi }_{as}^{\prime }(H)\le {\chi }_{as}^{\prime }(G)$ is not always true. Let $K_{m,n}$ be the complete bipartite graph, then ${\chi }_{as}^{\prime }(K_{2,3})=3$, and $K_{2,3}-e$ for any edge, then ${\chi }_{as}^{\prime }(K_{2,3}-e)=4$. Deletion of an edge of a graph may also decrease the coloring number of the graph. Let $n\ge 3$, then ${\chi }_{as}^{\prime }(K_{1,n})=n$ and ${\chi }_{as}^{\prime }(K_{1,n}-e)=n-1$.

In Ref. 2, Zhang et al. proved the following: if $G$ has $n$ components $G_i,1\le i\le n$ with at least three vertices in each, then ${\chi }_{as}^{\prime }(G)={max}_{1\le i\le n}\{{\chi }_{as}^{\prime }(G_i)\}$. So we consider only connected graphs. For a tree $T$ with $|V(T)|\ge 3$, if any two vertices of maximum degree are nonadjacent, then ${\chi }_{as}^{\prime }(T)=\mathrm{\Delta }(T)$. If $T$ has two vertices of maximum degree which are adjacent, then ${\chi }_{as}^{\prime }(T)=\mathrm{\Delta }(T)+1$. For the cycle $C_n$, we have ${\chi }_{as}^{\prime }(C_n)=3$ for $n\equiv 0(\mathrm{\text{mod}}3)$; otherwise, ${\chi }_{as}^{\prime }(C_n)=4$ for $n\not\equiv 0(\mathrm{\text{mod}}3)$ and $n\ne 5$, and ${\chi }_{as}^{\prime }(C_n)=5$ for $n=5$. For the complete bipartite graph $K_{m,n}$ for $1\le m\le n$, we have ${\chi }_{as}^{\prime }(K_{m,n})=n$ if $m<n$, and ${\chi }_{as}^{\prime }(K_{m,n})=n+2$ if $m=n\ge 2$. For the complete graph $K_n(n\ge 3)$, we have ${\chi }_{as}^{\prime }(K_n)=n$ for $n\equiv 1(\mathrm{\text{mod }}2)$; and ${\chi }_{as}^{\prime }(K_n)=n+1$ for $n\equiv 0(\mathrm{\text{mod}}2)$. If $G$ is a graph which has two adjacent maximum-degree vertices, then ${\chi }_{as}^{\prime }(G)\ge \mathrm{\Delta }(G)+1$. If $G$ is a graph such that the degrees of any two adjacent vertices are different, then ${\chi }_{as}^{\prime }(G)=\mathrm{\Delta }(G)$ In Ref. 3, Shiu et al. proved the following: for $n\ge 3$, we have ${\chi }_{as}^{\prime }(F_n)=n$ if $n=3,4$, and ${\chi }_{as}^{\prime }(F_{n-1})=n-1$ for $n\ge 5$. For $n\ge 3$, we have ${\chi }_{as}^{\prime }(W_n)=5$ if $n=3$, and ${\chi }_{as}^{\prime }(W_n)=n$ for $n\ge 4$. In Ref. 4, Hatami proved that if $G$ is a graph with no isolated edges and maximum degree $\mathrm{\Delta }(G)>{10}^{20}$, then ${\chi }_{as}^{\prime }\le \mathrm{\Delta }+300$. In Ref. 5, Balister et al. proved the following: if $G$ is a $k$-chromatic graph with no isolated edges, then ${\chi }_{as}^{\prime }(G)\le \mathrm{\Delta }(G)+O(logk)$. In Ref. 6, Axenovich et al. obtained the upper bound for adjacent vertex-distinguishing edge-colorings of graphs. In Ref. 7, Baril et al. obtained the exact values for adjacent vertex-distinguishing edge-coloring of meshes. In Ref. 8, Bu et al. found the adjacent vertex-distinguishing edge-colorings of planar graphs with a girth of at least six. In Ref. 9, Chen and Li obtained the adjacent vertex-distinguishing proper edge-coloring of planar bipartite graphs with $\mathrm{\Delta }=9$, 10 or 11.

Observation 1.1. If a connected graph $G$ contains two adjacent vertices of degree $\mathrm{\Delta }(G)$, then ${\chi }_{as}^{\prime }(G)\ge 1+\mathrm{\Delta }(G)$.

Observation 1.2. If $G$ is a graph such that the degrees of any two adjacent vertices are different, then ${\chi }_{as}^{\prime }(G)=\mathrm{\Delta }(G)$.

2. AVD Proper Edge-Chromatic Indices of Middle Graph, Splitting Graph and Shadow Graph

In this section, we investigate the AVD proper edge-colorings of middle graph, splitting graph and shadow graph of path and cycle, and present the results in the following subsections.

2.1. AVD proper edge-chromatic index of middle graph of path and cycle

The middle graph $M(G)$ of a connected graph $G$ is the graph whose vertex set is $V(G)\cup E(G)$ and in which two vertices are adjacent if and only if either they are the adjacent edges of $G$ or one is the vertex of $G$ and the other is an edge incident on it.

Theorem 2.1.

Proof. Let $P_n=x_1{x}_2\dots x_n$ and $e_1,e_2,\dots ,e_{n-1}$ be the edges of $P_n$. $M(P_n)$ is the middle graph of $P_n$ with vertices $x_1,x_2,\dots ,x_{n-1},x_n,x_1^{\prime },x_2^{\prime },\dots ,x_{n-1}^{\prime }$ such that $f_i=x_i{x}_i^{\prime }$, $g_i=x_{i+1}{x}_i^{\prime }$, for $i\in \{1,2,\dots ,n-1\}$, and $h_i=x_i^{\prime }{x}_{i+1}^{\prime }$, for $i\in \{1,2,\dots ,n-2\},$ where $e_1=x_1^{\prime },e_2=x_2^{\prime },\dots ,e_{n-1}=x_{n-1}^{\prime }$.

Define $\sigma :E(M(P_2))\to \{1,2,3\}$ as follows: $\sigma (f_1)=2=\sigma (f_2)$, $\sigma (g_1)=3$ and $\sigma (h_1)=1$. Therefore, $\sigma$ is a proper edge-coloring. The induced vertex-color sets are: $S_{\sigma }(x_1)=2,S_{\sigma }(x_2)=\{2,3\}{S}_{\sigma }(x_1^{\prime })=\{1,2,3\}$ and $S_{\sigma }(x_2^{\prime })=\{1,2\}$. Hence, $\sigma$ is an AVD proper edge-coloring of $M(P_2)$. By Observation 1.1, ${\chi }_{as}^{\prime }(M(P_2))\ge 3,$ and so ${\chi }_{as}^{\prime }(M(P_2))=3$. Define $\sigma :E(M(P_3))\to \{1,2,3,4\}$ as follows: $\sigma (f_1)=2=\sigma (f_2)$, $\sigma (g_1)=3$, $\sigma (g_2)=4$ and $\sigma (h_1)=1$. Therefore, $\sigma$ is a proper edge-coloring. The induced vertex-color sets are: $S_{\sigma }(x_1)=2$, $S_{\sigma }(x_2)=\{2,3\}$, $S_{\sigma }(x_3)=4$, $S_{\sigma }(x_1^{\prime })=\{1,2,3\}$ and $S_{\sigma }(x_2^{\prime })=\{1,2,4\}$. Hence, $\sigma$ is an AVD proper edge-coloring of $M(P_3)$. By Observation 1.1, ${\chi }_{as}^{\prime }(M(P_3))\ge 4$, and so ${\chi }_{as}^{\prime }(M(P_3))=4$. Define $\sigma :E(M(P_4))\to \{1,2,3,4\}$ as follows: $\sigma (f_1)=\sigma (f_2)=\sigma (f_3)=2$, $\sigma (g_1)=\sigma (g_2)=\sigma (g_3)=3$, $\sigma (h_1)=1$ and $\sigma (h_2)=4$. Therefore, $\sigma$ is a proper edge-coloring. The induced vertex-color sets are: $S_{\sigma }(x_1)=2$, $S_{\sigma }(x_2)=\{2,3\}=S_{\sigma }(x_3),S_{\sigma }(x_3)=3$, $S_{\sigma }(x_1^{\prime })=\{1,2,3\}$, $S_{\sigma }(x_2^{\prime })=\{1,2,3,4\}$ and $S_{\sigma }(x_3^{\prime })=\{2,3,4\}$. Hence, $\sigma$ is an AVD proper edge-coloring of $M(P_4)$. By Observation 1.1, ${\chi }_{as}^{\prime }(M(P_4))\ge 4$, and so ${\chi }_{as}^{\prime }(M(P_4))=4$.

For $n\ge 5,$ since $\mathrm{\Delta }(M(P_n))=4$, by Observation 1.1, ${\chi }_{as}^{\prime }(M(P_n))\ge 5$. To show ${\chi }_{as}^{\prime }(M(P_n))\le 5$, we define $\sigma :E(M(P_n))\to \{1,2,3,4,5\}$ as follows:

Therefore, $\sigma$ is a proper edge-coloring. It remains to show that $\sigma$ is an AVD proper edge-coloring. We compare the sets of colors of adjacent vertices of the same degree.

The induced vertex-color sets are as follows:

Therefore, $\sigma$ is an AVD proper edge-coloring of $M(P_n)$. Hence ${\chi }_{as}^{\prime }(M(P_n))=5$. □

Theorem 2.2. ${\chi }_{as}^{\prime }(M(C_n))=5$ for $n\ge 4$.

Proof. Let $C_n=x_1{x}_2\dots x_n{x}_1$ and $e_1,e_2,\dots ,e_n$ be the edges of $C_n$. $M(C_n)$ is the middle graph of $C_n$ with the vertices $x_1,x_2,\dots ,x_{n-1},x_n,x_1^{\prime },x_2^{\prime },\dots ,x_{n-1}^{\prime },x_n^{\prime }$ such that $f_i=x_i{x}_i^{\prime }$, $g_i=x_{i+1}{x}_i^{\prime }$ and $h_i=x_i^{\prime }{x}_{i+1}^{\prime }$, for $i\in \{1,2,\dots ,n\}$, where $x_{n+1}^{\prime }=x_1^{\prime }$, $x_{n+1}=x_1$ and $e_1=x_1^{\prime },e_2=x_2^{\prime },\dots ,e_{n-1}=x_{n-1}^{\prime },e_n=x_n^{\prime }$.

For $n\ge 4$, since $\mathrm{\Delta }(M(C_n))=4$, by Observation 1.1, ${\chi }_{as}^{\prime }(M(C_n))\ge 5$. To show ${\chi }_{as}^{\prime }(M(C_n))\le 5$, we consider two cases and in each case, we first define $\sigma :E(M(C_n))\to \{1,2,3,4,5\}$ as follows:

Case 1. If $n$ is even,

Therefore, $\sigma$ is a proper edge-coloring. It remains to show that $\sigma$ is an AVD proper edge-coloring. We compare the sets of colors of adjacent vertices of the same degree.

The induced vertex-color sets are as follows:

Observe that $\sigma$ is an AVD proper edge-coloring of $M(C_n)$. Hence ${\chi }_{as}^{\prime }(M(C_n))=5$.

Case 2. If $n$ is odd,

Therefore, $\sigma$ is a proper edge-coloring. It remains to show that $\sigma$ is an AVD proper edge-coloring. We compare the sets of colors of adjacent vertices of the same degree.

The induced vertex-color sets are as follows:

Observe that $\sigma$ is an AVD proper edge-coloring of $M(C_n)$. Hence ${\chi }_{as}^{\prime }(M(C_n))=5$. □

2.2. AVD proper edge-chromatic index of splitting graph of path and cycle

The splitting graph of a graph $G$, $S^{\prime }(G)$ is obtained by adding a new vertex $v^{\prime }$ corresponding to each vertex $v$ of $G$ such that $N(v)=N(v^{\prime })$, where $N(v)$ and $N(v^{\prime })$ are the neighborhood sets of $v$ and $v^{\prime }$, respectively.

Theorem 2.3.

Proof. Let $P_n=x_1{x}_2\dots x_n$ and $x_1^{\prime },x_2^{\prime },\dots ,x_n^{\prime }$ be the newly added vertices corresponding to the vertices $x_1,x_2,\dots ,x_n$ to form $S^{\prime }(P_n)$. In $S^{\prime }(P_n)$ for $i\in \{1,2,\dots ,n-1\}$, let $e_i=x_i{x}_{i+1}$, $f_i=x_i^{\prime }{x}_{i+1}$ and $g_i=x_{i+1}^{\prime }{x}_i$.

Define $\sigma :E(S^{\prime }(P_2))\to \{1,2,3\}$ as follows: $\sigma (e_1)=1$, $\sigma (f_1)=3$ and $\sigma (g_1)=2.$ Therefore, $\sigma$ is a proper edge-coloring. The induced vertex-color sets are: $S_{\sigma }(x_1)=\{1,2\}$, $S_{\sigma }(x_2)=\{1,3\}$, $S_{\sigma }(x_1^{\prime })=3$ and $S_{\sigma }(x_2^{\prime })=2$. Hence, $\sigma$ is an AVD proper edge-coloring of $S^{\prime }(P_2)$. By Observation 1.1, ${\chi }_{as}^{\prime }(S^{\prime }(P_2))\ge 3$, and so ${\chi }_{as}^{\prime }(S^{\prime }(P_2))=3$.

Define $\sigma :E(S^{\prime }(P_3))\to \{1,2,3,4\}$ as follows: $\sigma (e_1)=1$, $\sigma (e_2)=4$, $\sigma (f_1)=2=\sigma (g_1)$ and $\sigma (f_2)=3=\sigma (g_2)$. Therefore, $\sigma$ is a proper edge-coloring. The induced vertex-color sets are: $S_{\sigma }(x_1)=\{1,2\}$, $S_{\sigma }(x_2)=\{1,2,3,4\}$, $S_{\sigma }(x_3)=\{3,4\}$, $S_{\sigma }(x_1^{\prime })=2$, $S_{\sigma }(x_2^{\prime })=\{2,3\}$ and $S_{\sigma }(x_3^{\prime })=3$. Therefore, $\sigma$ is an AVD proper edge-coloring of $S^{\prime }(P_3)$. By Observation 1.1, ${\chi }_{as}^{\prime }(S^{\prime }(P_3))\ge 4$, and so ${\chi }_{as}^{\prime }(S^{\prime }(P_3))=4$. Hence ${\chi }_{as}^{\prime }(S^{\prime }(P_3))=4$.

For $n\ge 4$, since $\mathrm{\Delta }(S^{\prime }(P_n))=4$, by Observation 1.1, ${\chi }_{as}^{\prime }(S^{\prime }(P_n))\ge 5$. To show ${\chi }_{as}^{\prime }(S^{\prime }(P_n))\le 5$, we define $\sigma :E(S^{\prime }(P_n))\to \{1,2,3,4,5\}$ as follows:

Therefore, $\sigma$ is a proper edge-coloring. It remains to show that $\sigma$ is an AVD proper edge-coloring. We compare the sets of colors of adjacent vertices of the same degree.

The induced vertex-color sets are as follows:

Observe that $\sigma$ is an AVD proper edge-coloring of $S^{\prime }(P_n)$. Hence ${\chi }_{as}^{\prime }(S^{\prime }(P_n))=5$. □

Theorem 2.4. ${\chi }_{as}^{\prime }(S^{\prime }(C_n))=5$ for $n\ge 4$.

Proof. Let $C_n=x_1{x}_2\dots x_n{x}_1$, for $n\ge 4$, and $x_1^{\prime },x_2^{\prime },\dots ,x_n^{\prime }$ be the newly added vertices corresponding to the vertices $x_1,x_2,\dots ,x_n$ to form $S^{\prime }(C_n)$. In $S^{\prime }(C_n)$, for $i\in \{1,2,\dots ,n\}$, let $e_i=x_i{x}_{i+1}$, $f_i=x_i^{\prime }{x}_{i+1}$ and $g_i=x_{i+1}^{\prime }{x}_i$, where $x_{n+1}=x_1$ and $x_{n+1}^{\prime }=x_1^{\prime }$.

For $n\ge 4$, since $\mathrm{\Delta }(S^{\prime }(C_n))=4$, by Observation 1.1, ${\chi }_{as}^{\prime }(S^{\prime }(C_n))\ge 5$. To show ${\chi }_{as}^{\prime }(S^{\prime }(C_n))\le 5$, we consider three cases and in each case, we first define $\sigma :E(S^{\prime }(C_n))\to \{1,2,3,4,5\}$ as follows:

Case 1. If $n\equiv 0\mathrm{\text{mod}}3$,

Therefore, $\sigma$ is a proper edge-coloring. It remains to show that $\sigma$ is an AVD proper edge-coloring. We compare the sets of colors of adjacent vertices of the same degree.

The induced vertex-color sets are as follows:

Observe that $\sigma$ is an AVD proper edge-coloring of $S^{\prime }(C_n)$. Hence ${\chi }_{as}^{\prime }(S^{\prime }(C_n))=5$.

Case 2. If $n\equiv 1\mathrm{\text{mod}}3$,

Therefore, $\sigma$ is a proper edge-coloring. It remains to show that $\sigma$ is an AVD proper edge-coloring. We compare the sets of colors of adjacent vertices of the same degree.

The induced vertex-color sets are as follows:

Observe that $\sigma$ is an AVD proper edge-coloring of $S^{\prime }(C_n)$. Hence ${\chi }_{as}^{\prime }(S^{\prime }(C_n))=5$.

Case 3. If $n\equiv 2\mathrm{\text{mod}}3$,

Therefore, $\sigma$ is a proper edge-coloring. It remains to show that $\sigma$ is an AVD proper edge-coloring. We compare the sets of colors of adjacent vertices of the same degree.

The induced vertex-color sets are as follows:

Observe that $\sigma$ is an AVD proper edge-coloring of $S^{\prime }(C_n)$. Hence ${\chi }_{as}^{\prime }(S^{\prime }(C_n))=5$. □

2.3. AVD proper edge-chromatic index of shadow graph of path and cycle

The shadow graph $D_2(G)$ of a connected graph $G$ is constructed by taking two copies of $G$ say $G^{\prime }$ and $G^{\prime \prime }$ and joining each vertex $u^{\prime }$ in $G^{\prime }$ to neighbors of the corresponding vertex $u^{\prime \prime }$ in $G^{\prime \prime }$.

Theorem 2.5.

Proof. Let $P_n=x_1{x}_2\dots x_n$ and $x_1^{\prime },x_2^{\prime },\dots ,x_n^{\prime }$ be the newly added vertices corresponding to the vertices $x_1,x_2,\dots ,x_n$ to form $D_2(P_n)$. In $D_2(P_n)$, for $i\in \{1,2,\dots ,n-1\}$ let $e_i=x_i{x}_{i+1}$, $f_i=x_i^{\prime }{x}_{i+1}$, $g_i=x_{i+1}^{\prime }{x}_i$ and $h_i=x_i^{\prime }{x}_{i+1}^{\prime }$.

Since $D_2(P_2)\cong C_4$ and ${\chi }_{as}^{\prime }(C_4)=4$, then ${\chi }_{as}^{\prime }(D_2(P_2))=4$.

Define $\sigma :E(D_2(P_3))\to \{1,2,3,4\}$ as follows: $\sigma (e_1)=1=\sigma (h_1)$, $\sigma (e_2)=4=\sigma (h_2)$, $\sigma (f_1)=2=\sigma (g_1)$ and $\sigma (f_2)=3=\sigma (g_2)$. Therefore, $\sigma$ is a proper edge-coloring. The induced vertex-color sets are: $S_{\sigma }(x_1)=\{1,2\}=S_{\sigma }(x_1^{\prime })$, $S_{\sigma }(x_2)=\{1,2,3,4\}=S_{\sigma }(x_2^{\prime })$ and $S_{\sigma }(x_3)=\{3,4\}=S_{\sigma }(x_3^{\prime })$. Therefore, $\sigma$ is an AVD proper edge-coloring of $D_2(P_3)$. By Observation 1.1, ${\chi }_{as}^{\prime }(D_2(P_3))\ge 4$, and so ${\chi }_{as}^{\prime }(D_2(P_3))=4$. Hence ${\chi }_{as}^{\prime }(D_2(P_3))=4$.

For $n\ge 4$, since $\mathrm{\Delta }(D_2(P_n))=4$, by Observation 1.1, ${\chi }_{as}^{\prime }(D_2(P_n))\ge 5$. To show ${\chi }_{as}^{\prime }(D_2(P_n))\le 5$, we define $\sigma :E(D_2(P_n))\to \{1,2,3,4,5\}$ as follows:

Therefore, $\sigma$ is a proper edge-coloring. It remains to show that $\sigma$ is an AVD proper edge-coloring. We compare the sets of colors of adjacent vertices of the same degree.

The induced vertex-color sets are as follows:

Observe that $\sigma$ is an AVD proper edge-coloring of $D_2(P_n)$. Hence ${\chi }_{as}^{\prime }(D_2(P_n))=5$. □

Theorem 2.6.

Proof. Let $C_n=x_1{x}_2\dots x_n{x}_1$ and $x_1^{\prime },x_2^{\prime },\dots ,x_n^{\prime }$ be the newly added vertices corresponding to the vertices $x_1,x_2,\dots ,x_n$ to form $D_2(C_n)$. In $D_2(C_n)$, for $i\in \{1,2,\dots ,n\}$, let $e_i=x_i{x}_{i+1}$, $f_i=x_i^{\prime }{x}_{i+1}$, $g_i=x_{i+1}^{\prime }{x}_i$ and $h_i=x_i^{\prime }{x}_{i+1}^{\prime }$, where $x_{n+1}^{\prime }=x_1^{\prime }$ and $x_{n+1}=x_1$.

For $n=7$, we define $\sigma :E(D_2(C_7))\to \{1,2,3,4,5,6\}$ as follows: $\sigma (e_1)=\sigma (e_4)=\sigma (h_1)=\sigma (h_4)=1$, $\sigma (e_2)=\sigma (e_5)=\sigma (h_2)=\sigma (h_5)=4$, $\sigma (e_3)=\sigma (e_6)=\sigma (h_3)=\sigma (h_6)=5$, $\sigma (e_7)=6=\sigma (h_7)$, $\sigma (f_1)=\sigma (f_3)=\sigma (f_5)=\sigma (g_1)=\sigma (g_3)=\sigma (g_5)=2$, $\sigma (f_2)=\sigma (f_4)=\sigma (f_6)=\sigma (g_2)=\sigma (g_4)=\sigma (g_6)=3$ and $\sigma (f_7)=4=\sigma (g_7)$ Therefore, $\sigma$ is a proper edge-coloring. The induced vertex-color sets are:

$S_{\sigma }(x_1)=\{1,2,4,6\}=S_{\sigma }(x_1^{\prime })$, $S_{\sigma }(x_2)=S_{\sigma }(x_5)=S_{\sigma }(x_2^{\prime })=S_{\sigma }(x_5^{\prime })=\{1,2,3,4\}$, $S_{\sigma }(x_3)=S_{\sigma }(x_6)=S_{\sigma }(x_3^{\prime })=S_{\sigma }(x_6^{\prime })=\{2,3,4,5\}$, $S_{\sigma }(x_4)=\{1,2,3,5\}=S_{\sigma }(x_4^{\prime })\mathrm{\text{ and }}{S}_{\sigma }(x_7)=\{3,4,5,6\}=S_{\sigma }(x_7^{\prime })$. Therefore, $\sigma$ is an AVD proper edge-coloring of $D_2(C_7)$. By Observation 1.1, ${\chi }_{as}^{\prime }(D_2(C_7))\ge 6,$ and so ${\chi }_{as}^{\prime }(D_2(C_7))=6$. Hence ${\chi }_{as}^{\prime }(D_2(C_7))=6$.

For $n\ge 5$ and $n\ne 7$, since $\mathrm{\Delta }(D_2(C_n))=4$, by Observation 1.1, ${\chi }_{as}^{\prime }(D_2(C_n))\ge 5$. To show ${\chi }_{as}^{\prime }(D_2(C_n))\le 5$, we consider five cases and in each case, we first define $\sigma :E(D_2(C_n))\to \{1,2,3,4,5\}$ as follows:

Case 1. For $n\equiv 0\mathrm{\text{mod}}3$,

Therefore, $\sigma$ is a proper edge-coloring. It remains to show that $\sigma$ is an AVD proper edge-coloring. We compare the sets of colors of adjacent vertices of the same degree.

The induced vertex-color sets are as follows:

Observe that $\sigma$ is an AVD proper edge-coloring of $D_2(C_n)$. Hence ${\chi }_{as}^{\prime }(D_2(C_n))=5$.

Case 2. For $n\equiv 5\mathrm{\text{mod}}6$,

Therefore, $\sigma$ is a proper edge-coloring. It remains to show that $\sigma$ is an AVD proper edge-coloring. We compare the sets of colors of adjacent vertices of the same degree.

The induced vertex-color sets are as follows:

Observe that $\sigma$ is an AVD proper edge-coloring of $D_2(C_n)$. Hence ${\chi }_{as}^{\prime }(D_2(C_n))=5$.

Case 3. For $n\equiv 1\mathrm{\text{mod}}6$ and $n\ge 13$,

Therefore, $\sigma$ is a proper edge-coloring. It remains to show that $\sigma$ is an AVD proper edge-coloring. We compare the sets of colors of adjacent vertices of the same degree.

The induced vertex-color sets are as follows:

Observe that $\sigma$ is an AVD proper edge-coloring of $D_2(C_n)$. Hence ${\chi }_{as}^{\prime }(D_2(C_n))=5$.

Case 4. For $n\equiv 2\mathrm{\text{mod}}6$,

Therefore, $\sigma$ is a proper edge-coloring. It remains to show that $\sigma$ is an AVD proper edge-coloring. We compare the sets of colors of adjacent vertices of the same degree.

The induced vertex-color sets are as follows:

Observe that $\sigma$ is an AVD proper edge-coloring of $D_2(C_n)$. Hence ${\chi }_{as}^{\prime }(D_2(C_n))=5$.

Case 5. For $n\equiv 4\mathrm{\text{mod}}6$,

Therefore, $\sigma$ is a proper edge-coloring. It remains to show that $\sigma$ is an AVD proper edge-coloring. We compare the sets of colors of adjacent vertices of the same degree.

The induced vertex-color sets are as follows:

Observe that $\sigma$ is an AVD proper edge-coloring of $D_2(C_n)$. Hence ${\chi }_{as}^{\prime }(D_2(C_n))=5$. □

3. AVD Proper Edge-Chromatic Index of Triangular Grid $T_n$ Graph

In this section, the AVD proper edge-coloring of triangular grid $T_n$ is discussed.

The triangular grid graph $T_n$ is the graph on vertices $(i,j,k)$ with $i,j$ and $k$ being nonnegative integers summing to $n$ such that the vertices are adjacent if the sum of absolute differences of the coordinates of two vertices is 2.¹⁰

Theorem 3.1.

Proof. Let $T_l$, for $l\ge 3$, be the triangular grid with vertices of $T_l$ on $l$ levels as $x_j^i$ for $i\in \{1,2,\dots ,l\}$, $j\in \{1,2,\dots ,l\}$.

We define $\sigma :E(T_3)\to \{1,2,3,4,5\}$ as follows: $\sigma (x_1^1{x}_1^2)=2$, $\sigma (x_1^1{x}_2^2)=3$, $\sigma (x_1^2{x}_1^3)=4$, $\sigma (x_2^2{x}_2^3)=4$, $\sigma (x_1^2{x}_2^3)=5$, $\sigma (x_2^2{x}_3^3)=5$, $\sigma (x_1^2{x}_2^2)=1$, $\sigma (x_1^3{x}_2^3)=2$ and $\sigma (x_2^3{x}_3^3)=3$. Therefore, $\sigma$ is a proper edge-coloring. The induced vertex-color sets are: $S_{\sigma }(x_1^1)=\{2,3\},S_{\sigma }(x_1^2)=\{1,2,4,5\}$, $S_{\sigma }(x_2^2)=\{1,3,4,5\},S_{\sigma }(x_1^3)=\{2,4\}$, $S_{\sigma }(x_2^3)=\{2,3,4,5\}$ and $S_{\sigma }(x_3^3)=\{3,5\}$. Hence, $\sigma$ is an AVD proper edge-coloring of $T_l$. By Observation 1.1, ${\chi }_{as}^{\prime }(T_3)\ge 5$, and so ${\chi }_{as}^{\prime }(T_3)=5$. Hence ${\chi }_{as}^{\prime }(T_3)=5$. We define $\sigma :E(T_4)\to \{1,2,3,4,5,6\}$ as follows: $\sigma (x_1^1{x}_1^2)=2$, $\sigma (x_1^1{x}_2^2)=3$, $\sigma (x_1^2{x}_1^3)=4$, $\sigma (x_2^2{x}_2^3)=4$, $\sigma (x_1^2{x}_2^3)=5$, $\sigma (x_2^2{x}_3^3)=5$, $\sigma (x_1^3{x}_1^4)=\sigma (x_2^3{x}_2^4)=\sigma (x_3^3{x}_3^4)=2$, $\sigma (x_1^3{x}_2^4)=\sigma (x_2^3{x}_3^4)=\sigma (x_3^3{x}_4^4)=3$, $\sigma (x_1^2{x}_2^2)=1$, $\sigma (x_1^3{x}_2^3)=1$, $\sigma (x_2^3{x}_3^3)=6$, $\sigma (x_1^4{x}_2^4)=4$, $\sigma (x_2^4{x}_3^4)=5$ and $\sigma (x_3^4{x}_4^4)=6$. Therefore, $\sigma$ is a proper edge-coloring. The induced vertex-color sets are: $S_{\sigma }(x_1^1)=\{2,3\},S_{\sigma }(x_1^2)=\{1,2,4,5\}$, $S_{\sigma }(x_2^2)=\{1,3,4,5\}$, $S_{\sigma }(x_1^3)=\{1,2,3,4\}$, $S_{\sigma }(x_2^3)=\{1,2,3,4,5,6\}$, $S_{\sigma }(x_3^3)=\{2,3,5,6\}$, $S_{\sigma }(x_1^4)=\{2,6\}$, $S_{\sigma }(x_2^4)=\{2,3,4,6\}$, $S_{\sigma }(x_3^4)=\{2,3,4,5\}$ and $S_{\sigma }(x_4^4)=\{3,5\}$ Therefore, $\sigma$ is an AVD proper edge-coloring of $T_l$. As $\mathrm{\Delta }({\chi }_{as}^{\prime }(T_4))=6$, by Observation 1.2, ${\chi }_{as}^{\prime }(T_4)=6$.

For $l\ge 5$, since $\mathrm{\Delta }(T_l)=6$, by Observation 1.1, ${\chi }_{as}^{\prime }(T_l)\ge 7$. To show ${\chi }_{as}^{\prime }(T_l)\le 7$, we define $\sigma :E(T_l)\to \{1,2,3,4,5,6,7\}$ as follows :

For $i\in \{4,5,6,\dots ,l-1\}$, $j\in \{1,2,3,\dots ,i-1\}$,

$$\begin{array}{l}\mathrm{\text{for}}i\equiv 1\mathrm{\text{mod}}3,\sigma (x_j^i{x}_{j+1}^i)=\left\{\begin{array}{cc}1\hfill & \mathrm{\text{if}}j\equiv 1\mathrm{\text{mod}}3,\hfill \\ 7\hfill & \mathrm{\text{if}}j\equiv 2\mathrm{\text{mod}}3,\hfill \\ 6\hfill & \mathrm{\text{if}}j\equiv 0\mathrm{\text{mod}}3;\hfill \end{array}\right.\\ \mathrm{\text{for}}i\equiv 2\mathrm{\text{mod}}3,\sigma (x_j^i{x}_{j+1}^i)=\left\{\begin{array}{cc}7\hfill & \mathrm{\text{if}}j\equiv 1\mathrm{\text{mod}}3,\hfill \\ 6\hfill & \mathrm{\text{if}}j\equiv 2\mathrm{\text{mod}}3,\hfill \\ 1\hfill & \mathrm{\text{if}}j\equiv 0\mathrm{\text{mod}}3;\hfill \end{array}\right.\\ \mathrm{\text{for}}i\equiv 0\mathrm{\text{mod}}3,\sigma (x_j^i{x}_{j+1}^i)=\left\{\begin{array}{cc}6\hfill & \mathrm{\text{if}}j\equiv 1\mathrm{\text{mod}}3,\hfill \\ 1\hfill & \mathrm{\text{if}}j\equiv 2\mathrm{\text{mod}}3,\hfill \\ 7\hfill & \mathrm{\text{if}}j\equiv 0\mathrm{\text{mod}}3.\hfill \end{array}\right.\end{array}$$

If $l\equiv 5\mathrm{\text{mod}}6$, $l\equiv 1\mathrm{\text{mod}}6$ and $l\equiv 3\mathrm{\text{mod}}6$,

$$\begin{array}{l}\mathrm{\text{for}}i\in \{1,3,5,\dots ,l-2\},\sigma (x_j^i{x}_j^{i+1})=2\\ \mathrm{\text{if}}j\in \{1,2,\dots ,i\};\\ \mathrm{\text{for}}i\in \{1,3,5,\dots ,l-2\},\sigma (x_j^i{x}_{j+1}^{i+1})=3\\ \mathrm{\text{if}}j\in \{1,2,\dots ,i\};\\ \mathrm{\text{for}}i\in \{2,4,6,\dots ,l-1\},\sigma (x_j^i{x}_j^{i+1})=4\\ \mathrm{\text{if}}j\in \{1,2,\dots ,i\};\\ \mathrm{\text{for}}i\in \{2,4,6,\dots ,l-1\},\sigma (x_j^i{x}_{j+1}^{i+1})=5\\ \mathrm{\text{if}}j\in \{1,2,\dots ,i\}.\end{array}$$

If $l\equiv 0\mathrm{\text{mod}}6$, $l\equiv 2\mathrm{\text{mod}}6$ and $l\equiv 4\mathrm{\text{mod}}6$,

$$\begin{array}{l}\mathrm{\text{for}}i\in \{1,3,5,\dots ,l-1\},\sigma (x_j^i{x}_j^{i+1})=2\\ \mathrm{\text{if}}j\in \{1,2,\dots ,i\};\\ \mathrm{\text{for}}i\in \{1,3,5,\dots ,l-1\},\sigma (x_j^i{x}_{j+1}^{i+1})=3\\ \mathrm{\text{if}}j\in \{1,2,\dots ,i\};\\ \mathrm{\text{for}}i\in \{2,4,6,\dots ,l-2\},\sigma (x_j^i{x}_j^{i+1})=4\\ \mathrm{\text{if}}j\in \{1,2,\dots ,i\};\\ \mathrm{\text{for}}i\in \{2,4,6,\dots ,l-2\},\sigma (x_j^i{x}_{j+1}^{i+1})=5\\ \mathrm{\text{if}}j\in \{1,2,\dots ,i\}.\end{array}$$

For $j\in \{1,2,3,\dots ,l-1\}$

$$\begin{array}{l}\mathrm{\text{for}}l\equiv 5\mathrm{\text{mod}}6,l\equiv 1\mathrm{\text{mod}}6\mathrm{\text{and}}l\equiv 3\mathrm{\text{mod}}6,\\ \sigma (x_j^l{x}_{j+1}^l)=\left\{\begin{array}{cc}2\hfill & \mathrm{\text{if}}j\equiv 1\mathrm{\text{mod}}3,\hfill \\ 3\hfill & \mathrm{\text{if}}j\equiv 2\mathrm{\text{mod}}3,\hfill \\ 6\hfill & \mathrm{\text{if}}j\equiv 0\mathrm{\text{mod}}3;\hfill \end{array}\right.\\ \mathrm{\text{for}}l\equiv 0\mathrm{\text{mod}}6,l\equiv 2\mathrm{\text{mod}}6\mathrm{\text{and}}l\equiv 4\mathrm{\text{mod}}6,\\ \sigma (x_j^l{x}_{j+1}^l)=\left\{\begin{array}{cc}4\hfill & \mathrm{\text{if}}j\equiv 1\mathrm{\text{mod}}3,\hfill \\ 5\hfill & \mathrm{\text{if}}j\equiv 2\mathrm{\text{mod}}3,\hfill \\ 6\hfill & \mathrm{\text{if}}j\equiv 0\mathrm{\text{mod}}3.\hfill \end{array}\right.\end{array}$$

Therefore, $\sigma$ is a proper edge-coloring. It remains to show that $\sigma$ is an AVD proper edge-coloring. We compare the sets of colors of adjacent vertices of the same degree.

The induced vertex-color sets are as follows:

For $i\in \{5,6,\dots ,l-1\}$, $j\in \{2,3,\dots ,i-1\}$,

$$\begin{array}{l}\mathrm{\text{for}}i\equiv 5\mathrm{\text{mod}}6,S_{\sigma }(x_1^i)=\{2,3,4,7\},\\ S_{\sigma }(x_j^i)=\left\{\begin{array}{cc}\{2,3,4,5,6,7\}\hfill & \mathrm{\text{if}}j\equiv 2\mathrm{\text{mod}}3,\hfill \\ \{1,2,3,4,5,6\}\hfill & \mathrm{\text{if}}j\equiv 0\mathrm{\text{mod}}3,\hfill \\ \{1,2,3,4,5,7\}\hfill & \mathrm{\text{if}}j\equiv 1\mathrm{\text{mod}}3,\hfill \end{array}\right.\\ S_{\sigma }(x_i^i)=\{2,3,5,7\};\\ \mathrm{\text{for}}i\equiv 0\mathrm{\text{mod}}6,S_{\sigma }(x_1^i)=\{2,4,5,6\},\\ S_{\sigma }(x_j^i)=\left\{\begin{array}{cc}\{1,2,3,4,5,6\}\hfill & \mathrm{\text{if}}j\equiv 2\mathrm{\text{mod}}3,\hfill \\ \{1,2,3,4,5,7\}\hfill & \mathrm{\text{if}}j\equiv 0\mathrm{\text{mod}}3,\hfill \\ \{2,3,4,5,6,7\}\hfill & \mathrm{\text{if}}j\equiv 1\mathrm{\text{mod}}3,\hfill \end{array}\right.\\ S_{\sigma }(x_i^i)=\{1,3,4,5\};\\ \mathrm{\text{for}}i\equiv 1\mathrm{\text{mod}}6,S_{\sigma }(x_1^i)=\{1,2,3,4\},\\ S_{\sigma }(x_j^i)=\left\{\begin{array}{cc}\{1,2,3,4,5,7\}\hfill & \mathrm{\text{if}}j\equiv 2\mathrm{\text{ mod }}3,\hfill \\ \{2,3,4,5,6,7\}\hfill & \mathrm{\text{if}}j\equiv 0\mathrm{\text{mod}}3,\hfill \\ \{1,2,3,4,5,6\}\hfill & \mathrm{\text{if}}j\equiv 1\mathrm{\text{mod}}3,\hfill \end{array}\right.\\ S_{\sigma }(x_i^i)=\{2,3,5,6\};\\ \mathrm{\text{for}}i\equiv 2\mathrm{\text{mod}}6,S_{\sigma }(x_1^i)=\{2,4,5,7\},\\ S_{\sigma }(x_j^i)=\left\{\begin{array}{cc}\{2,3,4,5,6,7\}\hfill & \mathrm{\text{if}}j\equiv 2\mathrm{\text{mod}}3,\hfill \\ \{1,2,3,4,5,6\}\hfill & \mathrm{\text{if}}j\equiv 0\mathrm{\text{mod}}3,\hfill \\ \{1,2,3,4,5,7\}\hfill & \mathrm{\text{if}}j\equiv 1\mathrm{\text{mod}}3,\hfill \end{array}\right.\\ S_{\sigma }(x_i^i)=\{3,4,5,7\};\\ \mathrm{\text{for}}i\equiv 3\mathrm{\text{mod}}6,S_{\sigma }(x_1^i)=\{2,3,4,6\},\\ S_{\sigma }(x_j^i)=\left\{\begin{array}{cc}\{1,2,3,4,5,6\}\hfill & \mathrm{\text{if}}j\equiv 2\mathrm{\text{mod}}3,\hfill \\ \{1,2,3,4,5,7\}\hfill & \mathrm{\text{if}}j\equiv 0\mathrm{\text{mod}}3,\hfill \\ \{2,3,4,5,6,7\}\hfill & \mathrm{\text{if}}j\equiv 1\mathrm{\text{mod}}3,\hfill \end{array}\right.\\ S_{\sigma }(x_i^i)=\{1,2,3,5\};\\ \mathrm{\text{for}}i\equiv 4\mathrm{\text{mod}}6,S_{\sigma }(x_1^i)=\{1,2,4,5\},\\ S_{\sigma }(x_j^i)=\left\{\begin{array}{cc}\{1,2,3,4,5,7\}\hfill & \mathrm{\text{if}}j\equiv 2\mathrm{\text{mod}}3,\hfill \\ \{2,3,4,5,6,7\}\hfill & \mathrm{\text{if}}j\equiv 0\mathrm{\text{mod}}3,\hfill \\ \{1,2,3,4,5,6\}\hfill & \mathrm{\text{if}}j\equiv 1\mathrm{\text{mod}}3,\hfill \end{array}\right.\\ S_{\sigma }(x_i^i)=\{3,4,5,6\}.\end{array}$$

For $j\in \{2,3,\dots ,l-1\}$,

$$\begin{array}{l}\mathrm{\text{for}}l\equiv 5\mathrm{\text{mod}}6,S_{\sigma }(x_1^l)=\{2,4\},\\ S_{\sigma }(x_j^l)=\left\{\begin{array}{cc}\{2,3,4,5\}\hfill & \mathrm{\text{if}}j\equiv 2\mathrm{\text{mod}}3,\hfill \\ \{3,4,5,6\}\hfill & \mathrm{\text{if}}j\equiv 0\mathrm{\text{mod}}3,\hfill \\ \{2,4,5,6\}\hfill & \mathrm{\text{if}}j\equiv 1\mathrm{\text{mod}}3,\hfill \end{array}\right.\\ S_{\sigma }(x_l^l)=\{2,5\};\\ \mathrm{\text{for}}l\equiv 0\mathrm{\text{mod}}6,S_{\sigma }(x_1^l)=\{2,4\},\\ S_{\sigma }(x_j^l)=\left\{\begin{array}{cc}\{2,3,4,5\}\hfill & \mathrm{\text{if}}j\equiv 2\mathrm{\text{mod}}3,\hfill \\ \{2,3,5,6\}\hfill & \mathrm{\text{if}}j\equiv 0\mathrm{\text{mod}}3,\hfill \\ \{2,3,4,6\}\hfill & \mathrm{\text{if}}j\equiv 1\mathrm{\text{mod}}3,\hfill \end{array}\right.\\ S_{\sigma }(x_l^l)=\{3,5\};\\ \mathrm{\text{for}}l\equiv 1\mathrm{\text{mod}}6,S_{\sigma }(x_1^l)=\{2,4\},\\ S_{\sigma }(x_j^l)=\left\{\begin{array}{cc}\{2,3,4,5\}\hfill & \mathrm{\text{if}}j\equiv 2\mathrm{\text{mod}}3,\hfill \\ \{3,4,5,6\}\hfill & \mathrm{\text{if}}j\equiv 0\mathrm{\text{mod}}3,\hfill \\ \{2,4,5,6\}\hfill & \mathrm{\text{if}}j\equiv 1\mathrm{\text{mod}}3,\hfill \end{array}\right.\\ S_{\sigma }(x_l^l)=\{5,6\};\\ \mathrm{\text{for}}l\equiv 2\mathrm{\text{mod}}6,S_{\sigma }(x_1^l)=\{2,4\},\\ S_{\sigma }(x_j^l)=\left\{\begin{array}{cc}\{2,3,4,5\}\hfill & \mathrm{\text{if}}j\equiv 2\mathrm{\text{mod}}3,\hfill \\ \{2,3,5,6\}\hfill & \mathrm{\text{if}}j\equiv 0\mathrm{\text{mod}}3,\hfill \\ \{2,3,4,6\}\hfill & \mathrm{\text{if}}j\equiv 1\mathrm{\text{mod}}3,\hfill \end{array}\right.\\ S_{\sigma }(x_l^l)=\{3,4\};\\ \mathrm{\text{for}}l\equiv 3\mathrm{\text{mod}}6,S_{\sigma }(x_1^l)=\{2,4\},\\ S_{\sigma }(x_j^l)=\left\{\begin{array}{cc}\{2,3,4,5\}\hfill & \mathrm{\text{if}}j\equiv 2\mathrm{\text{mod}}3,\hfill \\ \{3,4,5,6\}\hfill & \mathrm{\text{if}}j\equiv 0\mathrm{\text{mod}}3,\hfill \\ \{2,4,5,6\}\hfill & \mathrm{\text{if}}j\equiv 1\mathrm{\text{mod}}3,\hfill \end{array}\right.\\ S_{\sigma }(x_l^l)=\{3,5\};\\ \mathrm{\text{for}}l\equiv 4\mathrm{\text{mod}}6,S_{\sigma }(x_1^l)=\{2,4\},\\ S_{\sigma }(x_j^l)=\left\{\begin{array}{cc}\{2,3,4,5\}\hfill & \mathrm{\text{if}}j\equiv 2\mathrm{\text{mod}}3,\hfill \\ \{2,3,5,6\}\hfill & \mathrm{\text{if}}j\equiv 0\mathrm{\text{mod}}3,\hfill \\ \{2,3,4,6\}\hfill & \mathrm{\text{if}}j\equiv 1\mathrm{\text{mod}}3,\hfill \end{array}\right.\\ S_{\sigma }(x_l^l)=\{3,6\}.\end{array}$$

Observe that $\sigma$ is an AVD proper edge-coloring of $T_l$. Hence ${\chi }_{as}^{\prime }(T_l)=7$. □

4. AVD Proper Edge-Chromatic Index of $H$-Graph

In this section, AVD proper edge-coloring of $H$-graph will be discussed.¹¹

The $H$-graph $H(r)$, $r\ge 2$, is the 3-regular graph of order $6r$, with the vertex set

and edge set (subscripts are taken modulo $2r)$

$$\begin{array}{l}E(H(r))=\{(x_i,x_{i+1}),(z_i,z_{i+1}),(x_i,y_i),(y_i,z_i):0\le i\\ \le 2r-1\}\cup \{(y_{2i},y_{2i+1}):0\le i\le r-1\}.\end{array}$$

Proposition 4.1. ${\chi }_{as}^{\prime }(H(2))=4$.

Proof. We define $\sigma :E(H(2))\to \{1,2,3,4\}$ as follows:

Therefore, $\sigma$ is a proper edge-coloring. It remains to show that $\sigma$ is an AVD proper edge-coloring. We compare the sets of colors of adjacent vertices of the same degree.

The induced vertex-color sets are as follows:

Observe that $\sigma$ is an AVD proper edge-coloring of $H(2)$. Hence ${\chi }_{as}^{\prime }(H(2))=4$. □

Proposition 4.2. ${\chi }_{as}^{\prime }(H(3))=4$.

Proof. We define $\sigma :E(H(3))\to \{1,2,3,4\}$ as follows:

Therefore, $\sigma$ is a proper edge-coloring. It remains to show that $\sigma$ is an AVD proper edge-coloring. We compare the sets of colors of adjacent vertices of the same degree.

The induced vertex-color sets are as follows:

Observe that $\sigma$ is an AVD proper edge-coloring of $H(3)$. Hence ${\chi }_{as}^{\prime }(H(3))=4$. □

Theorem 4.1. ${\chi }_{as}^{\prime }(H(r))=4forr\ge 4$.

Proof. Since $\mathrm{\Delta }(H(r))=3$, by Observation 1.1, ${\chi }_{as}^{\prime }(H(r))\ge 4$. To show ${\chi }_{as}^{\prime }(H(r))\le 4$, we consider two cases and in each case, we define $\sigma :E(H(r))\to \{1,2,3,4\}$ as follows:

Case 1. If $r$ is even,

Therefore, $\sigma$ is a proper edge-coloring. It remains to show that $\sigma$ is an AVD proper edge-coloring. We compare the sets of colors of adjacent vertices of the same degree.

The induced vertex-color sets are as follows:

Observe that $\sigma$ is an AVD proper edge-coloring of $H(r)$. Hence ${\chi }_{as}^{\prime }(H(r))=4$.

Case 2. If $r$ is odd,

Therefore, $\sigma$ is a proper edge-coloring. It remains to show that $\sigma$ is an AVD proper edge-coloring. We compare the sets of colors of adjacent vertices of the same degree.

The induced vertex-color sets are as follows:

Observe that $\sigma$ is an AVD proper edge-coloring of $H(r)$. Hence ${\chi }_{as}^{\prime }(H(r))=4$. □

4.1. Generalized $H$-graphs

We now consider a natural extension of $H$-graphs. For every integer $r\ge 2$, the generalized $H$-graph $H^l(r)$ with $l$ levels, $l\ge 1$, is the 3-regular graph of order $2r(l+2)$, with the vertex set

and edge set (subscripts are taken modulo 2$r$)

$$\begin{array}{l}E(H^l(r))=\{{(x}_j^0,x_{j+1}^0),(x_j^{l+1},x_{j+1}^{l+1}):0\le j\le 2r-1\}\\ \cup \{{(x}_{2j}^i{x}_{2j+1}^i):1\le i\le l,0\le j\le r-1\}\\ \cup \{{(x}_j^i,x_j^{i+1}):0\le i\le l,0\le j\le 2r-1\}.\end{array}$$

Theorem 4.2. ${\chi }_{as}^{\prime }(H^l(r))=5$ for $r\ge 3$ and $l\ge 2$.

Proof. We define $\sigma :E(H^l(r))\to \{1,2,3,4,5\}$ as follows:

If $\sigma (x_j^0{x}_j^1)=\{\begin{array}{cc}4\hfill & \mathrm{\text{if}}j\mathrm{\text{is odd}}\hfill \\ 2\hfill & \mathrm{\text{if}}j\mathrm{\text{is even}}\hfill \end{array}$, for $i\in \{1,2,\dots ,l\}$,

$$\begin{array}{l}\mathrm{\text{for}}i\equiv 1\mathrm{\text{mod}}3,\sigma (x_j^i{x}_j^{i+1})=\left\{\begin{array}{cc}2\hfill & \mathrm{\text{if}}j\mathrm{\text{is odd}},\hfill \\ 5\hfill & \mathrm{\text{if}}j\mathrm{\text{is even}};\hfill \end{array}\right.\\ \mathrm{\text{for}}i\equiv 2\mathrm{\text{mod}}3,\sigma (x_j^i{x}_j^{i+1})=\left\{\begin{array}{cc}5\hfill & \mathrm{\text{if}}j\mathrm{\text{is odd}},\hfill \\ 3\hfill & \mathrm{\text{if}}j\mathrm{\text{is even}};\hfill \end{array}\right.\\ \mathrm{\text{for}}i\equiv 0\mathrm{\text{mod}}3,\sigma (x_j^i{x}_j^{i+1})=\left\{\begin{array}{cc}3\hfill & \mathrm{\text{if}}j\mathrm{\text{is odd}},\hfill \\ 2\hfill & \mathrm{\text{if}}j\mathrm{\text{is even}}.\hfill \end{array}\right.\end{array}$$

For $j\in \{1,2,\dots ,2r-1\}$,

Therefore, $\sigma$ is a proper edge-coloring. It remains to show that $\sigma$ is an AVD proper edge-coloring. We compare the sets of colors of adjacent vertices of the same degree.

The induced vertex-color sets are as follows :

For $i\in \{1,2,\dots ,l\}$, $j\in \{1,2,\dots ,2r\}$,

$$\begin{array}{l}\mathrm{\text{for}}i=1,S_{\sigma }(x_j^i)=\left\{\begin{array}{cc}\{1,2,4\}\hfill & \mathrm{\text{if}}j\mathrm{\text{is odd}},\hfill \\ \{1,2,5\}\hfill & \mathrm{\text{if}}j\mathrm{\text{is even}};\hfill \end{array}\right.\\ \mathrm{\text{for}}i\equiv 2\mathrm{\text{mod}}3,S_{\sigma }(x_j^i)=\left\{\begin{array}{cc}\{1,2,5\}\hfill & \mathrm{\text{if}}j\mathrm{\text{is odd}},\hfill \\ \{1,3,5\}\hfill & \mathrm{\text{if}}j\mathrm{\text{is even}};\hfill \end{array}\right.\\ \mathrm{\text{for}}i\equiv 0\mathrm{\text{mod}}3,S_{\sigma }(x_j^i)=\left\{\begin{array}{cc}\{1,3,5\}\hfill & \mathrm{\text{if}}j\mathrm{\text{is odd}},\hfill \\ \{1,2,3\}\hfill & \mathrm{\text{if}}j\mathrm{\text{is even}};\hfill \end{array}\right.\\ \mathrm{\text{for}}i\equiv 1\mathrm{\text{mod}}3,S_{\sigma }(x_j^i)=\left\{\begin{array}{cc}\{1,2,3\}\hfill & \mathrm{\text{if}}j\mathrm{\text{is odd}},\hfill \\ \{1,2,5\}\hfill & \mathrm{\text{if}}j\mathrm{\text{is even}}.\hfill \end{array}\right.\end{array}$$

For $j\in \{1,2,\dots ,2r\}$, Observe that $\sigma$ is an AVD proper edge-coloring of $H^l(r)$. Hence ${\chi }_{as}^{\prime }(H^l(r))=5$. □

5. Conclusion

In this paper, I investigate the AVD proper edge-chromatic indices of the middle, splitting and shadow graphs of path and cycle, and also I investigated the triangular grid $T_n$, $H$-graph and generalized $H$-graph. To derive similar results for other graph families is an open area of research.

Acknowledgments

The author expresses his sincere thanks to the referee for his/her careful reading and suggestions that helped to improve this paper.