# The Dominator Edge Coloring of Graphs

Authors: Minhui Li; Shumin Zhang; Caiyun Wang; Chengfu Ye
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

LetG be a simple graph. A dominator edge coloring (DE-coloring) of G is a proper edge coloring in which each edge of G is adjacent to every edge of some color class (possibly its own class). The dominator edge chromatic number (DEC-number) of G is the minimum number of color classes among all dominator edge colorings of G, denoted by χd′G. In this paper, we establish the bounds of the DEC-number of a graph, present the DEC-number of special graphs, and study the relationship of the DEC-number between G and the operations of G.


---

## Body

## 1. Introduction and Preliminaries

All graphs considered here are finite, undirected, and simple. For standard graph theory terminology not given here, we refer to[1]. Let G=V,E be a simple graph with the vertex set V=VG and the edge set E=EG. The order and size of G are denoted by n=V and m=E, respectively. The degree of a vertex v is the number of edges incident with v, denoted by dv. A vertex u is called isolated vertex if du=0. Let δG and ΔG be the minimum degree and the maximum degree of G, respectively. The diameter of G is the maximum distance between any two vertices in G, denoted by diam (G). A vertex (An edge) independent set of G is a set of vertices (edges) such that any two vertices (edges) of the set are not adjacent. The vertex (edge) independence number of G is the maximum of the cardinalities of all vertex (edge) independent sets, denoted by αGβG. For any subset X⊆VG, let G−X denote a subgraph of G obtained by removing X. For any subset Y⊆EG, let G−Y denote a subgraph of G obtained by removing Y. We denote a path, a cycle, a complete graph, a star, and a wheel graph of order n by Pn, Cn, Kn, K1,n−1, and Wn, respectively. A graph G=X,Y is bipartite if VG admits a partition into XandY classes such that every edge of G has its ends in different classes. A double star graph Sn,m is a tree, obtained by adding an edge between the center vertices of K1,n and K1,m. A double wheel graph Wn,n is obtained by two cycles of order n connected to a common hub. We say that a graph is connected if there is a path between any two vertices of the graph and otherwise is called disconnected.A setS⊆VG is called a dominating set of G if every vertex not in S is adjacent to at least one vertex in S. The domination number of G is the minimum cardinality taken over all dominating sets of G, denoted by γG.Aproper coloring of a graph G is a function f:VG⟶1,…,kk∈N such that fu≠fv if u and v are adjacent. The chromatic number of G is the minimum number of colors needed in a proper coloring of G, denoted by χG. Gera et al. [2] introduced and studied the dominator coloring of a graph. A dominator coloring of G is a proper coloring of G such that every vertex of G is adjacent to all vertices of at least one color class. The dominator chromatic number of G is the minimum number of color classes in dominator colorings of G, denoted by χdG. For more surveys of dominator coloring in graphs, refer [3–6].Motivated by a dominator coloring of a graph, we consider the proper edge coloring ofG and introduce the dominator edge coloring of G. A proper edge coloring of a graph G is a function c:EG⟶1,…,kk∈N with ce≠cf for any adjacent edges eandf. The edge chromatic number of G is the minimum number of colors needed in a proper edge coloring of G, denoted by χ′G.Definition 1.
A dominator edge coloring ofG, briefly DE-coloring, is a proper edge coloring of G in which each edge of G is adjacent to every edge of some color class (possibly its own class). The dominator edge chromatic number of G, briefly DEC-number, is the minimum number of color classes among all dominator edge colorings of G, denoted by χd′G.
If an edgee is adjacent to every edge of some color class, we also say that edominates this color class. A color is free if no edge dominates this color class in a DE-coloring of G.
The DEC-number of a graph is related to its edge domination number. In 1977, Mitchell and Hedetniemi introduced the concept of the edge dominating of a graph in [7]. Also the reader can consult [8–11] for more details about the edge domination problem. An edge dominating setD⊆E of G, briefly ED-set, is an edge set such that every edge is adjacent to at least one edge in D. The edge domination number of G is the minimum cardinality among all edge dominating sets of G, denoted by γ′G. Clearly, a γ′G-set is an ED-set of G with minimum cardinality.
A concept closely related to dominator edge coloring is total dominator edge coloring. In [12], Ghanbari and Alikhani introduced the total dominator edge coloring. A total dominator edge coloring of G, briefly TDE-coloring, is a proper edge coloring in which each edge of G is adjacent to every edge of some (other) color class. The total dominator edge chromatic number of G, briefly TDEC-number, is the minimum number of color classes among all total dominator edge colorings of G, denoted by χd′tG. In addition, some results in [13–15] provide a lot of ideas for this paper.
In this paper, we establish the lower and upper bounds of the DEC-number of a graph, present the DEC-number of special graphs, and study the relationship of DEC-number betweenG and the operations of G.
Now, we briefly introduce some related results.Lemma 1 (see [10]).
For a pathPn with n≥2,(1)γ′Pn=n3,ifn≡0mod3,n3,ifn≡1mod3,n3,ifn≡2mod3.Lemma 2 (see [10]).
For a cycleCn with n≥3, γ′Cn=⌈n/3⌉.Lemma 3 (see [10]).
For any graphG with order n and size m, γ′G=n−m if and only if G has γ′G components each of which is isomorphic to a star.


## 2. DEC-Number of a Graph

In this section, we establish the bounds of the DEC-number of a graph. First, we present the following three observations.Observation 1.
LetG be a graph. Then, χ′G≤χd′G, and also the bound is sharp.Observation 2.
LetG be a graph with size m≥1. Then, 1≤χd′G≤m, and also the bounds are sharp.Observation 3.
LetT be a tree with diamT≤3. Then, χd′T=χ′T.Proof.
IfdiamT=1, then T is K2. Clearly, χd′K2=χ′K2=1. If diamT=2, then T is a star. We have χd′T=χ′T=ΔT. If diamT=3, then T is a double star. We have χd′T=χ′T=ΔT.Theorem 1.
LetG be a connected graph. Then,(2)maxχ′G,γ′G≤χd′G≤γ′G+χ′G,and also the bounds are sharp.Proof.
First, we prove the lower bound. Obviously,χ′G≤χd′G. Let f=E1,E2,…,El be a minimal DE-coloring of G, where l=χd′G and D=e1,e2,…,el for each edge ei∈Ei1≤i≤l. According to the definition of DE-coloring of G, for any edge of G, it dominates at least a color class, and then any edge e∈EG is adjacent to at least one edge of D or is an edge in D. And by the definition of ED-set of G, it is easy to see that D is a γ′G-set of G, so γ′G≤χd′G.
Now, we proveχd′G≤γ′G+χ′G. Let c:EG⟶1,2,…,k be a proper edge coloring of G. We assign the colors k+1,k+2,…,k+γ′ to the edges of a γ′G-set of G, and the other edges are colored as before. Clearly, this is a DE-coloring of G, so χd′G≤γ′G+χ′G.
WhenG≅P3, we know that χd′P3=χ′P3=2. When G≅P7, we know that χd′tP7=γ′P7+χ′P7=4. So, the bounds are sharp.Theorem 2.
LetG be a connected graph. Then,(3)χd′G≤γ′G+minDχ′GEG−D,where D⊆EG is a γ′G-set of G, and also the bound is sharp.Proof.
Letp=minχ′GEG−D|Dis aγ′G−set, S=e1,e2,…,eq be a γ′G-set such that χ′GEG−S=p, and f:EG−S⟶1,2,…,p be a proper edge coloring of GEG−S. We define g:EG⟶1,2,…,p+q such that(4)ge=p+i,ife=ei∈S,fe,ife∉S.
SinceS is an ED-set of G, g is a DE-coloring of G. Hence, χd′G≤q+p=γ′G+minχ′GEG−D|Dis aγ′G−set.
WhenG≅C3, we know that χd′tC3=γ′C3+minDχ′GEC3−D=3. So, the bound is sharp.Next, we give an upper bound for the DEC-number of a graphG in terms of the edge independence number βG.Theorem 3.
LetG be a connected graph with size m. Then,(5)χd′G≤m+1−βG,and also the bound is sharp.Proof.
LetG be a connected graph with size m and M be a maximum independent edge set of G. Let E−M=e1,e2,…,em−βG and f=E1,E2,…,Em+1−βG be an edge coloring of G in which Ei=ei1≤i≤m−βG and Em+1−βG=M. Since G is connected and M is an edge independent set, every edge of M is adjacent to some edge ei and dominates the color class Ei1≤i≤m−βG. By the coloring f, we know that each edge ei dominates the color class Ei. Thus, f is a DE-coloring of G, and χd′G≤m+1−βG.
WhenG≅P4, we know that χd′P4=m+1−βP4=3+1−2=2. So, the bound is sharp.Theorem 4.
LetG be a graph with order n, and γ′G=1. Then, χd′G=χ′G.Proof.
Obviously,χd′G≥χ′G. Since γ′G=1, G is a connected graph with order at least 2. If G=K2, this result is obvious. If n>2, then G has an edge e which is adjacent to all other edges of the graph. Let f be a proper edge color of G with χ′ colors. Then, the edge e will take a unique color. Therefore, f is also a DE-coloring, and χd′G≤χ′G. Hence, χd′G=χ′G.Theorem 5.
LetG be a graph with order n and size m, γ′G=n−m. Then, χd′G=γ′G+χ′G−1.Proof.
First, we proveχd′G≤γ′G+χ′G−1. By Lemma 3, we know that G has γ′ components G1,G2,…,Gγ′, each of which is isomorphic to a star. Let D=ei|ei∈Gi,1≤i≤γ′ and f be a proper edge coloring of G with χ′ colors. Assign the color i to ei of D, respectively, where 1≤i≤γ′, and we give a proper edge coloring with χ′−1 colors to G−D. Obviously, this is a DE-coloring of G. So, χd′G≤γ′G+χ′G−1.
Now, we proveχd′G≥γ′G+χ′G−1. Let f′ be a minimal DE-coloring of G. According to the definition of DE-coloring, every Gi contains at least one edge with unique color in f′, so we need at least γ′ unique colors. The other edges except for colored uniquely need at least χ′−1 colors such that f′ is a DE-coloring. So, χd′G≥γ′G+χ′G−1. Hence, χd′G=γ′G+χ′G−1.


## 3. DEC-Number of Special Graphs

In this section, we obtain the DEC-number of special graphs.Observation 4.
LetKn be a complete graph. Then, χd′K3=χd′K4=3,χd′K5=5.Theorem 6.
LetKn be a complete graph with n≥6. Then,(6)χd′Kn=n+n2−2,ifn≡0mod2,n+n2−1,ifn≡1mod2.Proof.
Letf=E1,E2,…,Eχ′ be a proper edge coloring of Knn≥6. Then, every Ei1≤i≤χ′ consists of ⌊n/2⌋ edges. We take a color class Ei1≤i≤χ′ and assign a unique color to each edge of Ei; the other edges of G be colored as before. Clearly, this is a DE-coloring of Kn. So, χd′Kn≤⌊n/2⌋+χ′Kn−1.
Now, we proveχd′Kn≥⌊n/2⌋+χ′Kn−1. Let f′=E1,E2,…,Eχd′ be a minimal DE-coloring of Kn. We see that if an edge e of Kn dominates some color class Ej1≤j≤χd′, then Ej contains at most two edges. When Ej=1, there are 2n−3 edges to dominate Ej in Kn. When Ej=2, there are 4 edges to dominate Ej in Kn. Obviously, 2n−3≥4 when n≥6. Therefore, the size of the dominated color classes of f′ is 1, and f′ contains ⌊n/2⌋ dominated color classes. That is, ⌊n/2⌋ edges of Kn are put unique color in f′, and the remaining edges of Kn need χ′Kn−1 colors to have a proper edge coloring. So, χd′Kn≥⌊n/2⌋+χ′Kn−1.
Hence,χd′Kn=⌊n/2⌋+χ′Kn−1; in addition,(7)χ′Kn=n−1,ifn≡0mod2,n,ifn≡1mod2.
So, we have(8)χd′Kn=n+n2−2,ifn≡0mod2,n+n2−1,ifn≡1mod2.Theorem 7.
LetG=X,Y be a bipartite graph with no isolated vertex, and X=n and Y=m. Then,(9)ΔG≤χd′G≤minn,m+ΔG−1,and also the bounds are sharp.Proof.
The lower bound is obvious. We show thatχd′G≤minn,m+ΔG−1. Without loss of generality, suppose that n≥m. Let X=v1,v2,…,vn, Y=u1,u2,…,um, and D=viuj|vi∈X,uj∈Y,1≤i≤n,1≤j≤m be an edge independent set of G and D=m. We assign a unique color to each edge of D and give a proper edge coloring with ΔG−1 colors to edges of EG−D. Clearly, this is a DE-coloring of G, so χd′G≤minn,m+ΔG−1.
WhenG≅P3, we know that χd′P3=ΔP3=2. When G≅P7, we know that χd′P7=min4,3+ΔP7−1=4. So, the bounds are sharp.Theorem 8.
LetPn be a path with n≥9. Then,(10)χd′Pn=k+2,ifn=3k,3k+1,k+3,ifn=3k+2.Also,χd′P2=1, χd′P3=χd′P4=2, χd′P5=χd′P6=3, and χd′P7=χd′P8=4.Proof.
Forn≤8, the results are obvious. Suppose that n≥9. Let VPn=vi|1≤i≤n and ei=vivi+11≤i≤n−1. According to the definition of DE-coloring, we must use at least one new color for each of three consecutive edges in Pn. In fact, if we assign used colors to the edges ei and ei+1, then a new color is assigned to the edge ei+2. If we assign used colors to the edges ei and ei+2, then a new color is assigned to the edge ei+1 (see Figure 1(a)).
Ifn=3k, we give a DE-coloring which uses only one new color in each of three consecutive edges to P3k. Defining a coloring function f0 on EP3k, see Figure 1(b).(11)f0ei=2,ifi≡0mod3,1,ifi≡1mod3,3+i−23,ifi≡2mod3.
Clearly, this coloring is a DE-coloring ofP3k with the minimum number of colors, so χd′P3k=k+2.
Ifn=3k+1, we give a minimal DE-coloring to P3k+1 using f0 (see Figure 1(b)). So, χd′P3k+1=k+2.
Ifn=3k+2, we color 3k edges according to f0 and assign a new color k+3 to the edge e3k+1 (see Figure 1(b)). Clearly, this is a DE-coloring of P3k+2 with the minimum number of colors, so χd′P3k+2=k+3.Figure 1
(a) Three consecutive edges. (b) A DE-coloring ofPn for n=3k,3k+1,and3k+2.
(a)(b)Corollary 1.
LetPn be a path with n≥9. Then, χd′Pn=γ′Pn+2.Proof.
By Lemma1 and Theorem 8, it is easy to prove the result.Theorem 9.
There exists aχd′Pn-coloring of Pnn≥5 in which the subcoloring induced on consecutive n−3 vertices is a dominator edge coloring of Pn−3.Proof.
LetPn=v1v2⋯vn, ei=vivi+11≤i≤n−1, and f be an arbitrary χd′Pn-coloring of Pn. Suppose that the restriction on f to Pn−3=vk,vk+1,…,vk+n−4 is not a DE-coloring, where 1≤k≤4.
Whenk=1, Pn−3=v1,v2,…,vn−3. Since Pn−3 has no DE-coloring on f, it must be that both fen−5 and fen−4 are reused colors and fen−3 is a unique color. We interchange the colors on en−4 and en−3. Thus, the resulting coloring induces a DE-coloring of Pn−3.
Whenk=2, Pn−3=v2,v3,…,vn−2. It may be three cases that fe2 and fe3 are reused colors and fe1 is a unique color or fen−4 and fen−3 are reused colors and fen−2 is a unique color or both. We interchange the colors on e1 and e2 or the colors on en−3 and en−2 or both. Thus, the resulting coloring induces a DE-coloring of Pn−3.
Whenk=3, Pn−3=v3,v4,…,vn−1; it is similar to k=2.
Whenk=4, Pn−4=v4,v5,…,vn; it is similar to k=1.Theorem 10.
LetG be a graph with size m and diameter d. Then, χd′G≤m−⌊2d−1/3⌋+2.Proof.
LetP be a path of G with size d and the edge set e1,e2,…,ed. We give a DE-coloring to G as follows: giving a DE-coloring to P, by Theorem 8, we know that χd′Pd+1≤⌈d+1/3⌉+2. Furthermore, we assign unique color to the other edges of G. So, we have a DE-coloring of G with m−⌊2d−1/3⌋+2 colors. Thus, χd′G≤m−⌊2d−1/3⌋+2.Theorem 11.
LetCn be a cycle with n≥6. Then,(12)χd′Cn=k+2,ifn=3k,k+3,ifn=3k+1,3k+2.Also,χd′C3=3, χd′C4=2, and χd′C5=3.Proof.
It is easy to show thatχd′C3=χd′C5=3 and χd′C4=2. When n≥6, it is similar to the proof of Theorem 8.Corollary 2.
LetCn be a cycle with n≥6. Then, χd′Cn=γ′Cn+2.Proof.
By Lemma2 and Theorem 11, this result is immediate.Corollary 3.
Forn≥9, χd′Pn=χd′Cn−1.Proof.
By Theorem8 and Theorem 11, this result is immediate.Theorem 12.
(i) LetWn be a wheel graph with n≥4. Then, χd′Wn=n−1. (ii) Let Wn,n be a double wheel graph with n≥3. Then, χd′Wn,n=2n.Proof.
(i) It is obvious thatχd′Wn≥ΔWn=n−1. On the other hand, we can give a DE-coloring with n−1 colors to Wn (see Figure 2(a)). So, χd′Wn=n−1. (ii) It is similar to the proof of (i), so χd′Wn,n=2n (see Figure 2(b)).Figure 2
(a) A DE-coloring ofWn. (b) A DE-coloring of Wn,n.
(a)(b)Theorem 13.
(i) LetK1,n be a star graph with n≥1. Then, χd′K1,n=n. (ii) Let Sn,m be a double star graph with n,m≥1. Then, χd′Sn,m=maxn,m+1.Proof.
(i) It is obvious thatχd′K1,n≥ΔK1,n=n. On the other hand, we can give a DE-coloring of K1,n with n colors (see Figure 3(a)). So, χd′K1,n=n.
(ii) Without loss of generality, suppose thatn≥mn,m≥1. Since ΔSn,m=n+1, a DE-coloring of Sn,m contains at least n+1 colors. We assign the color i to the edge uui1≤i≤n, the color j to the edge vvj1≤j≤m, and the color n+1 to the edge uv (see Figure 3(b)). Obviously, this is a DE-coloring of Sn,m, so χd′Sn,m=maxn,m+1.Figure 3
(a) A DE-coloring ofK1,n. (b) A DE-coloring of Sn,m.
(a)(b)


## 4. DEC-Number of Some Operations of a Graph

Letv∈VG and e=uv∈EG. The deletion of v in G, denoted by G−v, is the graph by deleting the vertex v and all edges incident with v in G. The deletion of e in G, denoted by G−e, is the graph by simply deleting the edge e. The contraction of v in G, denoted by G/v, is the graph by deleting v and putting a clique on the open neighbourhood of v. The contraction of e in G, denoted by G/e, is the graph by replacing u and v with a single vertex such that edges incident with the new vertex are the edges other than e that was incident with u or v, and G/e has one edge less edge than G.Next, we study the DEC-number aboutG−v, G−e, G/v, and G/e.Theorem 14.
IfG is a connected graph and v∈VG but not a cut vertex, then(13)χd′G−dv≤χd′G−v≤χd′G+dv.Proof.
First, we proveχd′G−v≥χd′G−dv. Giving a DE-coloring to G−v, we add the vertex v and all the corresponding edges. We assign unique color to all incident edges with v, and the other edges of G are colored as before. This is a DE-coloring of G and χd′G≤χd′G−v+dv.
Now, we proveχd′G−v≤χd′G+dv. Giving a DE-coloring to G, we remove the vertex v. We take dv edges in which the endpoints of them cover Nv and assign unique color to these edges, and the other edges of G−v are colored as before. Clearly, this is a DE-coloring of G−v, and χd′G−v≤χd′G+dv.
The lower bound is sharp for the graphG in Figure 4. Obviously, χd′G−v=χd′G−dv=2.Figure 4
The graphG that the lower bound is sharp.Theorem 15.
IfG is a connected graph and e∈EG, then(14)χd′G−1≤χd′G−e≤χd′G+1.Proof.
First, we proveχd′G−e≥χd′G−1. We give a DE-coloring to G−e and assign a new color to e in G. Obviously, this is a DE-coloring of G, so χd′G−1≤χd′G−e.
Now, we proveχd′G−e≤χd′G+1. Suppose that f is a DE-coloring of G and the edge e=uv has the color i. We consider the following three cases.
Ifi is not free color and only the edge e has the color i, then by removing e, we can add at most one new color to give a DE-coloring to G−e. Let the color j be a new color, we only assign the colors i and j to two edges which are adjacent to e and their endpoints are u and v, respectively, and the other edges of G−e are colored as before. This coloring is a DE-coloring of G−e. So, χd′G−e≤χd′G+1.
Ifi is not free color and there are other edges with the color i, according to the definition of DE-coloring, we know that at most two edges having the color i. We color every edge of G−e according to f; this is also a DE-coloring of G−e. So, χd′G−e≤χd′G.
Ifi is free color, the restriction on f is a DE-coloring of G−e, so χd′G−e≤χd′G.
From the above discussion, we haveχd′G−e≤χd′G+1.
The lower bound is sharp for the graphG≅P5 and G−e≅P4 and χd′P4=χd′P5−1.Theorem 16.
IfG is a connected graph and v∈VG, then(15)χd′G−dv≤χd′Gv≤χd′G+3dv2.Proof.
First, we proveχd′G/v≥χd′G−dv. Giving a DE-coloring to G/v, we assign unique color to incident edges of v in G, and the other edges are colored as before. This is a DE-coloring of G. So, χd′G−dv≤χd′G/v.
Now, we proveχd′G/v≤χd′G+⌊3dv/2⌋. According to the definition of DE-coloring, we only need to consider the case that Nv is an independent set. Giving a DE-coloring to G and contracting the vertex v, we know that Nv becomes a clique, denoted by Kdv. By Theorem 6, assigning unique color to ⌊dv/2⌋+1 edges of Kdv which cover all vertices of Kdv and contain a maximum independent edge set of Kdv, we give a proper edge coloring with dv−1 colors to the other edges of Kdv, and the other edges of G/v are colored as before. This is a DE-coloring of G/v. Hence, χd′G/v≤χd′G+⌊3dv/2⌋.Theorem 17.
IfG is a connected graph and e=uv∈EG, then(16)χd′G−1≤χd′Ge≤χd′G+mindu,dv.Proof.
First, we proveχd′G/e≥χd′G−1. Giving a DE-coloring to G/e and assigning a new color to e in G, obviously, we know that this is a DE-coloring of G. So, χd′G−1≤χd′G/e.
Now, we proveχd′G/e≤χd′G+mindu,dv. Without loss of generality, suppose that mindu,dv=du. Giving a DE-coloring to G and contracting the edge e, we assign u−1 new colors and the color of e to incident edges of u in G, and the other edges of G/e are colored as before. Clearly, this is a DE-coloring of G/e. Hence, χd′G/e≤χd′G+mindu,dv.
The lower bound is sharp for the graphG≅C5 and G/e≅C4, χd′C4=χd′C5−1.


## 5. Further Research

This paper introduces a new variation of edge coloring, namely, dominator edge coloring combining the concepts of edge domination and edge coloring. We just studied some initial results onχd′G. There is abundant scope for further research on dominator edge coloring of graphs. We list the following open problems.Problem 1.
For treesT, determine the bound of χd′T.Problem 2.
Fork≥3, characterize graphs G satisfying χd′G=k.Problem 3.
Characterize graphsG satisfying χd′G=χ′G.Problem 4.
Characterize graphsG satisfying χd′G=γ′G.Problem 5.
Characterize graphsG satisfying χd′G=χd′tG.



---

*Source: 8178992-2021-10-07.xml*