On the r-dynamic coloring of subdivision-edge coronas of a path

1.   Introduction

In 1970, Frucht and Harary ^[1] introduced the corona product $G\odot H$ of a center graph $G = (V(G), E(G))$ and an outer graph $H$ as the graph that is obtained from $G$ and $|V(G)|$ copies of $H$, all of them being vertex-disjoint, so that the $i^{\mathrm{th}}$ vertex of $V(G)$ is joined to every vertex in the $i^{\mathrm{th}}$ copy of $H$. Further, the subdivision graph of a graph $G$ is defined as the graph $S(G)$ obtained by inserting a new vertex into every edge of $G$. From here on, the set of such inserted vertices is denoted $I(G)$. In 2016, Pengli Lu and Yufang Miao ^[2] introduced the subdivision-edge corona $G\ominus H$ of two vertex-disjoint graphs $G$ and $H$ as the graph obtained from $S(G)$ and $|I(G)|$ copies of $H$, all of them being vertex-disjoint, so that the $i^{\mathrm{th}}$ vertex of $I(G)$ is joined to every vertex in the $i^{\mathrm{th}}$ copy of $H$.

In the literature, one can find different studies on chromatic numbers of the corona product of two given types of graphs ^{[3,4,5,6,7,9,8,10,11,12,13,14,15,16,17]} and even some particular study on chromatic numbers of the subdivision-edge corona of two graphs ^[18]. This paper delves into this last topic. Particularly, we focus on the $r$-dynamic proper $k$-coloring of a subdivision-edge corona of a finite path and a certain simple, finite and connected graph. Recall in this regard that, in 2001, Bruce Montgomery ^[19] (see also ^[20]) introduced the concept of $r$-dynamic proper $k$-coloring or $(r, k)$-coloring of a graph $G = (V(G), E(G))$ as a proper $k$-coloring $c:V(G)\rightarrow \{1, \ldots, k\}$ such that the number of colors appearing within the neighborhood $N(v)$ of each vertex $v\in V(G)$ satisfies that

Here, $d(v)$ denotes the degree of the vertex $v$ within the graph $G$. Further, the $r$-dynamic chromatic number $\chi_r(G)$ was introduced as the minimum positive integer $k$ such that the graph $G$ has an $r$-dynamic proper $k$-coloring. As such, both notions generalize the classical ones of proper coloring and chromatic number of a graph, which result for $r = 1$. Since the original manuscript of Montgomery, a wide amount of authors have dealt with the study of $r$-dynamic proper $k$-colorings and $r$-dynamic chromatic numbers of different types of graphs ^{[21,22,23,24,25,26,27,28,29]}. Of particular interest for the topic of this paper, it is remarkable the study of $r$-dynamic chromatic numbers of graphs described by a corona product ^{[5,10,11,12,13]}. Furthermore, the notion of $r$-dynamic proper coloring was generalized by Akbari et al. ^[30] to that of list dynamic coloring of a graph, for which the color of each vertex is chosen from its own list assignment of colors. Recent advances concerning this last topic are dealt with in ^{[31,32,33,34,35,36,37,38]}.

This paper is organized as follows. In order to get a self-contained paper, Section 2 describes some preliminary concepts and results on Graph Theory that are used throughout the paper. In Section 3, we establish a series of lemmas that are later used in our study. Finally, Section 4 enumerates the different results dealing with the $r$-dynamic chromatic numbers of the subdivision-edge corona of a path with each one of the nine types of graphs under study.

2.   Preliminaries

This section deals with some preliminary concepts and results on Graph Theory that are used throughout the paper.

A graph is a pair $G = (V(G), E(G))$ formed by a set $V(G)$ of vertices and a set $E(G)$ of edges joining two vertices, which are then said to be adjacent. Each edge is said to be incident to the two vertices that it contains. If both vertices are indeed the same one, then the edge is said to be a loop. A graph is said to be simple if it does not contain any loop. The neighborhood of a vertex $v\in V(G)$ is the subset $N_G(v)\subseteq V(G)$ that is formed by all its adjacent vertices. The cardinality of this subset is the degree of $v$, which is denoted $d_G(v)$. From now on, we denote $N(v)$ and $d(v)$ whenever there is no risk of confusion. Moreover, the maximum vertex degree of the graph $G$ is denoted $\Delta(G)$. Further, a subetaaph of the graph $G$ is any other graph $H = (V(H), E(H))$ such that $V(H)\subseteq V(G)$ and $E(H)\subseteq E(G)$.

The order of a graph is the number of its vertices. A graph is said to be finite if its order is. A finite graph is said to be complete if any two of its vertices are adjacent. The complete graph of order $n$ is denoted $K_n$. Further, a finite graph of order $m+n$ is said to be complete bipartite if its vertices can be partitioned into two subsets of respective sizes $m$ and $n$ so that every pair of vertices in different subsets are adjacent, but no more edges exist. This graph is denoted $K_{m, n}$. The complete bipartite graph $K_{1, n}$, with $n > 2$, is called a star. Its center is the unique vertex that is contained in all the edges. A double star $K_{1, n, n}$, with $n > 2$, is the graph that results after adding $n$ new vertices and edges to the star $K_{1, n}$ so that each new edge joins a non-center vertex of the star with one of the new vertices. Figure 1 illustrates these four types of graphs.

From now on, the edge formed by two given vertices $v, w\in V(G)$ is denoted $vw$. A path between two distinct vertices $v, w\in V(G)$ is any ordered sequence of adjacent vertices $\langle\, v, v_2, \ldots, v_{n-1}, w\, \rangle$ in $V(G)$, with $n > 2$, such that all the vertices under consideration are pairwise distinct. This is a cycle if $v = w$. If all the vertices of a cycle are joined to a new vertex, then the resulting graph is called a wheel. From here on, let $P_n$, $C_n$ and $W_n$ respectively denote the path, the cycle and the wheel, all of them of order $n$. A graph is said to be connected if there always exists a path between any pair of vertices. The fan graph $F_{m, n}$ is the graph that results after joining each vertex of a set of $m$ isolated vertices with all the vertices of the path $P_n$. Further, the friendship graph $F_n$ is the graph that results after joining $n$ copies of the cycle $C_3$ with a common vertex. Figure 2 illustrates these five types of graphs.

A proper $k$-coloring of the graph $G$ is any map $c:V(G)\rightarrow \{1, \ldots, k\}$ assigning a set of $k$ labels or colors to the vertices of $V(G)$ so that no two adjacent vertices have the same color. The chromatic number $\chi(G)$ of the graph $G$ constitutes the minimum positive integer $k$ for which such a graph has a proper $k$-coloring. A particular example of both concepts are the so-called $r$-dynamic proper $k$-coloring and $r$-dynamic chromatic number $\chi_r(G)$ of a graph $G$, which have already been described in the preliminary section (see (1.1)). In particular, $\chi_1(G) = \chi(G)$. In the original manuscript of Montgomery ^[19], he established the following results.

Lemma 1. ^[19] Let $G$ be a graph and let $r$ be a positive integer. Then, the following results hold.

Lemma 2. ^[19] Let $n, r$ be two positive integers such that $n > 2$ and $r\geq 2$. Then,

Furthermore, it is also known the $r$-dynamic chromatic number of certain graphs.

Lemma 3. ^[27] Let $m, n, r$ be three positive integers. The following results hold.

a) $\chi_r(K_n) = n$.

b) If $2\leq m\leq n$, then $\chi_r(K_{m, n}) = \min\{2r, m+n, m+r\}$.

Finally, concerning the $r$-dynamic chromatic number of a corona product of graphs, the following results are also known.

Theorem 4. ^[10] Let $m, n, r$ be three positive integers such that $m, n > 2$. Then,

Theorem 5. ^[10] Let $m, n, r$ be three positive integers such that $m, n > 2$. Then,

Theorem 6. ^[10] Let $m, n, r$ be three positive integers such that $m, n > 2$. Then,

3.   Some preliminary lemmas

In this section, we establish a series of preliminary lemmas that are later used in our study. Our first result shows that the $r$-dynamic chromatic number of a subdivision-edge corona $G\ominus H$ is lower bounded by that one of the graph $H$.

Lemma 7. Let $G$ and $H$ be two simple, finite and connected graphs, and let $r$ be a positive integer. The following results hold.

a) $\chi(H) < \chi_r(G\ominus H)$.

b) If $r > 1$, then, $\chi_{r-1}(H) < \chi_r(G\ominus H)$.

Proof. Let $k = \chi_r(G\ominus H)$ and let $H_i$ be the $i^{\mathrm{th}}$ copy of the graph $H$, whose vertices are all of them joined with the $i^{\mathrm{th}}$ vertex of the set $I(G)$ within the subdivision-edge corona $G\ominus H$. The first assertion holds readily from the fact that, in any $r$-dynamic proper $k$-coloring of the graph $G\ominus H$, this $i^{\mathrm{th}}$ vertex in $I(G)$ must be colored in a different way from all the vertices of the graph $H_i$.

Further, in order to prove the second assertion, it is enough to see that $\chi_{r-1}(H_i) < \chi_r(G\ominus H)$. To this end, let $c:V(G\ominus H)\rightarrow \{1, \ldots, k\}$ be an $r$-dynamic proper $k$-coloring of the subdivision-edge corona $G\ominus H$ satisfying Condition (1.1). In particular, the restriction of the map $c$ to the subset $V(H_i)$ is a proper $(k-1)$-coloring of the graph $H_i$. Notice to this end that, at least, the color of the $i^{\mathrm{th}}$ vertex of the set $I(G)$ is not used in such a restriction. Moreover, if $v\in V(H_i)$, then $|c(N_{G\ominus H}(v))|\geq \min\{r, d_{G\ominus H}(v)\}$. Thus, since $d_{H_i}(v) = d_{G\ominus H}(v)-1$, we have that

Hence, the restriction of the map $c$ to the subset $V(H_i)$ constitutes indeed an $(r-1)$-dynamic proper $(k-1)$-coloring of the graph $H_i$. As a consequence, $\chi_{r-1}(H_i) < \chi_r(G\ominus H)$.

Let $n > 2$ be a positive integer and let $G$ be a simple, finite and connected graph. From here on, we suppose that:

● $P_n = \langle\, v_1, \ldots, v_n\, \rangle$.

● $I(P_n) = \{u_1, \ldots, u_{n-1}\}$. That is, $\{v_iu_i, u_iv_{i+1}\}\subset E(S(P_n))$, for all $1\leq i < n$.

● $x_{i, j}$ denotes the copy of each vertex $x_j\in V(G)$ in the $i^{\mathrm{th}}$ copy of the graph $G$. It is joined to the vertex $u_i\in I(P_n)$.

The following result holds.

Lemma 8. Let $r, n$ be two positive integers such that $n > 2$ and let $G$ be a simple and connected graph of order $m\geq 2$. Then,

Proof. Since $G$ is a simple and connected graph of order $m\geq 2$, one always can find a pair of distinct vertices $x_j, x_{j'}\in V(G)$ such that $x_ix_j\in E(G)$. Then, the result follows straightforwardly from the definition of the subdivision-edge corona $P_n \ominus G$. Notice to this end that each set of vertices $\{u_i, x_{i, j}, x_{i, j'}\}\subset V(P_n\ominus G)$, together with their corresponding edges, constitutes a complete subetaaph $K_3$ of both graphs $P_n\ominus G$ and $P_n\odot G$, and recall that $\chi(K_3) = 3$.

We focus now on the relationship between the $r$-dynamic chromatic numbers of both the subdivision-edge corona $P_{n+1}\ominus G$ and the corona product $P_n\odot G$.

Lemma 9. Let $r, n$ be two positive integers such that $n > 2$ and let $G$ be a finite graph. Then,

Proof. Firstly, notice that the corona product $P_n\odot G$ may be seen as a subetaaph of the subdivision-edge corona $P_{n+1}\ominus G$. To see it, we consider the following two steps.

1. We define the path $\overline{P_n}: = \langle\, u_0, v_1, u_1, v_2, \ldots, v_{n-1}, u_{n-1}, v_n, u_n\, \rangle$ that results after adding two new edges $u_0v_1$ and $v_nu_n$ to the subdivision graph $S(P_n)$.

2. The subdivision-edge corona $P_{n+1}\ominus G$ results from replacing the center graph $P_n$ of the corona product $P_n\odot G$ by the new path $\overline{P_n}$. More specifically, the vertices $v_i$ are placed in the same position that they were. That is, all the edges joining the center and the outer graphs $G$ are preserved.

Now, let $k = \chi_r(P_n\odot G)$ and let $c:V(P_n\odot G)\rightarrow\{1, \ldots, k\}$ be an $r$-dynamic proper $k$-coloring of the corona product $P_n\odot G$ satisfying Condition (1.1). From this map, it is possible to define an $r$-dynamic proper $k$-coloring $\overline{c}$ of the subdivision-edge corona $P_{n+1}\ominus G$ satisfying also Condition (1.1). Notice to this end that, according to our construction, each vertex $x_{i, j}$ is adjacent to the vertex $v_i$ in the subdivision-edge corona $P_{n+1}\ominus G$. Then, let us consider the map $\overline{c}:V(P_{n+1}\ominus G)\rightarrow\{1, \ldots, k\}$ such that

This repetitive distribution of colors throughout the graph $P_{n+1}\ominus G$, together with the fact that the map $c$ holds Condition (1.1), enables us to ensure that such a condition is also satisfied by the map $\overline{c}$, and hence, the result holds.

4.   Dynamic coloring of subdivision-edge coronas of a path

In this section, we study separately the $r$-dynamic chromatic number of the subdivision-edge corona of a path $P_n$ with each one of the following nine types of graphs: a path $P_m$, a cycle $C_m$, a wheel $W_m$, a complete graph $K_m$, a complete bipartite graph $K_{m, t}$, a star $K_{1, m}$, a double star $K_{1, m, m}$, a fan graph $F_{1, m}$ and a friendship graph $F_m$. Throughout all the section, we use the following notation.

● $P_n = \langle\, v_1, \ldots, v_n\, \rangle$.

● $I(P_n) = \{u_1, \ldots, u_{n-1}\}$. That is, $\{v_iu_i, u_iv_{i+1}\}\subset E(S(P_n))$, for all $1\leq i < n$.

Moreover, for each graph $G\in\{P_m, C_m, W_m, K_m, K_{m, t}, K_{1, m}, K_{1, m, m}, F_{1, m}, F_m\}$, all the $r$-dynamic proper colorings $c:V(P_n\ominus G)\rightarrow \{1, 2, 3, \ldots\}$ described throughout the different proofs of this section satisfy that the first three colors $1$, $2$ and $3$ are sequential and repetitively assigned to the vertices $v_1$, $u_1$, $v_2$, $\ldots$, $u_{n-1}$ and $v_n$. That is,

Let us start with the path $P_m$, the cycle $C_m$ and the wheel $W_m$.

Theorem 10. Let $m, n, r$ be three positive integers such that $m, n > 2$. Then,

Proof. From Lemma 8 and Condition (2.3), once it is observed that $\Delta(P_n \ominus P_m) = m+2$, we have that

Then, the result holds readily from Theorem 4 and Lemmas 8 and 9.

Theorem 11. Let $m, n, r$ be three positive integers such that $m, n > 2$. Then,

Proof. From Lemma 8, together with Condition (2.3) once it is observed that $\Delta(P_n \ominus C_m) = m+2$, we have that

In order to prove the current theorem, let us study separately each one of the cases exposed in Theorem 5. In this regard, the case $r\in\{1, 2\}$ with $m$ even, the case $r = 3$ and $m = 3k$, for some $k\geq 1$, and both cases concerning $r\geq 4$ follow straightforwardly from the previous lower bound together with Theorem 5 and Lemma 9. Figure 3 illustrates the case $m = n = r = 3$.

Let us study separately the remaining three cases.

● Case $r\in\{1, 2\}$ and $m$ odd.

From the above mentioned results, we have that $\chi_{r}(P_n \ominus C_m)\in\{3, 4\}$. Nevertheless, Lemma 7 implies that the best lower bound is not possible, because $\chi(C_m) = 3$. Hence, $\chi_r(P_n \ominus C_m) = 4$.

● Case $r = 3$ and $m = 5$.

Based on Lemmas 2 and 7, together with Theorem 5, we have that $\chi_3(P_n \ominus C_5) = 6$.

● Case $r = 3$ and $5\neq m\neq 3k$, for some $k\geq 1$.

Again, based on Lemmas 2 and 7, together with Theorem 5, we have that $\chi_3(P_n \ominus C_m) = 5$.

Theorem 12. Let $m, n, r$ be three positive integers such that $m, n > 2$. Then,

Proof. The result follows similarly to the proof of Theorem 11, once it is observed that $\chi_r(W_m) = \chi_r(C_m)+1$.

Let us focus now on the complete graph $K_m$ and the complete bipartite graph $K_{m, t}$.

Theorem 13. Let $m, n, r$ be three positive integers such that $n > 2$. Then,

Proof. From Lemmas 3 and 7, we have that $m = \chi(K_m) < \chi_{r}(P_n \ominus K_m)$. Moreover, since $\Delta(P_n \ominus C_m) = m+2$, we have from Condition (2.3) that

In order to prove that all these lower bounds are fitted, let us define an appropriate $r$-dynamic proper coloring $c : V\left(P_n \ominus K_m\right) \rightarrow \left\{1, 2, \ldots\right\}$ satisfying Condition (4.1) for each one of the three cases described in the hypothesis. To this end, we suppose that $x_{i, j}$ denotes the copy of each vertex $x_j\in V(K_m)$ in the $i^{\mathrm{th}}$ copy of the graph $K_m$. It is joined to the vertex $u_i\in I(P_n)$.

● Case $1 \leq r < m+1$.

Let $c : V\left(P_n \ominus K_m\right) \rightarrow \left\{1, 2, \ldots, m+1\right\}$ satisfying that all the $m$ colors different from $c(u_i)$ are assigned to the vertices of the $i^{\mathrm{th}}$ copy of the complete graph $K_m$. Then, Condition (1.1) holds and hence, $\chi_r(P_n \ominus K_m) = m+1$.

● Case $r = m+1$.

Let $c : V\left(P_n \ominus K_m\right) \rightarrow \left\{1, 2, \ldots, m+2\right\}$ satisfying that all the $m$ colors different from both $c(v_i)$ and $c(u_i)$ are assigned to the vertices of the $i^{\mathrm{th}}$ copy of the complete graph $K_m$. Then, Condition (1.1) holds and hence, $\chi_r(P_n \ominus K_m) = m+2$. Figure 4 illustrates the case $n = 3$, $m = 4$ and $r = 5$.

● Case $r \geq m+2$.

Let $c : V\left(P_n \ominus K_m\right) \rightarrow \left\{1, 2, \ldots, m+2\right\}$ satisfying that all the $m$ colors in the set $\{4, 5, \ldots, m+3\}$ are assigned to the vertices of the $i^{\mathrm{th}}$ copy of the complete graph $K_m$. Then, Condition (1.1) holds and hence, $\chi_r(P_n \ominus K_m) = m+3$.

Theorem 14. Let $m, n, r, t$ be four positive integers such that $2\leq m\leq t$ and $n\geq 3$. Then,

Proof. From Lemmas 3, 7 and 8, together with Condition (2.3) once it is observed that $\Delta(P_n \ominus K_{m, t}) = m+t+2$, we have that all the expressions in the hypothesis are lower bounds of $\chi_{r}(P_n \ominus K_{m, t})$. In order to prove that all of them are fitted, we define an $r$-dynamic proper coloring $c : V\left(P_n \ominus K_{m, t}\right) \rightarrow \left\{1, 2, \ldots\right\}$ satisfying Condition (4.1) for each one of the cases. To this end, let us suppose that the vertices of the graph $K_{m, t}$ are distributed into the sets

with

Moreover, let $V_{1, i}$ and $V_{2, i}$ respectively denote the copies of the sets $V_1$ and $V_2$ in the $i^{\mathrm{th}}$ copy of the graph $K_{m, t}$, for all $i\in\{1, \ldots, n\}$. All these vertices are joined to the vertex $u_i\in I(P_n)$.

● Case $r\in\{1, 2\}$.

Let $c : V\left(P_n \ominus K_{m, t}\right) \rightarrow \left\{1, 2, 3\right\}$ satisfying that the two colors different from $c(u_i)$ are respectively assigned to all the vertices in $V_1$ and $V_2$. Then, Condition (1.1) holds and hence, $\chi_r(P_n \ominus K_{m, t}) = 3$.

● Case $3 \leq r < m$.

Let $c : V\left(P_n \ominus K_{m, t}\right) \rightarrow \left\{1, 2, \ldots, 2r-1\right\}$ be such that the following conditions hold.

- All the $r-1$ colors in the set $\{1, 2, \ldots, r\}\setminus\{c(u_i)\}$ are assigned to the set $V_{1, i}$.

- All the $r-1$ colors in the set $\{r+1, r+2, \ldots, 2r-1\}$ are assigned to the set $V_{2, i}$.

Then, Condition (1.1) holds and hence, $\chi_r(P_n \ominus K_{m, t}) = 2r-1$.

● Case $m\leq r < t$.

Let $c : V\left(P_n \ominus K_{m, t}\right) \rightarrow \left\{1, 2, \ldots, m+r\right\}$ be such that the following conditions hold.

- All the $m$ colors in the set $\{1, 2, \ldots, m+1\}\setminus\{c(u_i)\}$ are assigned to the set $V_{1, i}$.

- All the $r-1$ colors in the set $\{m+2, m+3, \ldots, m+r\}$ are assigned to the set $V_{2, i}$.

Then, Condition (1.1) holds and hence, $\chi_r(P_n \ominus K_{m, t}) = m+r$.

● Case $t\leq r < m+t$.

Let $c : V\left(P_n \ominus K_{m, t}\right) \rightarrow \left\{1, 2, \ldots, m+t+1\right\}$ be such that the following conditions hold.

- All the $m$ colors in the set $\{1, 2, \ldots, m+1\}\setminus\{c(u_i)\}$ are assigned to the set $V_{1, i}$.

- All the $t$ colors in the set $\{m+2, m+3, \ldots, m+t+1\}$ are assigned to the set $V_{2, i}$.

Then, Condition (1.1) holds and hence, $\chi_r(P_n \ominus K_{m, t}) = m+t+1$. Figure 5 illustrates the case $m = 2$, $n = t = 3$ and $r = 4$.

● Case $m+t\leq r < m+t+2$.

Let $c : V\left(P_n \ominus K_{m, t}\right) \rightarrow \left\{1, 2, \ldots, r+1\right\}$ be such that the following conditions hold.

- All the $m$ colors in the set $\{1, 2, \ldots, m+2\}\setminus\{c(v_i), c(u_i)\}$ are assigned to the set $V_{1, i}$.

- All the $r-m-1$ colors in the set $\{m+3, m+4, \ldots, r+1\}$ are assigned to the set $V_{2, i}$.

Then, Condition (1.1) holds and hence, $\chi_r(P_n \ominus K_{m, t}) = r+1$.

● Case $r \geq m+t+2$.

Let $c : V\left(P_n \ominus K_{m, t}\right) \rightarrow \left\{1, 2, \ldots, m+t+3\right\}$ be such that the following conditions hold.

- All the $m$ colors in the set $\{4, 5, \ldots, m+3\}$ are assigned to the set $V_{1, i}$.

- All the $t$ colors in the set $\{m+4, m+5, \ldots, m+t+3\}$ are assigned to the set $V_{2, i}$.

Then, Condition (1.1) holds and hence, $\chi_r(P_n \ominus K_{m, t}) = m+t+3$.

Let us focus now on the star $K_{1, m}$ and the double star $K_{1, m, m}$.

Theorem 15. Let $m, n, r$ be three positive integers such that $m, n > 2$. Then,

Proof. From Lemma 8 and Condition (2.3), once it is observed that $\Delta(P_n \ominus K_{1, m}) = m+3$, all the expressions in the hypothesis are lower bounds of $\chi_{r}(P_n \ominus K_{1, m})$. In order to prove that all of them are fitted, we define an appropriate $r$-dynamic proper coloring $c : V\left(P_n \ominus K_{1, m}\right) \rightarrow \left\{1, 2, \ldots\right\}$ satisfying Condition (4.1) for each one of the cases. To this end, let us suppose that

and

Moreover, let $x_i$ and $y_{i, j}$ respectively denote the copies of the vertices $x$ and $y_j$ in the $i^{\mathrm{th}}$ copy of the graph $K_{1, m}$. All these vertices are joined to the vertex $u_i\in I(P_n)$.

● Case $r\in\{1, 2\}$.

Let $c : V\left(P_n \ominus K_{1, m}\right) \rightarrow \left\{1, 2, 3\right\}$ be such $c(x_i) = c(v_{i+1})$ and $c(y_{i, j}) = c(v_i)$, for all $1\leq i\leq n$ and $1\leq j\leq m$. Then, Condition (1.1) holds and hence, $\chi_r(P_n \ominus K_{1, m}) = 3$.

● Case $3\leq r < m+3$.

Let $c : V\left(P_n \ominus K_{1, m}\right) \rightarrow \left\{1, 2, \ldots, r+1\right\}$ be such $c(x_i) = c(v_{i+1})$ and all the $r-1$ colors in the set $\{c(v_i), 4, 5, \ldots, r+1\}$ are assigned to the set of vertices $\{y_{i, 1}, \ldots, y_{i, m}\}$. Then, Condition (1.1) holds and hence, $\chi_r(P_n \ominus K_{1, m}) = r+1$. Figure 6 illustrates the case $m = n = 3$ and $r = 4$.

● Case $r\geq m+3$.

Let $c : V\left(P_n \ominus K_{1, m}\right) \rightarrow \left\{1, 2, \ldots, m+4\right\}$ be such $c(x_i) = 4$ and all the $m$ colors in the set $\{5, 6, \ldots, m+4\}$ are assigned to the set of vertices $\{y_{i, 1}, \ldots, y_{i, m}\}$. Then, Condition (1.1) holds and hence, $\chi_r(P_n \ominus K_{1, m}) = m+4$.

Theorem 16. Let $m, n, r$ be three positive integers such that $m, n > 2$. Then,

Proof. From Lemma 8, together with Condition (2.3) once it is observed that $\Delta(P_n \ominus K_{1, m, m}) = 2m+3$, we have that all the expressions in the hypothesis are lower bounds of $\chi_{r}(P_n \ominus K_{1, m, m})$. In order to prove that all of them are fitted, let us define an appropriate $r$-dynamic proper coloring $c : V\left(P_n \ominus K_{1, m, m}\right) \rightarrow \left\{1, 2, \ldots\right\}$ satisfying Condition (4.1) for each one of the cases. To this end, let us suppose that

and

Moreover, let $x_i$, $y_{i, j}$ and $z_{i, j}$ respectively denote the copies of the vertices $x$, $y_j$ and $z_j$ in the $i^{\mathrm{th}}$ copy of the graph $K_{1, m, m}$. All these vertices are joined to the vertex $u_i\in I(P_n)$.

● Case $r\in\{1, 2\}$.

Let $c : V\left(P_n \ominus K_{1, m, m}\right) \rightarrow \left\{1, 2, 3\right\}$ be such that $c(x_i) = c(z_{i, j}) = c(v_{i+1})$ and $c(y_{i, j}) = c(v_i)$, for all $1\leq i\leq n$ and $1\leq j\leq m$. Then, Condition (1.1) holds and hence, $\chi_r(P_n \ominus K_{1, m, m}) = 3$.

● Case $3 \leq r < 2m+3$.

Let $c : V\left(P_n \ominus K_{1, m, m}\right) \rightarrow \left\{1, 2, \ldots, r+1\right\}$ be such $c(x_i) = c(v_{i+1})$ and the following conditions hold.

- If $3 \leq r < m+2$, then all the $r-1$ colors in the set $\{c(v_i), 4, 5, \ldots, r+1\}$ are assigned to both sets of vertices $\{y_{i, 1}, \ldots, y_{i, m}\}$ and $\{z_{i, 1}, \ldots, z_{i, m}\}$ so that $c(y_{i, j})\neq c(z_{i, j})$, for all $1\leq j\leq m$.

- If $m+2 \leq r < 2m+2$, then

* all the $m$ colors in the set $\{c(v_i), 4, 5, \ldots, m+2\}$ are assigned to the set of vertices $\{y_{i, 1}, \ldots, y_{i, m}\}$; and

* all the $r-m-1$ colors in the set $\{m+3, m+4, \ldots, r+1\}$ are assigned to the set of vertices $\{z_{i, 1}, \ldots, z_{i, m}\}$.

Figure 7 illustrates the case $m = n = 3$ and $r = 6$.

- If $r = 2m+2$, then

* all the $m$ colors in the set $\{4, 5, \ldots, m+3\}$ are assigned to the set of vertices $\{y_{i, 1}, \ldots, y_{i, m}\}$; and

* all the $r-m-2$ colors in the set $\{m+4, m+5, \ldots, r+1\}$ are assigned to the set of vertices $\{z_{i, 1}, \ldots, z_{i, m}\}$.

Then, Condition (1.1) holds and hence, $\chi_r(P_n \ominus K_{1, m, m}) = r+1$.

● Case $r \geq 2m+3$.

Let $c : V\left(P_n \ominus K_{1, m, m}\right) \rightarrow \left\{1, 2, \ldots, 2m+4\right\}$ be such $c(x_i) = 4$, for all $1\leq i\leq n$, and the following conditions hold.

- All the $m$ colors in the set $\left\{5, 6, \ldots, m+4\right\}$ are assigned to the set of vertices $\{y_{i, 1}, \ldots, y_{i, m}\}$.

- All the $m$ colors in the set $\left\{m+5, m+6, \ldots, 2m+4\right\}$ are assigned to the set of vertices $\{z_{i, 1}, \ldots, z_{i, m}\}$.

Then, Condition (1.1) holds and hence, $\chi_r(P_n \ominus K_{1, m, m}) = 2m+4$.

Let us study now the fan graph $F_{1, m}$.

Theorem 17. Let $m, n, r$ be three positive integers such that $m, n > 2$. Then,

Proof. Let us suppose that

and

Moreover, let $x_i$ and $y_{i, j}$ respectively denote the copies of the vertices $x$ and $y_j$ in the $i^{\mathrm{th}}$ copy of the graph $F_{1, m}$. All these vertices are joined to the vertex $u_i\in I(P_n)$. Notice in particular that, for all $i\in\{1, \ldots, n\}$, the set of vertices $\{u_i, x_i, y_{i, j}, y_{i, j'}\}\subset V(P_n\ominus F_{1, m})$ with their corresponding edges constitute a complete subetaaph $K_4$ of the graph $P_n\ominus F_{1, m}$. Then, $4 = \chi(K_4)\leq \chi_r(P_n\ominus F_{1, m})$. Furthermore, from Condition (2.3), once it is observed that $\Delta(P_n \ominus F_{1, m}) = m+3$, we have that

In order to prove that all these lower bounds are fitted, we define separately an appropriate $r$-dynamic proper coloring $c : V\left(P_n \ominus F_{1, m}\right) \rightarrow \left\{1, 2, \ldots\right\}$ satisfying Condition (4.1) for each one of the cases.

● Case $r\in\{1, 2, 3\}$.

Let $c : V\left(P_n \ominus F_{1, m}\right) \rightarrow \left\{1, 2, 3, 4\right\}$ be such that $c(x_i) = c(v_{i+1})$ and both colors in the set $\{c(v_i), 4\}$ are assigned to the set of vertices $\{y_{i, 1}, \ldots, y_{i, m}\}$. Then, Condition (1.1) holds and hence, we have that $\chi_r(P_n \ominus F_{1, m}) = 4$.

● Case $4 \leq r < m+3$.

Let $c : V\left(P_n \ominus F_{1, m}\right) \rightarrow \left\{1, 2, \ldots, r+1\right\}$ be such that $c(x_i) = c(v_{i+1})$ and the following conditions hold.

- If $4 \leq r < m+2$, then all the $r-1$ colors in the set $\{c(v_i), 4, 5, \ldots, r+1\}$ are assigned to the set of vertices $\{y_{i, 1}, \ldots, y_{i, m}\}$. Figure 8 illustrates the case $m = n = 3$ and $r = 4$.

- If $r = m+2$, then all the $r-2$ colors in the set $\{4, 5, \ldots, r+1\}$ are assigned to the set of vertices $\{y_{i, 1}, \ldots, y_{i, m}\}$.

Then, Condition (1.1) holds and hence, $\chi_r(P_n \ominus F_{1, m}) = r+1$.

● Case $r\geq m+3$.

Let $c : V\left(P_n \ominus F_{1, m}\right) \rightarrow \left\{1, 2, \ldots, m+4\right\}$ be such $c(x_i) = 4$ and all the $m$ colors in the set $\{5, 6, \ldots, m+4\}$ are assigned to the set of vertices $\{y_{i, 1}, \ldots, y_{i, m}\}$. Then, Condition (1.1) holds and hence, $\chi_r(P_n \ominus F_{1, m}) = m+4$.

In a very similar way to the proof of Theorem 17, the following result concerning a friendship graph holds.

Theorem 18. Let $m, n, r$ be three positive integers such that $m, n > 2$. Then,

Figure 9 illustrates the case $m = n = 3$ and $r = 6$.

5.   Conclusion and further works

In this paper, we have established the $r$-dynamic chromatic number of the subdivision-edge corona $P_n\ominus G$ of a path $P_n$ and a graph $G$ of one of the following nine types: a path, a cycle, a wheel, a complete graph, a complete bipartite graph, a star, a double star, a fan graph or a friendship graph. In case of considering the graph $G$ to be a path, a cycle or a wheel, it has been proven that this number coincides with the corresponding $r$-dynamic chromatic number of the corona product $P_n\odot G$. It is established as further work the study of such a relationship among the $r$-dynamic chromatic numbers of both graphs $P_n\ominus G$ and $P_n\odot G$, not only for the rest of considered types, but also for any graph $G$. Lemma 9 may be an interesting starting point to deal with this aspect.

Notice also that all the results here exposed concerning $r$-dynamic coloring of the subdivision-edge corona of two given graphs may be generalized for the more general concept of list dynamic coloring of a graph ^[30], which has already been mentioned in the introductory section. We also establish this generalization as further work.}

Acknowledgments

Falcón's work is partially supported by the research project FQM-016 from Junta de Andalucía, and the Departmental Research Budget of the Department of Applied Mathematics I of the University of Seville.

Conflict of interest

The authors declare no conflict of interest.