A proper coloring assigns distinct colors to the adjacent vertices of a graph. An equitable near proper coloring of a graph \(G\) is an improper coloring in which neighbouring vertices are allowed to receive the same color such that the cardinalities of two distinct color classes differ by not more than one and the number of monochromatic edges is minimised by giving certain restrictions on the number of color classes that can have an edge between them. This paper discusses the equitable near proper coloring of line, middle, and total graphs of certain graph classes, such as paths, cycles, sunlet graphs, star graphs, and gear graphs.
All graphs considered in this paper are finite, connected, simple, and undirected. For basic terminologies and notations, we refer to [1,10].
Graph coloring is an extensively studied area in graph theory. A proper vertex coloring is an assignment of colors to the vertices of the graph in which neighbouring vertices receive distinct colors. Equitable coloring of graphs was introduced in 1973 (see [9]) and defined as a proper vertex coloring in which the cardinalities of the color classes differ by not more than 1. The least integer value \(k\) for which \(G\) is equitably \(k\) colorable is known as the equitable chromatic number denoted by \(\chi_e(G)\).
An improper coloring or a defective coloring of \(G\) allows the adjacent vertices to receive the same colors. The resulting monochromatic edges are also called bad edges. A near proper coloring of \(G\) is a defective coloring in which the number of bad edges is minimised by restricting the adjacency of elements within the color classes [8]. A defective coloring problem arises when there is a situation that does not have enough resources. When there are insufficient resources to color a graph, near proper coloring plays an essential role in the literature. Motivated by the above studies, the notion of equitable near proper coloring is introduced in [2] and stated as follows.
[2] An equitable near proper coloring (or ENP \(k\)-coloring) of a graph \(G\) is a defective coloring in which the set of vertices of \(G\) can be partitioned into \(k\) color classes \(V_1,V_2,\ldots,V_k\) such that \(||V_i| – |V_j|| \leq 1\) for any \(1 \leq i \neq j \leq k\) and the number of bad edges is minimised by restricting the number of color classes that can have adjacency among their elements.
The minimum number of monochromatic edges or bad edges resulting from an ENP \(k\)-coloring of \(G\) is defined as equitable defective number and is denoted by \(b_{\chi_e}^k(G)\).
In an ENP coloring, the vertex set is partitioned into \(k\) color classes by the integer partitioning of \(n\), the order of the graph such that \(n=a_1+a_2+\ldots+a_k\) where \(|a_i-a_j|\le 1;~ 1 \le i\ne j \le k\) and \(a_i\) is the cardinality of the \(i\)-th color class \(V_i\) of \(G\). When the available number of colors increases, the cardinality of each color class decreases to maintain the equitability constraint. The colors can be suitably assigned to the vertices in such a manner that the number of resulting monochromatic edges is minimum. This coloring technique is used for all graph classes under consideration to get the minimum possible number of monochromatic edges in all cases. Integer partitioning technique is used as the fundamental method in the study to suitably identifying the optimal coloring schema. To ensure the optimality, the equitable integer partitioning technique is followed to decide the cardinality of color classes.
Graphs with equitable chromatic number \(2\) are excluded from this discussion, as coloring a graph with only one color makes all edges monochromatic. Hence, we consider the cases when \(\chi_e(G) \geq 3\).
Throughout the discussion, \(\{c_1, c_2, \ldots, c_k\}\) be the \(k\) available colors, and \(\{V_1, V_2, \ldots, V_k\}\) are the corresponding color classes. In an ENP-coloring, all possible values for \(k\) where \(2 \leq k \leq \chi_e(G)-1\) are considered. The function \(c(v_i)\) represents the color assigned to the vertex \(v_i\). The monochromatic edges resulting from an ENP \(k\)-coloring are represented by dotted lines.
ENP coloring offers a broad scope of research. The studies in this direction can be viewed in [4,3,5].
Let \(G\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\). The line graph of \(G\), denoted by \(L(G)\), is the graph whose vertex set is the edge set of \(G\) with two vertices of \(L(G)\) that are adjacent whenever the corresponding edges of \(G\) are adjacent.
The middle graph of \(G\), denoted by \(M(G)\), is the graph whose vertex set is \(V(G) \cup E(G)\), where two vertices in \(M(G)\) are adjacent if and only if they are either adjacent edges of \(G\) or one is a vertex and the other is an edge incident with it.
The total graph of \(G\), denoted by \(T(G)\), has vertex set \(V(G) \cup E(G)\), and the edges join all elements of this vertex set that are adjacent or incident in \(G\).
This paper discusses the ENP \(k\)-coloring of the line, middle, and total graph of paths, cycles, sunlet graphs, star graphs, and gear graphs and also investigates the corresponding equitable defective number. Throughout the discussion, let \(\{c_1, c_2, \cdots, c_k\}\) be the available colors and \(\{V_1, V_2,\cdots, V_k\}\) be the corresponding color classes. In an ENP \(k\)-coloring, we consider all possible cases for \(k\) where \(1 < k < \chi_e(G)\). The bad edges resulting from an ENP \(k\)-coloring are represented by dotted lines.
The line graph of a path graph of order \(n\) is a path graph of order \(n-1\), and hence the equitable chromatic number is \(2\). In an ENP \(k\)-coloring, we consider only the graphs with \(\chi_e(G) \geq 3\), and thus the line graph of paths is omitted from our study.
The equitable coloring of the middle graph of a path contains three colors. The following theorem describes the ENP \(k\)-coloring of the middle graph of a path graph.
Proof. Consider \(V(P_n)=\{v_1,v_2,\ldots,v_n\}\) and \(E(P_n)=\{e_1,e_2,\ldots,e_{n-1}\}\). Then, \(V((M(P_n))=V(P_n) \cup E(P_n)\). Thus, \(M(P_n)\) contains \(2n-1\) vertices, and observe that \(\chi_e(M(P_n))=3\). In an ENP \(k\)-coloring, only one case \(k=2\) is to be considered.
It is possible to partition the vertex set into two subsets, \(V_1=\{v_1,v_2,\ldots,v_n\}\) and \(V_2=\{e_1,e_2,\ldots,\\ e_{n-1}\}\). Now, assign the vertices in \(V_1\) with the color \(c_1\) and \(V_2\) with the color \(c_2\). Since \(e_i\) \(;\) \(1 \leq i \leq n-1\) forms a path of order \(n-2\), \(b_{\chi_e}^k(M(P_n))=n-2\), as \(n-2\) monochromatic edges are formed among the vertices \(e_i\).
Another possible way of an ENP \(k\)-coloring is defined as follows: \[c(v_i)= \begin{cases} c_1, & \mbox{if}~ i \equiv 1,2 \mathrm{mod} 4; \\ c_2, & \mbox{if}~ i \equiv 0,3 \mathrm{mod} 4. \end{cases}\]
This coloring results in \(n-2\) monochromatic edges of the form \(v_ie_i\) \(;\) \(1 \leq i \leq n-1\) or \(e_iv_j\) \(;\) \(1 \leq i \leq n-1\) \(,\) \(1 \leq j \leq n\). It also yields in \(n-2\) monochromatic edges, and thus \(b_{\chi_e}^k(M(P_n))=n-2\). ◻
Figure 1 depicts an ENP \(2\)-coloring of the middle graph of paths.
The total graph of a path contains \(2n-1\) vertices and \(\chi_e(T(P_n))=3\). The succeeding theorem addresses the ENP \(k\)-coloring of the total graph of paths when \(k=2\).
For a path \(P_n\) where \(n \geq 3\), \(b_{\chi_e}^2(T(P_n))=n-1\).
Proof. Let \(V((T(P_n))=\{v_1,v_2,\ldots,v_n,e_1,e_2,\ldots,e_{n-1}\}\), and in an ENP \(k\)-coloring, the below situations are investigated.
Case 1: When \(n\) is even, we partition the vertex set \(V(T(P_n))\) as follows:
\(V_1=\{v_1,e_1,v_3,e_3,\ldots,v_{n-1}e_{n-1}\}\) and \(V_2=\{v_2,e_2,v_4,e_4,\ldots,v_{n-2},e_{n-2},v_n\}\).
Case 2: When \(n\) is odd, \(V(T(P_n))\) is partitioned as below:
\(V_1=\{v_1,e_1,v_3,e_3,\ldots,v_{n-2}e_{n-2},v_n\}\) and \(V_2=\{v_2,e_2,v_4,e_4,\ldots,v_{n-1},e_{n-1}\}\).
In both cases, it is evident that \(||V_1|-|V_2|| = 1\). Now, assigning the vertices of \(V_1\) with the color \(c_1\) and \(V_2\) with the color \(c_2\), we observe that every edge \(v_ie_i\) \(;\) \(1 \leq i \leq n-1\) is a monochromatic edge, and hence the equitable defective number is \(n-1\). ◻
Figure 2 depicts an ENP \(2\)-coloring of the total graph of paths.
The line graph of a cycle \(C_n\) is the cycle \(C_n\) itself. Hence, the equitable chromatic number is \(2\) when \(n\) is even and \(3\) when \(n\) is odd. When \(k=2\) and \(n\) is odd, the equitable defective number is \(1\).
The subsequent theorem examines the ENP \(k\)-coloring of the middle graph of cycles for \(k=2\).
For a cycle \(C_n\), \(b_{\chi_e}^k(M(C_n))=n\).
Proof. Let \(V(C_n)=\{v_1, v_2,
\cdots, v_n\}\) and \(E(C_n)=\{e_1,
e_2, \cdots, e_n\}\). Now,
\(V(M(C_n))=V(C_n) \cup E(C_n)\), and
note that \(\chi_e(M(C_n))=3\), and
thus the ENP \(k\)-coloring considers
only one case \(k=2\). In the first
possible ENP \(k\)-coloring, assign all
of the vertices \(v_i\) and \(e_i\) with the colors \(c_1\) and \(c_2\) respectively, and it can be observed
that every edge between the vertices \(e_i\) is a monochromatic edge, and thus the
equitable defective number is \(n\).
The second possible ENP \(k\)-coloring may be performed as in Theorem 2.1, and this coloring also produces \(n\) monochromatic edges. Additionally, there are \(n\) monochromatic edges of the form \(v_ie_i\) \(;\) \(1 \leq i \leq n\) for even \(n\); however, for odd \(n\), there are \(n-1\) monochromatic edges of the form \(v_ie_i\) \(;\) \(1 \leq i \leq n-1\) and one \(e_{n-1}e_n\) monochromatic edge. Thus, \(b_{\chi_e}^2(M(C_n))=n\). ◻
Figure 3 depicts an ENP \(2\)-coloring of the middle graph of cycles.
The following theorem describes the ENP \(k\)-coloring of the total graph \(T(C_n)\) of a cycle.
For \(T(C_n)\) where \(n \geq 3\), \[b_{\chi_e}^k(T(C_n))= \begin{cases} n; &\mbox{if } k=2,~n~is~even,\\ n+1; &\mbox{if } k=2,~n~is~odd,\\ 1; &\mbox{if } k=3. \end{cases}\]
Proof. Note that \(\chi_e(T(C_n))=3\) when \(n \equiv 0 \mathrm{mod} 3\) and \(4\) otherwise. Hence, the following cases need to be addressed here.
Case 1: Assume that \(k=2\) and \(n\) is even. We partition the vertex set so that \(V_1=\{v_1,e_1,v_3,e_3,\ldots\\ v_{n-1},e_{n-1}\}\) and \(V_2=\{v_2,e_2,v_4,e_4,\ldots v_n,e_n\}\). Now, \(|V_1|=|V_2|\), and every \(v_ie_i\) edge, where \(1 \leq i \leq n\), is a monochromatic edge. Thus, the equitable defective number is \(n\).
Case 2: Assume that \(k=2\) and \(n\) is odd. Let us partition the vertex set such that \(V_1=\{v_1,e_1,v_3,e_3,\ldots v_{n-2},e_{n-2},v_n\}\) and \(V_2=\{v_2,e_2,v_4,e_4,\ldots v_{n-1},e_{n-1},e_n\}\). Here, \(|V_1|=|V_2|\) and \(n-1\) monochromatic edges are obtained connecting \(v_i\) and \(e_i\) \(;\) \(1 \leq i \leq n-1\). Furthermore, another \(v_1v_n\) and \(e_{n-1}e_n\) monochromatic edges are obtained. Thus, the equitable defective number, in this case, is \(n+1\) (see Figure 4 for illustration).
Case 3: When \(k=3\) and \(n \not\equiv 0 \mathrm{mod} 3\), assign the vertices with the three available colors in a cyclic order by considering the equitability condition. Here, the equitable defective number is \(1\). ◻
Figure 4 depicts an ENP \(2\)-coloring of the total graph of cycles.
A sunlet graph denoted by \(Sl_n\) is obtained by attaching \(n\) pendant edges to a cycle \(C_n\). ENP \(k\)-coloring of sunlet graphs is discussed in [4]. In a sunlet graph, the vertices corresponding to \(C_n\) are termed as rim vertices.
The following theorem investigates the ENP \(k\)-coloring of the line graph of a sunlet graph.
The equitable defective number of \(L(Sl_n)\), where \(n \geq 3\), is \(n\).
Proof. Consider \(V(L(Sl_n))=\{v_1,v_2,\ldots,v_n,u_1,u_2,\ldots,u_n\}\), where \(v_i\) induces a cycle of order \(n\), and \(u_i\) are the vertices that are adjacent with both \(v_i\) and \(v_{i+1}\). The equitable coloring of \(L(Sl_n)\) contains \(3\) colors (see [7]), and thus, in an ENP \(k\)-coloring, only one case as \(k=2\) is considered. Let \(c_1\) and \(c_2\) be the two available colors, and the following cases need to be considered.
Case 1: Let \(n\) be even. Then, the \(v_i\) \(;\) \(1 \leq i \leq n\) vertices can be properly colored with the two available colors. When the remaining vertices are assigned the same colors equitably, \(n\) monochromatic edges are obtained between \(v_i\) and \(u_i\) \(;\) \(1 \leq i \leq n\).
Case 2: Let \(n\) be odd and follow the same coloring procedure as in Case 1. That is, assign \(v_1\) with the color \(c_1\), \(v_2\) with the color \(c_2\), and so on. Since \(n\) is odd, both \(v_1\) and \(v_n\) receive the same color, and thus there is a \(v_1v_n\) monochromatic edge on the rim. Now, the vertex adjacent to both \(v_1\) and \(v_n\) receives an alternate color from the color assigned to both of them. Further, the remaining vertices can be assigned in an equitable manner. Thus, \(n-1\) monochromatic edges are obtained between the vertices \(v_i\) and \(u_i\), and the equitable defective number is \(n\).
Combining the above two cases, \(b_{\chi_e}^2(L(Sl_n))=n\). ◻
An ENP \(2\)-coloring of the line graph of sunlet graphs is illustrated in Figure 5.
An ENP \(k\)-coloring of the middle graph of a sunlet graph for distinct values of \(n\) is discussed in the next theorem.
Proof. Consider \(V(M(Sl_n))=\{ v_1, v_2, \ldots, v_n, u_1, u_2, \ldots, u_n, v_1', v_2', \ldots, v_n', u_1', u_2', \ldots, u_n'\}\). Here, the vertices \(v_1, u_1, v_2, u_2,\ldots, v_n, u_n\) forms an inner \(2n\) – cycle termed as the rim vertices of \(M(Sl_n)\), and each \(v_i'\); \(1 \leq i \leq n\) is connected to the corresponding \(v_i\); \(1 \leq i \leq n\) forms an outer \(n\) – cycle. Again, \(u_i';\) \(1 \leq i \leq n\) are the pendant vertices connected to the corresponding \(v_i'\). Recall that \(\chi_e(M(Sl_n))=4\) (see [7]), and in an ENP \(k\)-coloring, two cases are to be considered as \(k=2\) and \(k=3\).
Case 1: Assume \(k=2\) and we partition the vertex set as follows.
\(V_1=\{u_1,u_2,\ldots,u_n,u_1', u_2',\ldots,u_n'\}\) and \(V_2=\{v_1,v_2,\ldots,v_n,v_1',v_2',\ldots, v_n'\}\). Assign the vertices in \(V_1\) with the color \(c_1\) and \(V_2\) with the color \(c_2\). Now, \(|V_1|=|V_2|\), and \(n\) monochromatic edges generated among the vertices \(u_i\). Additionally, the vertices \(v_i\) and \(v_i'\) have \(n\) monochromatic edges connecting them, where \(1 \leq i \leq n\). Thus, the equitable defective number is \(2n\).
Case 2: Let \(k=3\). Among the \(4n\) vertices of \(M(Sl_n)\), \(2n\) vertices are on the rim. Assign all the rim vertices with the three available colors, say \(c_1\), \(c_2\), and \(c_3\), in a cyclic order, and consider the following three subcases.
Subcase 2.1: When \(n\equiv 0 \mathrm{mod} 3\), \(2n\equiv 0 \mathrm{mod} 3\), and assign the rim vertices with the three colors in a cyclic order such that each color repeats exactly \(\frac{2n}{3}\) times without creating any monochromatic edges. Now, assign the vertices \(v_i'\) with the same color received by the vertices \(v_i\), and \(n\) monochromatic edges are obtained in between the vertices \(v_i\) and \(v_i'\) \(;\) \(1 \leq i\leq n\). Further, the vertices \(u_i'\) can be equitably assigned these three colors without creating monochromatic edges. Thus, there are \(n\) monochromatic edges.
Subcase 2.2: When \(n\equiv 1 \mathrm{mod} 3\), \(2n\equiv 2 \mathrm{mod} 3\), follow the same coloring procedure for the rim vertices \(v_i\) and \(u_i\) where \(1 \leq i \leq n\) creates a \(u_1u_n\) monochromatic edge. Since \(2n\equiv 2 \mathrm{mod} 3\), to attain the equitability, color \(c_3\) can be assigned to \(v_1'\). The remaining \(v_i'\); (\(2 \leq i \leq n\)) can receive the same color received by \(v_i\) to obtain \(n-1\) monochromatic edges of the form \(v_iv_i'\) (\(2 \leq i \leq n\)). Further, each \(u_i'\); (\(1 \leq i \leq n\)) can be received any of the three colors equitably with the condition that \(v_i'\) and the corresponding \(u_i'\) receive different colors leading to the equitable defective number as \(n\).
Subcase 2.3: When \(n\equiv 2 \mathrm{mod} 3\), \(2n\equiv 1 \mathrm{mod} 3\), and the rim vertices follow the same coloring pattern as in the previous subcases leads to a \(v_1u_n\) monochromatic edge. Further, the remaining vertices \(v_i'\) and \(u_i'\) can receive any of the three colors by considering the equitability condition, creates \(n-1\) monochromatic edges as in Subcase 2.2. Hence, the equitable defective number in this case is \(n\).
Thus, combining the above three subcases, \(b_{\chi_e}^3(M(Sl_n))=n\). ◻
An ENP \(2\)-coloring of the middle graph of the sunlet graphs is illustrated in Figure 6.
The following theorem discusses the ENP \(k\)-coloring of the total graph of sunlet graphs for different parities of \(n\) and for \(k=2,3\).
For \(T(Sl_n)\) where \(n \geq 3\), \[b_{\chi_e}^k(T(Sl_n))= \begin{cases} 3n; &\mbox{if } k=2,\\ n; &\mbox{if } k=3, n \equiv 0,2 \mathrm{mod} 3,\\ n+1; &\mbox{if } k=3, n \equiv 1 \mathrm{mod} 3. \end{cases}\]
Proof. Consider the vertex sets and the adjacencies as in Theorem 2.6. Observe that \(\chi_e(T(Sl_n))=4\) (see [7]); thus, in an ENP \(k\)-coloring, the following cases need to be considered.
Case 1: When \(k=2\), repeat the same coloring procedure as in Case-1 of Theorem 2.6, and we obtain the equitable defective number as \(3n\).
Case 2: When \(k=3\), follow the same coloring pattern as in Case-2 of Theorem 2.6 by considering the equitability condition and maximising the properness of the coloring, there are the following observations.
Subcase 2.1: When \(n\equiv 0 \mathrm{mod} k\), \(n\) monochromatic edges are obtained of the form \(v_iv_i'\) \(;\) \(1 \leq i\leq n\) as in Theorem 2.6.
Subcase 2.2: When \(n\equiv 1 \mathrm{mod} k\), two monochromatic edges are obtained, one among the vertices \(v_i\) and one among the vertices \(u_i\). Apart from that, the vertices \(v_i\) and \(v_i'\) \(;\) \(2 \leq i \leq n-1\) have \(n-1\) monochromatic edges connecting them. Thus, the equitable defective number is \(n+1\). (See Figure \(\ref{fig:equ.tosun}\) for reference.)
Subcase 2.3: When \(n\equiv 2 \mathrm{mod} k\), we get the same \(n-1\) monochromatic edges as in Subcase 2.2 and an additional monochromatic edge \(v_1u_n\). Thus, the equitable defective number is \(n\). (refer to Figure 7 for illustration.) ◻
An ENP \(3\)-coloring of the total graph of sunlet graphs is illustrated in Figure 7.
The line graph of a star graph \(K_{1,n}\) is a complete graph of order \(n\). The ENP \(k\)-coloring and the corresponding equitable defective number of complete graphs are discussed in [2] and as follows.
The following theorem describes the ENP \(k\)-coloring of the middle graph of star graphs.
Proof. Consider \(V(K_{1,n})=\{v, v_1,v_2,\ldots,v_n\}\) and \(E(K_{1,n})=\{e_1,e_2,\ldots,e_n\}\). Consider \(u_1,u_2,\ldots,u_n\) as the corresponding vertex set of \(E(K_{1,n})\). These edges form a clique of order \(n\) in \(M(K_{1,n})\), and hence \(\chi_e(M(K_{1,n}))=n+1\) as the vertices \(v,u_1,u_2,\ldots,u_n\) induce a complete graph of order \(n+1\). Thus, in an ENP \(k\)-coloring, \(2 \leq k \leq n\) and the following cases need to be considered.
Case 1: When \(k\geq2\) and \(k \neq n\), assign the \(k\) available colors, say \(c_1,c_2,\ldots,c_k\) alternately to the vertices \(u_i\) \(;\) \(1 \leq i \leq n\). Now, color the \(v_i\) vertices so that each \(u_i\) and the corresponding \(v_i\) receive different colors in an equitable manner. Also, assign the vertex \(v\) with any available colors such that \(v\) receives the least used color assigned to the vertices \(u_i\). Since, \(\{v,u_1,u_2,\ldots,u_n\}\) induces a clique of order \(n+1\), the equitable defective number in this case is \(b_{\chi_e}^k(K_{n+1})\).
Case 2: When \(k=n\), assign the vertices \(u_i\) using the \(k\) colors, and the corresponding vertices \(v_i\) can be assigned using the same colors such that both \(u_i\) and the corresponding \(v_i\) receive different colors, and as a result of this assignment no monochromatic edges obtained. Further, assign the vertex \(v\) with any available colors; only one \(vu_i\) monochromatic edge is obtained, and thus the equitable defective number is \(1\). ◻
Figure 8 depicts an ENP \(2\)-coloring of the middle graph of star graphs.
The subsequent theorem determines the equitable defective number of the total graph of star graphs for distinct values of \(n\) and for various values of \(k\).
For the total graph \(T(K_{1,n})\) of a star graph where \(n \geq 3\), \[b_{\chi_e}^k(T(K_{1,n}))= \begin{cases} b_{\chi_e}^k(K_n)+n; &\mbox{if } k = 2,\\ b_{\chi_e}^k(K_n)+\lfloor\frac{2n+1}{k}\rfloor-1; &\mbox{if } k \geq 3;~ k \neq n,\\ 2; &\mbox{if } k=n. \end{cases}\]
Proof. Consider the vertices as in Theorem 2.9. Note that \(\chi_e(T(K_{1,n}))=n+1\) as \(\{v,u_1,u_2,\ldots,u_n\}\) induces a clique of order \(n+1\). The vertices \(u_1,u_2,\ldots,u_n\) induce a clique of order \(n\), and let \(v_1,v_2,\ldots,v_n\) be the vertices that are adjacent to \(u_1,u_2,\ldots,u_n\), respectively. In \(T(K_{1,n})\), the vertex \(v\) is adjacent to all the vertices \(u_i\) and \(v_i\) (\(1 \leq i \leq n\)). The ENP \(k\)-coloring of complete graphs is discussed in Theorem 2.8. Hence, the following cases need to be addressed here.
Case 1: When \(k=2\), assign the two available colors, say \(c_1\) and \(c_2\), for every alternate vertex of the complete graph. Further, if \(c(u_i)=c_1\) (or \(c_2\)), then assign \(c(v_i)=c_2\) (or \(c_1\)). Now, \(c(v)=c_1\) or \(c_2\), and based on this assignment, the following observations are to be noted.
When \(n\) is even, \(\frac{n}{2}\) monochromatic edges of the form \(vu_i\) and \(\frac{n}{2}\) monochromatic edges of the form \(vv_i\) are obtained. When \(n\) is odd, we get \(\lfloor\frac{n}{2}\rfloor\) monochromatic edges of the form \(vu_i\) and \(\lceil\frac{n}{2}\rceil\) monochromatic edges of the form \(vv_i\). Consequently, in both cases, the equitable defective number is \(b_{\chi_e}^k(K_n)+n\).
Case 2: When \(k\geq3\) and \(k \neq n\), we can assign all the vertices with the \(k\) available colors in an equitable manner as follows. When the vertex set is partitioned into \(k\) color classes, each color class consists of either \(\lfloor\frac{2n+1}{k}\rfloor\) vertices or \(\lceil\frac{2n+1}{k}\rceil\) vertices. If the vertex \(v\) is placed in the color class with minimum cardinality \(\lfloor\frac{2n+1}{k}\rfloor\), we obtain \(\lfloor\frac{2n+1}{k}\rfloor-1\) monochromatic edges. Hence, together with the monochromatic edges from \(K_n\), the equitable defective number is \(b_{\chi_e}^k(K_n)+\lfloor\frac{2n+1}{k}\rfloor-1\).
Case 3: When \(k = n\), we can properly color the complete graph of order \(n\) with the \(k\) available colors, and the vertices \(v_1,v_2,\ldots,v_n\) can also be properly colored with these \(k\) colors. Further, assign the vertex \(v\) with any of the \(k\) available colors, from which we obtain two monochromatic edges. ◻
Figure 9 depicts the ENP \(3\)-coloring of the total graph of star graphs.
A gear graph \(G_{1,n}\), which is a bipartite wheel graph, is obtained from a wheel graph by inserting a vertex between the rim vertices. That is, a gear graph is formed by adding a vertex between each pair of adjacent vertices of the outer cycle.
The subsequent theorem examines the ENP \(k\)-coloring of the line graph of a gear graph for different parities of \(n\).
For \(L(G_{1,n})\), \[b_{\chi_e}^k((L(G_{1,n}))= \begin{cases} b_{\chi_e}^k(K_n)+n; &\mbox{if } k = 2,\\ b_{\chi_e}^k(K_n); &\mbox{if } k \geq 3. \end{cases}\]
Proof. Let \(V(G_{1,n})=\{v,v_1,v_2,\ldots,v_{2n}\}\) and \(E(G_{1,n})=\{e_1,e_2,\ldots,e_n,e_1',e_2'\ldots,\\e_{2n}'\}\) such that \(e_i=vv_{2i-1}\) \(;\) \(1 \leq i \leq n\), \(e_i'=v_iv_{i+1}\) \(;\) \(1 \leq i \leq 2n-1\), and \(e_{2n}'=v_{2n}v_1\). Consequently, \(V(L(G_{1,n}))=\{e_1,e_2,\ldots,e_n,e_1',e_2'\ldots,e_{2n}'\}\). Since \(e_i\) \(;\) \(1 \leq i \leq n\) form a clique of order \(n\) in \(L(G_{1,n})\), \(\chi_e(L(G_{1,n}))=n\). Subsequently, in an ENP \(k\)-coloring, consider \(2 \leq k \leq n-1\) and address the following cases.
Case 1: Assume \(k=2\) and assign the vertices \(e_i\) with the two available colors, say \(c_1\) and \(c_2\) alternately. This assignment yields the same amount of monochromatic edges as in the equitable defective number of a complete graph, that is stated in Theorem 2.8. Further, assign the vertices \(e_j'\) with the same available colors in a cyclic order satisfying the equitability condition, and we obtain \(n\) monochromatic edges in between the vertices \(e_i\) and \(e_j'\) \(;\) \(1 \leq i,j' \leq n\). Thus, \(b_{\chi_e}^k(K_n)+n\) gives the equitable defective number in this case.
Case 2: When \(k\geq3\), assign the vertices \(e_i\) with the \(k\) available colors, \(b_{\chi_e}^k(K_n)\) monochromatic edges are obtained. By the definition of \(L(G_{1,n})\), each \(e_i\) is adjacent to two distinct vertices \(e_j'\), which forms a \(K_3\) that can be colored properly using the three available colors such that each vertex of \(K_3\) receives different color. This assignment of colors does not create any additional monochromatic edges; therefore, the equitable defective number is \(b_{\chi_e}^k(K_n)\). ◻
An ENP \(k\)-coloring of the line graph of gear graphs is illustrated in Figure 10.
For various parities of \(n\) and distinct values of \(k\), the theorem below discusses the ENP \(k\)-coloring of the middle graph of gear graphs.
Proof. Consider \(V(G_{1,n})=\{v,v_1,v_2,\ldots,v_{2n}\}\). Let \(E(G_{1,n})=\{e_1,e_2,\ldots,e_{2n}\} \cup \{e_i',e_2',\ldots,e_n'\}\) such that \(e_i=v_iv_{i+1}\) \(;\) \(1 \leq i \leq 2n-1\), \(e_{2n}=v_{2n}v_1\) and \(e_i'=v v_{2i-1}\) \(;\) \(1 \leq i \leq n\). Consequently, \(V(M(G_{1,n}))=\{v,v_1,v_2,\ldots,v_{2n},e_1,e_2,\ldots,e_{2n},e_1',e_2',\\e_3', \ldots,e_n'\}\). It is evident that the edges \(ve_i'\) \(;\) \(1 \leq i \leq n\), along with the vertex \(v\) form a clique of order \(n+1\), and thus \(\chi_e(M(G_{1,n}))=n+1\) (see [6]). In an ENP \(k\)-coloring, consider \(2 \leq k \leq n\) and address the following cases.
Case 1: Let \(k=2\) and consider the subcases as given below.
Subcase 1.1: When \(n\) is even, partition the vertex set into two subsets as follows.
Let \(V_1= \{ v_i: 1 \leq i \leq {2n-3}~;~i \equiv 1 \mathrm{mod} 4 \}\) \(\cup\) \(\{ v_j: 2 \leq j \leq {2n-2}~;~j \equiv 2 \mathrm{mod} 4 \}\) \(\cup\) \(\{ e_k': 1 \leq k \leq {n-1} ~;~ k \equiv 1 \mathrm{mod} 2 \}\) \(\cup\) \(\{ e_l: 3 \leq l \leq {2n-1} ~;~ l \equiv 3 \mathrm{mod} 4 \}\) \(\cup\) \(\{ e_m: 4 \leq m \leq {2n} ~;~ m \equiv 0 \mathrm{mod} 4 \}\).
\(V_2= \{ v_i: 3 \leq i \leq {2n-1}~;~i \equiv 3 \mathrm{mod} 4 \}\) \(\cup\) \(\{ v_j: 4 \leq j \leq 2n~;~j \equiv 0 \mathrm{mod} 4 \}\) \(\cup\) \(\{ e_k': 2 \leq k \leq {n} ~;~ k \equiv 0 \mathrm{mod} 2 \}\) \(\cup\) \(\{ e_l: 1 \leq l \leq {2n-3} ~;~ l \equiv 1 \mathrm{mod} 4 \}\) \(\cup\) \(\{ e_m: 2 \leq m \leq {2n-2} ~;~ m \equiv 2 \mathrm{mod} 4 \}\).
Now, \(|V_1| = |V_2| = \lfloor\frac{5n+1}{2}\rfloor\). Hence, the central vertex \(v\) can be placed into any one of the color classes, resulting in \(||V_1|-|V_2|| = 1\). Further, assign the vertices in the set \(V_1\) with the color \(c_1\) and \(V_2\) with the color \(c_2\). As a result of this assignment of colors, we obtain \(n\) monochromatic edges of the form \(e_i'v_j\) \(;\) \(1 \leq i \leq n\) and \(1 \leq j \leq 2n-1~;~j \equiv 1 \mathrm{mod} 2\). Also, the vertices \(v_i\) and \(e_i\) have \(n-1\) monochromatic edges connecting them, of the form \(v_ie_{i+1}\), where \(2 \leq i \leq 2n-2\) \(;\) \(i \equiv 0 \mathrm{mod} 2\) and there is a monochromatic edge \(e_1v_{2n}\). Further, \(n\) monochromatic edges are obtained in between the vertices \(e_i\) of the form \(e_ie_{i+1}\), where \(1 \leq i \leq 2n-1\) \(;\) \(\equiv 1 \mathrm{mod} 2\). Furthermore, together with the monochromatic edges from the complete graph that is investigated in Theorem 2.8, the equitable defective number is \(b_{\chi_e}^k(K_{n+1})+3n\).
Subcase 1.2: When \(n\) is odd, let us partition the vertex set as follows.
Let \(V_1= \{ v_i: 1 \leq i \leq {2n-1}~;~i \equiv 1 \mathrm{mod} 4 \}\) \(\cup\) \(\{ v_j: 2 \leq j \leq 2n~;~j \equiv 2 \mathrm{mod} 4 \}\) \(\cup\) \(\{ e_k': 1 \leq k \leq {n} ~;~ k \equiv 1 \mathrm{mod} 2 \}\) \(\cup\) \(\{ e_l: 3 \leq l \leq {2n-3} ~;~ l \equiv 3 \mathrm{mod} 4 \}\) \(\cup\) \(\{ e_m: 4 \leq m \leq {2n-2} ~;~ m \equiv 0 \mathrm{mod} 4 \}\).
\(V_2= \{v\}\) \(\cup\) \(\{ v_i: 3 \leq i \leq {2n-3}~;~i \equiv 3 \mathrm{mod} 4 \}\) \(\cup\) \(\{ v_j: 4 \leq j \leq {2n-2}~;~j \equiv 0 \mathrm{mod} 4 \}\) \(\cup\) \(\{ e_k': 2 \leq k \leq {n-1} ~;~ k \equiv 0 \mathrm{mod} 2 \}\) \(\cup\) \(\{ e_l: 1 \leq l \leq {2n-1} ~;~ l \equiv 1 \mathrm{mod} 4 \}\) \(\cup\) \(\{ e_m: 2 \leq m \leq {2n} ~;~ m \equiv 2 \mathrm{mod} 4 \}\).
Assign the vertices in \(V_1\) with the color \(c_1\) and \(V_2\) with the color \(c_2\). Now, \(|V_1| = |V_2| = \frac{5n+1}{2}\) and the vertices \(v_i\) and \(e_i\) have \(n-1\) monochromatic edges connecting them, of the form \(v_ie_i\), where \(2 \leq i \leq 2n-2\) \(;\) \(i \equiv 0 \mathrm{mod} 2\). Moreover, the vertices \(e_i'\) and \(v_j\) have \(n\) monochromatic edges connecting them of the form \(e_i'v_j\) \(;\) \(1 \leq i \leq n\) and \(1 \leq j \leq 2n-1\) \(;\) \(j \equiv 1 \mathrm{mod} 2\). Furthermore, a monochromatic edge \(e_1e_{2n}\) and \(n\) monochromatic edges among the vertices \(e_i\) of the form \(e_ie_{i+1}\) are generated, where \(1 \leq i \leq 2n-1\) \(;\) \(i \equiv 1 \mathrm{mod} 2\). Now, along with the monochromatic edges obtained in the ENP \(k\)-coloring of complete graphs, the equitable defective number is \(b_{\chi_e}^k(K_{n+1})+3n\).
Case 2: When \(k=3\), the following subcases are to be addressed.
Subcase 2.1: Let \(n \equiv 0 \mathrm{mod} 3\). Assign the \(4n\) vertices on the outer rim (\(v_i\) \(;\) \(1 \leq i \leq 2n\) and \(e_i\) \(;\) \(1 \leq i \leq 2n\)) using the three available colors in a cyclic order. Further, color the inner rim vertices (\(e_i'\) \(;\) \(1 \leq i \leq n\)) in the same cyclic order using the three colors such that both \(e_1'\) and \(e_1\) receive the same color. Then, assign \(v\) with any one of the three colors. It can be observed that along with the monochromatic edges obtained from the complete graph, the vertices \(e_i'\) and \(v_i\) generate \(n\) monochromatic edges of the form \(e_i'v_j\) \(;\) \(1 \leq i \leq n\) and \(1 \leq j \leq 2n\) \(;\) \(j \equiv 1 \mathrm{mod} 2\). Thus, the equitable defective number is \(b_{\chi_e}^k(K_{n+1})+n\) (see Figure 11 for illustration).
Subcase 2.2: Let \(n \equiv 1 \mathrm{mod} 3\). Repeat the same coloring procedure as in Subcase 2.1 for the outer rim vertices \(v_i\) and \(e_i\) where \(1 \leq i \leq 2n\), except for one vertex. Since \(4n \equiv 1 \mathrm{mod} 3\), the additional vertex on the outer rim can be assigned the color \(c_2\). Further, the inner rim vertices can also be assigned as in Subcase 2.1, and since \(n \equiv 1 \mathrm{mod} 3\), the additional vertex on the inner rim can be received the color \(c_3\). Further, the vertex \(v\) can receive the color \(c_1\) to maintain the equitability constraint. Here, we obtain the same number of monochromatic edges as compared to Subcase 2.1, and the equitable defective number is \(b_{\chi_e}^k(K_{n+1})+n\).
Subcase 2.3: Let \(n \equiv 2 \mathrm{mod} 3\). We follow the same coloring procedure as in Subcase 2.1 for the outer rim vertices, and the last two vertices of the outer rim receive the colors \(c_1\) and \(c_2\) respectively. Further, the inner rim vertices can also be assigned in the same cyclic order as in the above two subcases, and the last two inner rim vertices can be assigned the colors \(c_1\) and \(c_3\) respectively. Finally, the vertex \(v\) can receive the color \(c_2\) to maintain the equitability constraint. In comparison with Subcase 2.1, we get an additional monochromatic edge of the form \(e_ie_j\). Therefore, the equitable defective number is \(b_{\chi_e}^k(K_{n+1})+n+1\) (see Figure 11).
Case 3: When \(k\geq 4\), the vertices \(v_i\) \(;\) \(1 \leq i \leq 2n\), \(e_i\) \(;\) \(1 \leq i \leq 2n\) and \(e_i'\) \(;\) \(1 \leq i \leq n\) can be assigned properly using the \(k\) available colors. Now the vertex \(v\) can also be received any of the available colors equitably, the resulting monochromatic edges are only from the clique. Thus, the equitable defective number is \(b_{\chi_e}^k(K_{n+1}).\) ◻
Figure 11 represents the ENP \(k\)-coloring of the middle graph of gear graphs.
The subsequent theorem examines the ENP \(k\)-coloring of the total graph of gear graphs for different parities of \(n\) and various values of \(k\).
For the total graph of a gear graph \(G_{1,n}\), \[b_{\chi_e}^k (T(G_{1,n}))= \begin{cases} b_{\chi_e}^k(K_{n+1})+\frac{9n}{2}; &\mbox{if } k = 2,n~ even,\\ b_{\chi_e}^k(K_{n+1})+\frac{9n+1}{2}; &\mbox{if } k = 2,n~ odd,\\ b_{\chi_e}^k(K_{n+1})+n+\frac{n}{3}; &\mbox{if } k = 3, n \equiv 0 \mathrm{mod} k\\ b_{\chi_e}^k(K_{n+1})+n+\lfloor\frac{n}{3}\rfloor+2; &\mbox{if } k = 3, n \equiv 1,2 \mathrm{mod} 3\\ b_{\chi_e}^k(K_{n+1}); &\mbox{if } k \geq 4. \end{cases}\]
Proof. Note that \(V(T(G_{1,n}))=V(M(G_{1,n}))\) and \(\chi_e(T(G_{1,n}))=n+1\) (see [6]). The following observations are made when the same coloring procedure is followed, as in Theorem 2.12.
Case 1: When \(k=2\) and \(n\) is even, apart from the monochromatic edges obtained as in Subcase-1.1 of Theorem 2.12, \(n-1\) monochromatic edges are obtained of the form \(v_iv_{i+1}\), where \(1 \leq i \leq 2n-2 ~;~i \equiv 0 \mathrm{mod} 2\) along with a monochromatic edge \(v_1v_{2n}\). Further, there are \(\frac{n}{2}\) monochromatic edges connecting \(v_i\) and \(v\). Thus, the equitable defective number is \(b_{\chi_e}^k(K_{n+1})+\frac{9n}{2}\).
Case 2: When \(k=2\) and \(n\) is odd, along with the monochromatic edges obtained as in Subcase-1.2 of Theorem 2.12, we may obtain \(n\) monochromatic edges of the form \(v_iv_{i+1}\), where \(2 \leq i \leq 2n-2 ~;~i \equiv 0 \mathrm{mod} 2\) and another monochromatic edge \(v_1v_{2n}\) also obtained. Further, there are \(\lfloor\frac{n}{2}\rfloor\) monochromatic edges connecting the vertices \(v_i\) and \(v\). Hence, the equitable defective number is \(b_{\chi_e}^k (K_{n+1})+\frac{9n+1}{2}\).
Case 3: When \(k=3\), we have the below observations.
Subcase 3.1: When \(n \equiv 0 \mathrm{mod} 3\), apart from the monochromatic edges obtained as in Subcase 2.1 of Theorem 2.12, we obtain \(\frac{n}{3}\) additional monochromatic edges of the form \(vv_i\). Hence, the equitable defective number is \(b_{\chi_e}^k (K_{n+1})+n+\frac{n}{3}\).
Subcase 3.2: When \(n \equiv 1 \mathrm{mod} 3\), apart from the monochromatic edges obtained as in Subcase 2.2 of Theorem 2.12, we obtain \(\lfloor\frac{n}{3}\rfloor\) monochromatic edges of the form \(vv_i\). Further, there are two additional monochromatic edges of the form \(v_iv_j\), and hence, the equitable defective number is \(b_{\chi_e}^k (K_{n+1})+n+\lfloor\frac{n}{3}\rfloor+2\).
Subcase 3.3: When \(n \equiv 2 \mathrm{mod} 3\), along with the monochromatic edges obtained as in Subcase 2.3 of Theorem 2.12, we obtain \(\lfloor\frac{n}{3}\rfloor\) monochromatic edges of the form \(vv_i\) and one monochromatic edge of the form \(v_iv_j\). Hence, the equitable defective number is \(b_{\chi_e}^k (K_{n+1})+n+\lfloor\frac{n}{3}\rfloor+2\).
Case 4: When \(k\geq 4\), follow the same coloring procedure as in Case-3 of Theorem 2.12 by considering the equitability condition, which is illustrated in Figure 12. We observe that the resulting monochromatic edges are only from the clique. Hence, the equitable defective number is \(b_{\chi_e}^k(K_{n+1})\). ◻
Figure 12 illustrates the ENP \(k\)-coloring of the total graph of gear graphs.
In this paper, we explored the ENP \(k\)-coloring of the line, middle, and total graph of some graph classes and investigated the equitable defective number with respect to the ENP \(k\)-coloring. This study can be extended to different graph classes and many other derived graphs. Moreover, the central graph of all these graph classes can also be discussed. Further investigations can be done in powers of graphs and different graph products.
The authors would like to gratefully acknowledge the critical and constructive comments made by the reviewers which has elevated the standards of the paper significantly. They also acknowledge their co-researcher Ms. Phebe Sarah George for her inputs which refined the content of this paper.
The authors declare no conflict of interest.