On the r-dynamic coloring of some fan graph families

DOI: 10.2478/auom-2021-0039 An. S¸t. Univ. Ovidius Constant¸a Vol. 29(3),2021,151–181 On the r-dynamic coloring of some fan graph families Ra´ul M. Falc´on, M. Venkatachalam, S. Gowri and G. Nandini Abstract In this paper, we determine the r-dynamic chromatic number of the fan graph Fm,n and determine sharp bounds of this graph invariant for four related families of graphs: The middle graph M(Fm,n), the total graph T(Fm,n), the central graph C(Fm,n) and the line graph L(Fm,n). In addition, we determine the r-dynamic chromatic number of each one of these four families of graphs in case of being m= 1. 1 Introduction Let rand `be two positive integers. In 2001, as a natural generalization of the classical problem of graph coloring, Montgomery [24] introduced the concept of r-dynamic proper `-coloring of a given graph G= (V(G), E(G)) as any proper `-coloring c:V(G)→ {0, . . . , ` −1}such that every vertex v∈V(G) satisfies that |c(N(v))| ≥ min{r, d(v)}.(1) Here, N(v) and d(v) denote, respectively, the neighborhood and the degree of the vertex v. That is to say, in practice, the colors of the vertices within the neighborhood of each given vertex v∈V(G) are pairwise distinct, whenever r≥d(v). Otherwise, there exist at least rdistinct colors in its neighborhood. Key Words: r-dynamic coloring, fan graph, middle graph, total graph, central graph, line graph. 2010 Mathematics Subject Classification: Primary 05C15. Received: 01.02.2021 Accepted: 15.05.2021 151 ON THE R-DYNAMIC COLORING OF SOME FAN GRAPH FAMILIES 152 The minimum positive integer `for which an r-dynamic proper `-coloring of Gexists constitutes the r-dynamic chromatic number χr(G) of the graph G. If r= 1, then these two concepts coincide indeed with the classical ones of proper `-coloring and chromatic number of a graph. As a first stage in the study of this new graph coloring, the interest focused on the case r= 2 [1–4]. It is in the recent literature where one may observe how the problem of computing r-chromatic numbers of distinct types and families of graphs, with r > 2, has received particular interest from a wide amount of graph theorists and has become a prolific field of study [6,8,9,11,15–17,20,26]. Additionally, the study of upper bounds has also become a focus of study. Thus, for instance, Jahanbekam et al. [14] proved that χr(G)≤r·∆(G)+1, for a general positive integer r. (Here, ∆(G) denotes the maximum degree of the vertices of G.) Previously, Lai et al. [19] had already proved that χr(G)≤∆(G) + r2−r+ 1, whenever ∆(G)≤r. Of particular relevance for the aim of this paper is the study of the rdynamic coloring of fan graphs and related families [23,26], a type of graphs for which the study of different proper colorings awakes interest in the literature [29,32, 33]. This paper delves into this topic by focusing on the study of the r-dynamic chromatic number of four families of graphs: middle graphs, total graphs, central graphs and line graphs, derived all of them from a given fan graph Fm,n. In the recent literature, one can find studies concerning different proper colorings of middle, total, central and line graphs of different types of graphs [5, 27, 28, 30, 31]. More specifically, the r-dynamic proper coloring of these four families of graphs has already been studied for bistar graphs [25], gear graphs [7] and helm graphs [10]. Some partial results concerning fan graphs F1,n may be found in [23]. The r-dynamic chromatic number of the line graph of a given graph coincides with the r-dynamic edge chromatic number of the latter. Remind in this regard that Meganingtyas [21] introduced in 2015 the notion of rdynamic proper k-edge-coloring of a graph G= (V(G), E(G)) as a proper k-edge-coloring csuch that |c(N(uv))| ≥ min{r, d(u) + d(v)−2}, for every pair of adjacent vertices u, v ∈V(G), where N(uv) denotes the set of edges that are incident to that one containing both vertices uand v. The r-dynamic edge chromatic number λr(G) is the minimum positive integer kfor which an r-dynamic proper k-edge-coloring of the graph Gexists. If r= 1, then both concepts refer to the classical ones of proper edge-coloring and edge chromatic number. ON THE R-DYNAMIC COLORING OF SOME FAN GRAPH FAMILIES 153 The paper is organized as follows. In Section 2, we describe some preliminary concepts and results on Graph Theory that are used throughout the manuscript. Then, Sections 3–6 deal, respectively, with the r-dynamic chromatic number of the middle, total, central and line graphs of a fan graph. 2 Preliminaries This section deals with some preliminary concepts and results on Graph Theory that are used throughout the paper. For more details about this topic, we refer the reader to [13]. Any graph G= (V(G), E(G)) is formed by a set V(G) of vertices and a set E(G) of edges so that each edge contains two vertices, which are called adjacent. Two distinct edges sharing a common vertex are called incident. The cardinalities of V(G) and E(G) are, respectively, the order and size of G. If both values are finite, then Gis said to be finite. It is complete if any pair of vertices are adjacent. The complete graph of order nis denoted Kn. The subset of vertices in V(G) that are adjacent to a vertex v∈V(G) is its neighborhood NG(v). The cardinality dG(v) of this set is its degree. Every vertex of degree zero is said to be isolated. From now on, we write N(v) and d(v) when there is no risk of confusion. In addition, δ(G) and ∆(G) denote, respectively, the minimum and maximum vertex degree of G. Further, asubgraph of Gis any graph Hsuch that V(H)⊆V(G) and E(H)⊆E(G). It is said to be induced if E(H) is formed by all those edges in E(G) connecting vertices of V(H). It is an n-clique of Gif it coincides with Kn. Finally, a spanning subgraph of Gis any subgraph Hsuch that V(H) = V(G). From now on, let vw ∈E(G) denote the edge formed by two vertices v, w ∈V(G). It is a loop if v=w. Further, two distinct edges containing the same pair of vertices are said to be parallel. A graph is simple if it contains no loops and no parallel edges. From now on, all the graphs in this manuscript are simple and finite. Apath Pnbetween two distinct vertices v, w ∈V(G) is any ordered sequence of nadjacent and pairwise distinct vertices hv0=v, v1, . . . , vn−2, vn−1=wi in V(G), with n > 2. If v=w, then such a sequence is called a cycle, which is denoted Cn. The fan graph Fm,n is the graph that results after joining each vertex of a set of misolated vertices with all the vertices of the path Pn. The middle graph [12] of Gis the graph M(G) having as vertices the set V(M(G)) = V(G)∪E(G) so that two such vertices are adjacent if and only if they are either two incident edges in Gor a vertex and an edge in Gso that ON THE R-DYNAMIC COLORING OF SOME FAN GRAPH FAMILIES 154 the latter contains the former. If besides an edge is added for each pair of adjacent vertices in G, then we get the total graph T(G). Further, the central graph C(G) derives from Gby replacing each edge of the latter with a path of size two and then joining each pair of non-adjacent vertices in G. Finally, the line graph L(G) has the edges of Gas its set of vertices, so that two such vertices are adjacent if and only if the related two edges in Gare incident. Figure 1 illustrates these four graphs, all of them associated to F2,3. Figure 1: Fan graph, together with its middle, central, total and line graphs. Aproper `-coloring of the graph Gis any map c:V(G)→ {0, . . . , ` −1} assigning a set of `distinct colors to the set of vertices V(G) in such a way that no two adjacent vertices share the same color. Analogously, a proper `-edge-coloring of the graph Gis any map c:E(G)→ {0, . . . , ` −1}so that no two incident edges share the same color. The minimum positive integer k for which a proper k-coloring (respectively, a proper k-edge-coloring) of the graph Gexists is termed the chromatic number χ(G) (respectively, the edge chromatic number λ(G)) of G. Particular examples are the r-dynamic proper k-(edge-)coloring and the r-dynamic (edge) chromatic number of a graph G, which have already been introduced in Section 1. Particularly, χ1(G) = χ(G), λ1(G) = λ(G) and λr(G) = χr(L(G)), for every positive integer r. The following results are also known. Lemma 1. [18] Let Gbe a graph and let rbe a positive integer. Then, min {r, ∆(G)}+ 1 ≤χr(G)≤χr+1(G). Moreover, χr(G)≤χ∆(G)(G). Lemma 2. [19] Let nand rbe two positive integers such that n > 2. Then, a) χr(Pn) = (2,if r= 1, 3,otherwise. ON THE R-DYNAMIC COLORING OF SOME FAN GRAPH FAMILIES 155 b) χr(Cn) =                2,if r= 1 and nis even, 3,if (r= 1 and nis odd, r > 1and n≡0 (mod 3), 4,if r > 1and n6= 5, 5,otherwise. c) χr(Kn) = n. Lemma 3. [23] Let nand rbe two positive integers such that n > 2. Then, a) χ2(M(F1,n)) = n+ 1, if n≥7. b) χ5(T(F1,n)) = n+ 1, if n≥9. c) χ2(C(F1,n)) = n+ 1, if n≥4. d) χn(L(F1,n)) = n+ 1, if n≥6. Let mand nbe two positive integers such that n > 2. Throughout the whole paper, let Fm,n denote the fan graph of set of vertices V(Fm,n) = {u0, . . . , um−1, v0, . . . , vn−1}, which is associated to the path Pn=hv0, . . . , vn−1i. That is, the set of edges of the fan graph Fm,n is E(Fm,n) = {u0v0, . . . , u0vn−1, . . . , um−1vn−1, v0v1,..., vn−2vn−1}. In particular, δ(Fm,n) = min{m+ 1, n}and ∆(Fm,n) = max{m+ 2, n}. The following result establishes the r-dynamic coloring of the fan graph Fm,n. Proposition 1. Let m,nand rbe three positive integers such that n > 2. Then, χr(Fm,n) =                3,if r∈ {1,2}, 2r−1,if 3≤r≤min{m+ 1, n}, n+r−1,if n<r≤m+ 1, m+r, if max{3, m + 1} ≤ r≤n, m+n, if r≥max{m+ 1, n}. Proof. Since the vertices u0, v0, v1∈V(Fm,n) describe a 3-clique of Fm,n, Lemma 2 implies that every proper coloring of Fm,n requires at least three distinct colors. In addition, since N(ui) = {vj: 0 ≤j < n}, for all nonnegative integer i<m, and N(v0) = {ui: 0 ≤i<m}∪{v1}, the remaining values constitute lower bounds of χr(Fm,n) under the corresponding assumptions because of Condition (1) and the fact that the map cis a proper coloring. ON THE R-DYNAMIC COLORING OF SOME FAN GRAPH FAMILIES 156 In order to prove that each one of these lower bounds is reached, it is enough to describe for each case an appropriate r-dynamic proper coloring cof the fan graph Fm,n satisfying Condition (1). Thus, for instance, if r∈ {1,2}, then we define the map cso that c(ui) = 2 and c(vj) = jmod 2, for all non-negative integers i<mand j < n. Furthermore, if r≥3, the map cis defined so that, for each pair of non-negative integers i<mand j < n, we have that c(ui) = (min{r, n}+i, if i < min{r−1, m} min{r, n}+ min{r−1, m} − 1,otherwise. and c(vj) = (j, if j < min{r, n}, jmod r, otherwise. Figures 2 and 3 illustrate Proposition 1 for the fan graphs F2,3and F6,4. Figure 2: r-dynamic proper `colorings of the fan graph F2,3, for (r, `)∈ {1,2}×{3}(left) and r≥3 and `= 5 (right). Figure 3: r-dynamic proper `-coloring of the fan graph F6,4, for (r, `) = (3,5) (left), (r, `) = (4,7) (center) and r≥7 and `= 10 (right). ON THE R-DYNAMIC COLORING OF SOME FAN GRAPH FAMILIES 157 3 Dynamic coloring of the middle graph of a fan graph This section deals with the r-dynamic chromatic number of the middle graph M(Fm,n). Its set of vertices is V(M(Fm,n)) = {u0, . . . , um−1, v0, . . . , vn−1, u0v0, . . . , u0vn−1,..., um−1v0, . . . , um−1vn−1, v0v1, . . . , vn−2vn−1} In this middle graph, for each pair of non-negative integers i < m and j < n, we have that d(ui) = n, d(vj) = (m+ 1,if j∈ {0, n −1}, m+ 2,otherwise. and d(uivj) = (m+n+ 1,if j∈ {0, n −1}, m+n+ 2,otherwise. and, for each non-negative integer k < n −1, we have that d(vkvk+1) = (2m+ 3,if k∈ {0, n −2}, 2m+ 4,otherwise. Hence, δ(M(Fm,n)) = min{m+ 1, n}and ∆(M(Fm,n)) = max{m+n+ 2,2m+ 4}. Further, for each pair of non-negative integers i < m and j < n, let KM(Fm,n )(i) denote the (n+ 1)-clique of the middle graph M(Fm,n) that is defined by the set of vertices V(KM(Fm,n )(i)) = {ui, uiv0, . . . , uivn−1} and let K0 M(Fm,n )(j) denote the induced subgraph of M(Fm,n) that is defined by the set of vertices V(K0 M(Fm,n )(j)) = =     {v0, u0v0, . . . , um−1v0, v0v1},if j= 0, {vn−1, u0vn−1, . . . , um−1vn−1, vn−2vn−1},if j=n−1, {vj, u0vj, . . . , um−1vj, vj−1vj, vjvj+1},otherwise. Notice that K0 M(Fm,n )(j) constitutes an (m+ 2)-clique within M(Fm,n), if j∈ {0, n−1}, and an (m+3)-clique, otherwise. These cliques enable us to establish a pair of sharp bounds for the r-dynamic chromatic number χr(M(Fm,n)). ON THE R-DYNAMIC COLORING OF SOME FAN GRAPH FAMILIES 158 Proposition 2. Let m,nand rbe three positive integers such that n > 2. Then, max{m+ 3, n + 1} ≤ χr(M(Fm,n)) ≤(3m+ 5,if n= 3, m·n+ 6,otherwise. The lower bound is reached for every positive integer r < max{m+ 3, n + 1}, whereas the upper bound is reached for every positive integer r≥∆(M(Fm,n)). Proof. The lower bound holds simply from Lemma 2, once it is noticed that both the (n+ 1)-clique KM(Fm,n )(0) and the (m+ 3)-clique K0 M(Fm,n )(1) are subgraphs of the middle graph M(Fm,n). In order to prove that this lower bound is sharp, let us describe an appropriate proper χr(M(Fm,n))-coloring c of the middle graph M(Fm,n) satisfying Condition (1). In order to make clearer the proof, we illustrate this map cwith a specific dynamic coloring of a middle graph M(Fm,n), where the edges of the (n+ 1)-clique KM(Fm,n )(0) and the (m+ 3)-clique K0 M(Fm,n )(1) are respectively highlighted with bold and dashed lines. In addition, the vertices of the sets {u0, . . . , um−1},{v0, . . . , vn−1}, {u0v0, . . . , um−1vn−1}and {v0v1, . . . , vn−2vn−1}are respectively distinguished by means of the symbols N,H,•and . The following study of cases arises. •Case m≤n−2 and r≤n. Let the map cbe defined so that, for each pair of non-negative integers i<mand j < n, we have that c(ui)=(n+i) mod (n+ 1), c(vj) = (2 + j) mod (n+ 1), c(uivj)=(i+j) mod (n+ 1) and, for each non-negative integer k < n −1, we have that c(vkvk+1) = (n+k) mod (n+ 1). Condition (1) holds and hence, χr(M(Fm,n)) = n+1. Figure 4 illustrates the middle graph M(F1,4). •Case m>n−2 and r≤m+ 2. Let the map cbe defined so that, for each pair of non-negative integers i<mand j < n, we have that c(ui) = m+ 1, c(vj)=(n+j−1) mod (m+ 1) and c(uivj) = (i+j) mod (m+ 1), ON THE R-DYNAMIC COLORING OF SOME FAN GRAPH FAMILIES 159 Figure 4: r-dynamic proper 5-coloring of M(F1,4), for all r≤4. and, for each non-negative integer k < n −1, we have that c(vkvk+1) = (m+ 1,if kis even, m+ 2,otherwise. Condition (1) holds and hence, χr(M(Fm,n)) = m+ 3. Figure 5 illustrates the middle graph M(F3,4). Figure 5: r-dynamic proper 6-coloring of M(F3,4), for all r≤5. Now, in order to study the upper bound, Lemma 1 enables us to focus on the case r= ∆(M(Fm,n)). Let cbe a ∆(M(Fm,n))-dynamic proper χ∆(M(Fm,n ))(M(Fm,n))-coloring of the middle graph M(Fm,n). Then, Condition (1) implies that |c(N(v))|=d(v), for all v∈V(M(Fm,n)). In particular, the set {c(u0v0), . . . , c(um−1vn−1)}is formed by m·ndistinct colors, because {uiv0, . . . , uivn−1} ⊂ V(KM(Fm,n )(i)), for every non-negative integer i < m, and, if c(uivj) = c(ui0vj0) for some non-negative integers i, i0< m and j, j0< n such that i6=i0and j6=j0, then we would have, for instance, that |c(N(uivj0))|< d(uivj0). In a similar way, each one of the three vertices v1, v0v1,v1v2of the (m+ 3)-clique K0 M(Fm,n )(1) requires an extra new color. ON THE R-DYNAMIC COLORING OF SOME FAN GRAPH FAMILIES 166 So, let us assume the second option. Since d(v0) = 4 and d(v0v1) = 5, Condition (1), together with the already colored vertices, implies that {c(v0), c(v1)}={2,3}and c(v1v2) = 4. But then, |c(N(v1))|= 4, which contradicts Condition (1), because d(v1) = 6. – Subcase n≥5. Here, (2) contradicts Condition (1), because it would imply the existence of a non-negative integer k < n −1 such that |c(N(vkvk+1))|< d(vkvk+ 1) ≤6≤n+ 1. Thus, n+3 ≤χr(T(F1,n)). In order to prove that this bound is reached, let the map cbe defined so that c(vj) = n+ 1 + (jmod 2) and c(vkvk+1)=(k+ 2) mod n, for all non-negative integers j < n and k < n−1. Condition (1) holds and hence, χn+1(T(F1,n)) = n+ 3. Figure 11 illustrates the case n∈ {3,4}. Figure 11: (n+ 1)-dynamic proper (n+ 3)-coloring of T(F1,n), for n∈ {3,4}. •Case ρ= 2. Lemma 1 implies that n+ 3 ≤χn+2(T(F1,n)). If this lower bound were reached, then, similarly to the previous case, both colors n+1 and n+ 2 should be contained within each one of the sets that we have described in (2). In particular, since the map cis a proper coloring, it should be c(v0) = c(v1v2). It would imply that |c(N(v0v1))|<5 = d(v0v1), which contradicts Condition (1). Hence, n+ 4 ≤χn+2(T(F1,n)). This lower bound is not reached for n= 3, which requires an eight color. Otherwise, Condition (1) would imply that {c(v0), c(v0v1), c(v1v2)}={4,5,6}and c(v0) = c(v2). But then, any coloring of the vertex v1would contradict either Condition (1) or the fact that the map cis a proper coloring. Figure 12 (left) illustrates that χ5(T(F1,3)) = 8. ON THE R-DYNAMIC COLORING OF SOME FAN GRAPH FAMILIES 167 Figure 12: (n+ 2)-dynamic proper 8-coloring of T(F1,n), for n∈ {3,4}. Now, in order to prove that the lower bound n+ 4 is reached for all n≥4, let the map cbe defined so that c(v0) = n+1, c(vj)=(j+2) mod n, c(vn−1) = n+1+(nmod 3), and c(vkvk+1) = n+1+((k+1) mod 3), for all positive integer j < n −1 and all non-negative integer k < n −1. Condition (1) holds and hence, χn+2(T(F1,n)) = n+ 4, for all n≥4. Figure 12 (right) illustrates the case n= 4. •Case 3≤ρ < min{5, n}. If r≥n+ 3, then Condition (1) implies that no two distinct vertices within the neighborhood of any given vertex v∈V(T(F1,n)) \ {u0}are equally colored. Particularly, if we focus our attention on the vertex v1, then it is simply verified that n+ 6 ≤χr(T(F1,n)), for every positive integer r≥n+ 3. In order to prove that this lower bound is reached, let the map cbe defined so that c(vj) = n+1+(2jmod 5) and c(vkvk+1) = n+1+((2k+1) mod 5), for all non-negative integers j < n and k < n −1. Condition (1) holds and hence, χr(T(F1,n)) = n+ 6, whenever n+ 3 ≤r≤min{n+ 5,2n}. Figure 13 illustrates the case n∈ {3,4}. •Case 5≤ρ<n. From Lemma 1, we have that n+ρ+1 ≤χn+ρ(T(F1,n)). In order to prove that this lower bound is reached, it is enough to consider the map cthat we have just described in the previous case, except for c(vi) = n+6+i, for all non-negative integer i<ρ−5. ON THE R-DYNAMIC COLORING OF SOME FAN GRAPH FAMILIES 168 Figure 13: r-dynamic proper `-coloring of the total graph T(F1,n), for all r≥6, with (n, `)∈ {(3,9),(4,10)}. 5 Dynamic coloring of the central graph of a fan graph Let us focus now on the r-dynamic chromatic number of the central graph C(Fm,n). Its set of vertices is V(C(Fm,n)) = {u0, . . . , um−1, v0, . . . , vn−1, w0,0, . . . , w0,n−1, . . . , wm−1,0,..., wm−1,n−1, w0 0,1, . . . , w0 n−2,n−1}. Here, for each pair of non-negative integers i < m and j < n, the vertex wi,j is the third one within the path of size two joining both vertices uiand vj. Similarly, for each non-negative integer k < n −1, the vertex w0 k,k+1 is the third one within the path of size two joining both vertices vkand vk+1. In particular, d(ui) = d(vj) = m+n−1 and d(wi,j) = d(w0 k,k+1)=2 for all non-negative integers i<m,j < n and k < n−1. Hence, δ(C(Fm,n)) = 2 and ∆(C(Fm,n)) = m+n−1. Let KC(Fm,n )and K0 C(Fm,n )denote, respectively, the m- and dn 2e-cliques within the central graph C(Fm,n) that are described by the set of vertices V(KC(Fm,n )) = {u0, . . . , um−1}and V(K0 C(Fm,n )) = nv2i: 0 ≤i < ln 2mo. From now on, and similarly to the already studied families of graphs, every dynamic coloring of the central graph C(Fm,n) is illustrated so that the edges of the just described m- and n 2-cliques are respectively highlighted with bold and dashed lines. In addition, the vertices of the sets {u0, . . . , um−1}, ON THE R-DYNAMIC COLORING OF SOME FAN GRAPH FAMILIES 169 {v0, . . . , vn−1},{w0,0, . . . , wm−1,n−1}and {w0 0,1, . . . , w0 n−2,n−1}are respectively distinguished by means of the symbols N,H,•and . The following result establishes the chromatic number of the central graph C(Fm,n). Proposition 5. Let mand n > 2be two positive integers. Then, χ(C(Fm,n)) =      3,if m≤ dn 2e= 2, n 2,if m≤n 26= 2, m, otherwise. Proof. Let us study each case separately. •Case m≤ dn 2e= 2. Since the cycle C5described by the subset of vertices {v0, v0v1, v1, v1v2, v2} ⊂ V(C(Fm,n)) is an induced subgraph of the central graph C(Fm,n), Lemma 2 implies that 3 ≤χ(C(Fm,n)). This lower bound is sharp for all m≤ dn 2e= 2. To see it, it is enough to define a proper 3-coloring cof the central graph C(Fm,n) so that c(ui) = i, c(wi,j)=2, c(vj) = j 2and c(w0 k,k+1) = 2, for all non-negative integers i < m,j < n and k < n −1. Condition (1) holds and hence, χ(C(Fm,n)) = 3, for all m≤ dn 2e= 2. Figure 14 (left) illustrates the central graph C(F2,4). Figure 14: Proper 3-colorings of C(F2,4), C(F3,5) and C(F3,4). ON THE R-DYNAMIC COLORING OF SOME FAN GRAPH FAMILIES 170 •Case m≤ dn 2e 6= 2. The existence of the n 2-clique K0 C(Fm,n )as a subgraph of the central graph C(Fm,n), together with Lemma 2 implies that n 2≤χ(C(Fm,n)). In order to prove that this lower bound is reached, we define a proper n 2-coloring cof the central graph C(Fm,n) so that c(wi,j) =      n 2−1,if max i, j 2<n 2−1, (i+ 1) mod n 2,if i≤n 2−1 = j, j 2+ 1mod n 2,otherwise. c(ui) = i, c(vj) = j 2and c(w0 k,k+1) = ln 2m−1, for all non-negative integers i < m,j < n and k < n −1. Condition (1) holds and hence, χ(C(Fm,n)) = n 2, for all m≤ dn 2e 6= 2. Figure 14 (center) illustrates the central graph C(F3,5). •Case m > dn 2e. The existence of the m-clique KC(Fm,n )as a subgraph of the central graph C(Fm,n), together with Lemma 2 implies that m≤χ(C(Fm,n)). In order to prove that this lower bound is reached, we define a proper m-coloring cof the central graph C(Fm,n) so that c(ui) = i, c(wi,j) = (m−1,if i<m−1, j 2+ 1mod n 2,otherwise. c(vj) = j 2and c(w0 k,k+1) = m−1, for all non-negative integers i < m,j < n and k < n −1. Condition (1) holds and hence, χ(C(Fm,n)) = m, for all m > dn 2e. Figure 14 (right) illustrates the central graph C(F3,4). The following result describes a pair of sharp bounds for the case r > 1. Proposition 6. Let m,nand rbe three positive integers such that n > 2and r > 1. Then, m+n≤χr(C(Fm,n)) ≤(n+ 2,if m= 1, 2m+n−1,if m > 1. ON THE R-DYNAMIC COLORING OF SOME FAN GRAPH FAMILIES 171 The lower bound is reached whenever r < max{m, n}, whereas the upper bound is reached whenever r≥∆(C(Fm,n)). Proof. Throughout the proof, let cdenote an r-dynamic proper χr(C(Fm,n))- coloring of the central graph C(Fm,n). Since d(wi,j) = d(w0 k,k+1) = 2, for every non-negative integers i<m,j < n and {c(u0), . . . , c(um−1), c(v0), . . . , c(vn−1)} is formed by m+ndistinct colors. Hence, m+n≤χr(C(Fm,n)). In order to prove that this lower bound is reached whenever r < max{m, n}, the following two cases arise. •Case m≤n. Let the map cbe defined so that c(ui) = i, c(wi,j) = m+ ((j+ 1) mod n), c(vj) = m+jand c(w0 k,k+1)=0, for all non-negative integers i < m,j < n and k < n −1. Condition (1) holds and hence, χr(C(Fm,n)) = m+n. Figure 15 (left) illustrates the case (m, n) = (1,4). Figure 15: r-dynamic proper colorings of the central graphs C(F1,4) and C(F4,3), for all r∈ {2,3}. •Case n<m. Let the map cbe defined so that c(ui) = i, c(wi,j) = (m+ ((j+ 1) mod n),if i= 0, (i+j+ 1) mod m, otherwise. ON THE R-DYNAMIC COLORING OF SOME FAN GRAPH FAMILIES 172 c(vj) = m+jand c(w0 k,k+1)=0, for all non-negative integers i < m,j < n and k < n −1. Condition (1) holds and hence, χr(C(Fm,n)) = m+n. Figure 15 (right) illustrates the case (m, n) = (4,3). Now, in order to deal with the upper bound, Lemma 1 enables us to focus on the case r= ∆(C(Fm,n)). The following two cases arise. •Case m= 1. Condition (1) implies that the set {c(w0 0,1), . . . , c(w0 n−2,n−1)}is formed by, at least, two distinct colors. Since one of them may coincide with c(u0), and none of them belongs to the set of ndistinct colors {c(v0),..., c(vn−1)}, we have that n+ 2 ≤χ∆(C(Fm,n ))(C(Fm,n)). In order to prove that this lower bound is reached, let the map cbe defined so that c(u0)=0, c(w0,j) = j+ 2, c(vj) = j+ 1 and c(w0 k,k+1) = (0,if k≡n(mod 2), n+ 1,if k6≡ n(mod 2). for every pair of non-negative integers j < n and k < n −1. Condition (1) holds and hence, χ∆(C(Fm,n ))(C(F1,n)) = n+ 2. Figure 16 (left) illustrates the central graph C(F1,4). Figure 16: r-dynamic proper colorings of the central graphs C(Fm,n), for all r≥m+n−1, with (m, n)∈ {(1,4),(4,3)}. •Case m > 1. For each non-negative integer j < n, since |c(N(vj))|=d(vj) = m+n−1, Condition (1) implies that the set {c(w0,j), . . . , c(wm−1,j )}is formed by mdistinct colors, none of them in the set {c(u0), . . . , c(um−1), c(v0), . . . , c(vn−1)} ON THE R-DYNAMIC COLORING OF SOME FAN GRAPH FAMILIES 173 except for      {c(v1)},if j= 0, {c(vj−1), c(vj+1)},if 0 < j < n −1, {c(vn−2)},if j=n−1, As a consequence, 2m+n−1≤χ∆(C(Fm,n ))(C(Fm,n)). In order to prove that this lower bound is reached, let the map cbe defined so that c(wi,j) =          m+j+ 1,if i= 0 and j < n −1, 2m+n−2,if (i, j) = (0, n −1), m+n−2,if (i, j)=(m−1, n −1), m+n+ ((i+j−1) mod (m−1)),otherwise. c(ui) = i, c(vj) = m+jand c(w0 k,k+1) = (0,if kis even, 1,if kis odd. for all non-negative integers i < m,j < n and k < n −1. Condition (1) holds and hence, χ∆(C(Fm,n ))(C(F1,n)) = 2m+n−1. Figure 16 (right) illustrates the case (m, n) = (4,3). As an immediate consequence of Propositions 5 and 6, the following result establishes the r-dynamic chromatic number of the central graph C(F1,n). Theorem 3. Let n > 2and rbe two positive integers. Then, χr(C(F1,n)) =          3,if r= 1 and n∈ {3,4}, dn 2e,if r= 1 and n > 4, n+ 1,if 2≤r < n, n+ 2,otherwise. 6 Dynamic coloring of the line graph of a fan graph Let us finish this paper by dealing with the r-dynamic chromatic number of the line graph L(Fm,n). Its set of vertices is V(L(Fm,n)) = E(Fm,n) and its set of edges is ON THE R-DYNAMIC COLORING OF SOME FAN GRAPH FAMILIES 174 E(L(Fm,n)) = {(uivj)(uivk),(uivj)(vlvj): 0 ≤i, l < m, and 0 ≤j, k < n} ∪ {(uivj)(vj−1vj),(uivj)(vjvj+1): 0 ≤i<mand 0 < j < n −1} ∪ {(uiv0)(v0v1),(uivn−1)(vn−2vn−1): 0 ≤i<m}. For all non-negative integers i<m,j < n and k < n −1, we have that d(uivj) = (m+n−1,if j∈ {0, n −1}, m+n, otherwise. and d(vkvk+1) = (2m+ 1,if k∈ {0, n −2}, 2m+ 2,otherwise. Hence, δ(L(Fm,n)) = (2m+ 1,if m≤n−2, m+n−1,otherwise. and ∆(L(Fm,n)) = (m+n, if m≤n−2, 2m+ 2,otherwise. Further, let KL(Fm,n )and K0 L(Fm,n )denote, respectively, the n- and (m+ 2)- cliques within the line graph L(Fm,n) that are described by the sets of vertices V(KL(Fm,n )) = {u0vj: 0 ≤j < n} and V(K0 L(Fm,n )) = {v0v1, v1v2, uiv1: 0 ≤i<m}. Again, similarly to the previous sections, every dynamic coloring of the line graph L(Fm,n) is illustrated from now on so that the edges of the just described n- and (m+2)-cliques are respectively highlighted with bold and dashed lines. Their corresponding vertices are respectively distinguished by means of the symbols Nand H. The following result establishes a pair of sharp bounds for the r-dynamic chromatic number χr(L(Fm,n)). Proposition 7. Let m,nand rbe three positive integers such that n > 2. Then, max{m+ 2, n} ≤ χr(L(Fm,n)) ≤(m·n+ 2,if n= 3, m·n+ 3,otherwise. ON THE R-DYNAMIC COLORING OF SOME FAN GRAPH FAMILIES 175 The lower bound is reached whenever r < max{m+ 2, n}, whereas the upper bound is reached whenever r≥∆(L(Fm,n)). Proof. The lower bound holds straightforwardly from Lemma 2, once it is noticed, for instance, that both cliques KL(Fm,n )and K0 L(Fm,n )are subgraphs of the line graph L(Fm,n). In order to prove that this lower bound is reached for every positive integer r < max{m+ 2, n}, it is enough to consider the proper coloring cof the line graph L(Fm,n) such that c(uivj)=(i+j) mod max{m+ 2, n} and c(vkvk+1)=(m+k+ 1) mod max{m+ 2, n}, for all non-negative integers i<m,j < n and k < n −1. Condition (1) holds and hence, χr(L(Fm,n)) = max{m+ 2, n}, whenever r < max{m+ 2, n}. Figure 17 illustrates the case (m, n)∈ {(2,3),(2,4)}. Figure 17: r-dynamic proper 4-colorings of the line graph L(Fm,n), for all r≤max{m+ 2, n}, with (m, n)∈ {(2,3),(2,4)}. Now, in order to study the upper bound, Lemma 1 enables us to focus on the case r= ∆(L(Fm,n)). Let cbe a ∆(L(Fm,n))-dynamic proper χ∆(L(Fm,n ))(∆(L(Fm,n)))-coloring of the line graph L(Fm,n). In a similar way to the proof of the upper bound in Proposition 2, we may ensure that the set {c(u0v0), . . . , c(um−1vn−1), c(v0v1), c(v1v2)} is formed by m·n+ 2 distinct colors. Moreover, if n≥4, then the vertex v2v3 requires an (m·n+ 3)th extra color. Hence, χ∆(L(Fm,n ))(∆(L(Fm,n))) ≥(3m+ 2,if n= 3, m·n+ 3,otherwise. In order to prove that this lower bound is reached, let the map cbe such that c(uivj) = i·n+jand c(vkvk+1) = m·n+ (kmod3),