Optimal secret share distribution in degree splitting communication networks

1.   Introduction

A $(k, t)$-threshold secret sharing scheme ^[1,2], with $k\geq t$, is a cryptographic protocol in which a dealer splits a secret into $k$ pieces of information or secret shares. Copies of these pieces are distributed among a group of $n$ participants, with $n\geq t$, so that only a subgroup sharing at least $t$ distinct secret shares can reconstruct the secret. The parameter $t$ is called the threshold of the scheme. These schemes are relevant in online storage and cloud computing because they enforce data security in communication networks ^[3], in which each node represents a participant of the scheme. Two nodes are adjacent if and only if there exists a proximity relationship between both participants so that they can cooperate to recover the original secret. This cooperation occurs simultaneously via discrete time-steps or rounds of communication that allow the spread of secret shares among all the nodes of the network. First, the dealer distributes the secret shares among the nodes of the network. In each subsequent round, each participant gathers all the pieces of information of the adjacent nodes and fuses them with its own information. Moreover, we suppose in this paper the following assumptions.

● Exactly one secret share is assigned by the dealer to each participant, so that no two adjacent nodes receive the same piece of information. To this end, the dealer has secure communication links to every participant. We also assume that the secret cannot be recovered from this initial distribution. That is, $t > 1$ in our $(k, t)$-threshold secret sharing scheme.

● The communication network is static. That is, its topology does not change during the rounds of communication.

Figure 1 illustrates these rounds of communications for a static network of $12$ nodes, among which the dealer has distributed four distinct pieces of information.

A main question to answer here is the following.

Problem 1. What is the minimum number of rounds that are necessary so that the original secret can be reconstructed by each one of the participants?

Of course, this number is less than or equal to the diameter of the graph under consideration. The exact solution of Problem 1 requires the design of an efficient and optimal distribution of secret shares among all the participants of the communication network. It requires a comprehensive analysis of the network topology and metrics ^[4], which would be even more relevant when the communication network under consideration is large enough to be considered for big data storage. Even if different analytic tools based on graph algorithms are usually used to this end ^[5,6,7], the most relevant tool for dealing with our problem is graph coloring.

A proper $n$-coloring of a graph $G$, with a set of vertices $V(G)$, is any map $c:V(G)\rightarrow \{0, \ldots, n-1\}$ such that $c(v)\neq c(w)$, for every pair of adjacent vertices $v, w\in V(G)$. The minimum positive integer $n$ for which this map exists is the chromatic number $\chi(G)$. If $G$ is the underlying graph of a communication network, then each color can be interpreted as the secret share assigned to the node under consideration. Hence, Problem 1 requires the design of an appropriate coloring for the graph $G$.

Depending on different local constraints, one may find in the literature a wide amount of distinct types of graph colorings ^[8,9], with different applications in real-world problems ^[10]. Thus, for instance, the $b$-coloring is useful to deal with clustering in data mining ^[11]; the equitable coloring ensures load balancing in scheduling ^[12]; the frugal coloring avoid collisions in networks based on a time-division multiple access ^[13]; the rainbow $k$-connected edge-coloring enables the strengthening of the conventional connectivity to get a much more secure network communication ^[14]; and the star coloring is useful in tracebacking IP addresses in communication networks ^[15].

Dynamic coloring has recently emerged ^[16] as a valuable type of proper-coloring that allows for the description of optimal distributions of pieces of information in a secret sharing scheme defined on a communication network. In 2001, Montgomery ^[17] introduced the $r$-dynamic proper $k$-coloring of a graph $G$ as a proper $k$-coloring $c:V(G)\rightarrow \{0, \ldots, k-1\}$ such that

for every vertex $v\in V(G)$. Here, $N_G(v)$ and $\mathrm{deg}_G(v)$ denote, respectively, the neighborhood and the degree of the vertex $v$. The problem of deciding whether a given graph has an $r$-dynamic proper $k$-coloring is NP-complete ^[18], whenever $2\leq r < k$. It is indeed harder than the classical coloring problem, which results for $r = 1$, and is a well known NP-complete problem, for $k > 2$. In this regard, even the classical $3$-colorability is polynomially solvable for graphs with maximum degree at most three, and the $2$-dynamic $3$-colorability remains NP-complete for planar bipartite graphs with maximum degree at most three and arbitrarily high girth ^[18].

Every $r$-dynamic $k$-proper coloring of a graph $G$ describes a distribution of pieces of information in any given $(k, r+1)$-threshold secret sharing scheme defined on the communication network having $G$ as its underlying graph, whenever $k\geq r+1$ ^[16]. This distribution makes possible that all the participants receive the maximum possible information about the original secret from the closest nodes after each round of communication. More precisely, condition (1.1) implies that, after the first round, each participant can either reconstruct the original secret or obtain a different secret share from each one of his/her neighbors. A second main question to answer here is the following.

Problem 2. What is the minimum number of pieces of information in which the secret has to split to ensure condition (1.1)?

This number coincides with the $r$-dynamic chromatic number $\chi_r(G)$, which is the minimum positive integer $k$ for which an $r$-dynamic proper $k$-coloring of the graph $G$ exists. (The case $r = 1$ refers to the classical chromatic number $\chi(G)$.) Determining this number constitutes the dynamic chromatic problem. (The case $r = 1$ refers to the classical chromatic problem.) The case $r\geq 2$ has already been solved for distinct families of graphs ^{[19,20,21,22,23,24,25,26,27]}. One may also find some papers studying how the dynamic chromatic number changes by including new vertices in the graph under consideration ^{[28,29,30,31,32,33]}. (For a recent survey on the topic, we refer to ^[34].)

All the mentioned papers can, therefore, be reinterpreted as dealing with Problem 2. However, in spite of the wide amount of papers on Montgomery's dynamic coloring, its interpretation as an optimal allocation of pieces of information has only been explicitly considered in ^[16], for extended neighborhood coronas, and, too superficially, in ^[35], for triangle-free graphs and sparse random graphs. Even more, Problem 1 has been solved only for extended neighborhood coronas ^[16]. More specifically, two rounds of communication have been proved to be enough so that all the participants in any extended neighborhood corona can reconstruct the secret under consideration in the corresponding communication network.

Similarly to Problem 2, it is interesting to study the behaviour of Problem 1 when new vertices are included in the graph under consideration. This paper delves into this aspect for both Problems 1 and 2, in case of dealing with degree splitting graphs. Recall here that, if $G$ is a graph of set of vertices $V(G) = \{v_1, \ldots, v_n\}$, and $V_k(G)\subseteq V(G)$ denotes its subset of vertices of degree $k$ for all $k > 1$, then the degree splitting graph ^[36] (from here on, DSG) of $G$ is the graph $DS(G)$ that results after connecting a new vertex to all those vertices in $V_k(G)$, whenever $|V_k(G)| > 1$. From here on, we denote this new vertex by $w_k$, and we say that it constitutes a control node of the initial network. Figure 2 illustrates this construction for the communication graph appearing in Figure 1. (The control nodes are highlighted in black color.)

No previous study exists in the literature concerning the dynamic chromatic problem for DSGs. The main reason for having chosen this type of graphs in our study is that DSGs maintain or improve the fairness of any given secret sharing scheme based on a communication network, by avoiding dishonesty. Recall here that a secret sharing scheme is fair if all the participants recover the original secret at the same time. Of course, the more regular the communication network is, the fairer the secret sharing scheme can be. But, even in the regular case, this fairness cannot be ensured in case there are dishonest participants who receive secret shares from the honest ones, but either do not share their own pieces of information, or share fake ones. To avoid this dishonesty, one can add control nodes connecting and supervising all those participants with a similar influence in the network. DSGs constitute a valuable alternative to this end, where control nodes are the new added vertices. Note that the DSG of any regular graph has diameter at most two. Hence, at most two rounds of communication are required so that all the participants can reconstruct the secret in the DSG of any regular communication network.

From here on, we assume that control nodes also receive secret shares so that condition (1.1) holds. So, we are interested in solving Problem 2 for DSGs. Even more, we assume that control nodes act in all the rounds of communication of the scheme, in exactly the same way as the rest of participants. We can distinguish whether control nodes are also participants of the scheme, or not. (This distinction is further clarified in Section 2.) In the affirmative case, we are interested in answering Problem 1 for any $\left(\chi_r\left(\mathrm{DS}(G)\right), \, r+1\right)$-threshold secret sharing scheme based on the DSG of a graph $G$, whenever $\chi_r\left(\mathrm{DS}(G)\right)\geq r+1$. In the negative case, we are interested in solving the following alternative question, whose solution is less than or equal to that of Problem 1 for both graphs $G$ and $\mathrm{DS}(G)$.

Problem 3. What is the minimum number of rounds of communication that is necessary so that all the participants, except for the control nodes, can recover the secret in a $\left(\chi_r\left(\mathrm{DS}(G)\right), \, r+1\right)$-threshold secret sharing scheme based on the DSG of a communication network $G$?

1.1.   Our contributions

In this paper, we solve Problem 2, and hence, the dynamic chromatic problem, for DSGs of regular graphs (Proposition 7) by determining the relationship among the dynamic chromatic number of a regular graph and that of its DSG. We illustrate this by solving the dynamic chromatic problem for DSGs of two families of regular graphs: cycles (Theorem 8) and cocktail party graphs (Theorem 10). With respect to the latter, we also correct (Lemma 9) a previous result on the classical dynamic chromatic problem. All our constructive solutions describe explicitly dynamic colorings on the graphs under consideration, and hence, optimal secret share distributions. It allows the establishment of the minimum number of rounds of communications that are necessary so that all the participants of a communication network defined on such graphs can reconstruct the secret. To this end, we distinguish whether the control nodes described by any DSG are also participants of the scheme (Problem 1), or not (Problem 3). In Section 3, we solve both problems for DSGs of cycles and cocktail party graphs.

Concerning DSGs of non-regular graphs, we solve Problems 1–3 for the DSGs of book graphs (Proposition 11), comb graphs (Proposition 12), fan graphs (Theorems 14 and 15) and jellyfish graphs (Propositions 16 and 17). In addition, we establish a new lower bound for the dynamic chromatic number of the DSGs of any non-regular graph (Lemma 18). We use this bound to solve Problems 1–3 for the DSGs of windmill graphs (Proposition 19) and barbell graphs (Proposition 20). Table 2 summarizes all our results concerning Problems 1 and 3.

2.   Preliminaries

This section deals with some preliminary concepts and results on graph theory that are used throughout the paper. We refer the reader to the manuscript ^[37] for more details about this topic.

All the communication networks throughout the paper are assumed to be finite and simple graphs. A graph $G = (V(G), E(G))$ is formed by a set of vertices $V(G)$ and a set of edges $E(G)$ so that each edge joins two vertices, which are then said to be adjacent. The graph $G$ is complete if all their vertices are pairwise adjacent. The complete graph with $n$ vertices is denoted $K_n$. Further, a graph $H = (V(H), E(H))$ is a subgraph of $G$ if $V(H)\subseteq V(G)$ and $E(H)\subseteq E(G)$. It is induced if $E(H)$ is formed by all those edges in $E(G)$ connecting vertices of $V(H)$. It is an $n$-clique if it coincides with $K_n$.

The cardinalities of the sets $V(G)$ and $E(G)$ constitute, respectively, the order and the size of the graph $G$. The latter is finite if both its order and its size are finite. From now on, let $vw$ denote the edge formed by two adjacent vertices $v, w\in V(G)$. It is a loop if $v = w$. A graph is simple if it does not contain loops. All the graphs in this paper are finite and simple.

The neighborhood of a vertex $v\in V(G)$ is the subset $N_G(v)\subset V(G)$ of vertices that are adjacent to $v$. The cardinality of this set is the degree $\mathrm{deg}_G(v)$ of such vertex. If $\mathrm{deg}_G(v) = 1$, then the vertex $v$ is said to be pendant. The maximum degree in $G$ is denoted $\Delta(G)$. A graph is said to be $k$-regular (or simply, regular), if all its vertices have degree $k$.

A path between two vertices $v, w\in V(G)$ is any ordered sequence of $n > 2$ adjacent and pairwise distinct vertices $\langle\, v_0 = v, v_1, \ldots, v_{n-2},$ $v_{n-1} = w\, \rangle$ in $V(G)$. The minimum possible size of this path is the distance $d_G(u, v)$. The diameter $\mathrm{diam}(G)$ is the maximum distance between any two vertices in $V(G)$.

A path is a cycle if its initial and final vertices coincide. If all the vertices of a cycle are joined to a new vertex, then we get a wheel. If we remove all the edges of the wheel that do not contain this new vertex, then we obtain a star. (Note that it is sometimes called a wheel network ^[38].) From here on, we denote, respectively, the cycle and the wheel of order $n$ by $C_n$ and $W_n$. Note here that $\mathrm{DS}(C_n) = W_n$.

Paths, cycles, wheels (stars) and complete graphs are four commonly used graphs in small communication networks and constitute fundamental subgraphs for more complex networks ^[38]. In this regard, we study in the subsequent sections the DSGs of the following families of graphs, which are based on the mentioned four graphs, and are usually considered in the literature as a first attempt to study more complex communication networks: cocktail party graphs ^[39], book graphs ^[40], comb graphs ^[41], fan graphs ^[39], jellyfish graphs ^[42], windmill graphs ^[43] and barbell graphs ^[44]. Let us recall here how all of them are defined. To this end, let $m$ and $n$ be two positive integers.

● The cocktail party graph $\mathrm{Cp}_{n}$, with $n > 1$, is described so that $V(\mathrm{Cp}_n) = \{v_0, \ldots, v_{2n-1}\}$ and $E(\mathrm{Cp}_n) = \{v_iv_j\colon\, 0\leq i, j < 2n, \, i\not\equiv j\, (\mathrm{mod}\, n)\}$.

● The book graph $B_n$ is formed by $n$ copies of the cycle $C_4$, sharing between all of them a unique, common edge.

● The comb graph $\mathrm{Cb}_n$, with $n > 2$, is the graph arising from connecting $n$ new vertices $v'_0, \ldots, v'_{n-1}$ to the path $P_n = \langle\, v_0, \ldots, v_{n-1}\, \rangle$ by means of the edges $v_iv'_i$, with $0\leq i < n$.

● The fan graph $F_{m, n}$ is the graph arising from connecting $m$ new vertices to all the vertices of the path $P_n$.

● The jellyfish graph $J_{m, n}$ arises from the cycle $C_4 = \langle\, v_0, v_1, v_2, v_3\, \rangle$ after joining the vertices $v_0$ and $v_2$ with an edge, connecting $m$ new pendant vertices to $v_1$, and $n$ new pendant vertices to $v_3$.

● The windmill graph $\mathrm{Wd}_{m, n}$, with $m, n \geq 2$, is the graph formed by $m$ copies of the complete graph $K_n$, sharing between all of them a unique, common vertex.

● The barbell graph $\mathrm{Ba}_n$, with $n > 2$, is the graph formed by two copies of the complete graph $K_n$ so that they are linked by an edge connecting one vertex of each copy. This edge is called the bridge of the graph $\mathrm{Ba}_n$.

Figures 3 and 4 illustrate, respectively, all of these graphs and their respective DSGs. (In Figure 4, control nodes are highlighted in black color.)

The diameters of these graphs are indicated in Table 1. Note herein that, except for fan graphs, the diameter of each DSG under consideration is smaller than the diameter of the corresponding graph. This exception is due to the fact that the distance between any two distinct control nodes in a DSG is at least three. It increases the diameter of some non-regular graphs having diameter two, as in fan graphs. In practice, this increment is a disadvantage only if control nodes are also participants of the secret sharing scheme under consideration, instead of being only added for supervising participants with a similar influence in the communication network. This is the main reason of distinguishing both Problems 1 and 3 in the introductory section. Based on this fact, the last column in Table 1 refers to the maximum distance between any two vertices in the DSG under consideration, whenever at least one of these two vertices is not a control node. We have denoted this maximum distance by $\mathrm{diam}^*(\mathrm{DS}(G))$, where $G$ is the graph under study.

The values appearing in the third and fourth columns in Table 1 constitute respective upper bounds for the solutions of Problem 1 and 3. The exact solutions are established throughout the paper, and collected in the conclusion section (see Table 2). Concerning Problem 2, the following known results are useful for our study.

Lemma 1. ^[25] Let $G$ be a finite simple graph and let $r$ be a positive integer. Then,

Moreover, $\chi_r(G)\leq\chi_{\Delta(G)}(G)$.

Lemma 2. ^[26] Let $n > 2$ and $r$ be two positive integers. Then, $\chi_r(K_n) = n$ and

Lemma 3. ^[21] Let $r$ and $m, n\geq 2$ be three positive integers. Then:

a) $\chi_r(\mathrm{Wd}_{m, n}) = \begin{cases} \begin{array}{ll} n, & \mathit{\text{if}}\ 1\leq r < n, \\ r+1, & \mathit{\text{if}}\ n\leq r\leq m(n-1), \\ m(n-1)+1, & \mathit{\text{otherwise}}. \end{array} \end{cases}$

b) If $n > 2$, then $\chi_r(\mathrm{Ba}_n) = \begin{cases} \begin{array}{ll} n, & \mathit{\text{if}}\ 1\leq r < n, \\ n+1, & \mathit{\text{otherwise}}. \end{array} \end{cases}$

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

The following lemma solves the dynamic chromatic problem for a comb graph.

Lemma 5. If $n > 2$, then $\chi_r(\mathrm{Cb}_n) = \min\left\{4, \, r+1\right\}$.

Proof. Let $\alpha = \min\left\{4, \, r+1\right\}$. Since $\Delta(\mathrm{Cb}_n) = 3$, Lemma 1 implies that $\chi_r(\mathrm{Cb}_n)\geq \alpha$. In order to prove that this lower bound is tight, let $\mathrm{Cb}_n$ be the comb graph that results after connecting $n$ new vertices $v'_0, \ldots, v'_{n-1}$ to the path $P_n = \langle\, v_0, \ldots, v_{n-1}\, \rangle$ by means of the edges $v_iv'_i$ for all $i < n$. Then, it is enough to consider the $r$-dynamic proper $\alpha$-coloring $c$ such that $c(v_i) = i\, \mathrm{mod}\, \alpha$, and

for every positive integer $i < n$. (Figure 5 illustrates the case $n = 4$.) □

Concerning the theory of DSGs, the following result establishes the relationship between the chromatic numbers of a finite simple graph and its DSG.

Lemma 6. ^[45] Let $G$ be a finite simple graph. If $G$ is regular, then $\chi(\mathrm{DS}(G)) = \chi(G)+1$. Otherwise, $\chi(\mathrm{DS}(G))\in\{\chi(G), \, \chi(G)+1\}$.

3.   The regular case

In the introductory section, we have already remarked that the DSG of a regular graph requires at most two rounds of communication so that every participant of a secret share scheme defined on this type of graph can recover the secret under consideration. In this section, we prove that this upper bound is not tight. Previously, it is required to solve Problem 2 for the DSG of any $k$-regular graph $G$ of order $n$, with vertex set $V(G) = \{v_0, \ldots, v_{n-1}\}$, so that $V(\mathrm{DS}(G)) = V(G)\cup\{w_k\}$. That is, we only add a control node $w_k$ supervising all the participants of the communication network. The following result establishes the relationship between the dynamic chromatic numbers of both graphs $G$ and $\mathrm{DS}(G)$.

Proposition 7. Let $G$ be a $k$-regular graph of order $n$. Then,

Proof. From Lemma 1, it is enough to prove the case $r\leq \Delta(\mathrm{DS}(G)) = n$. (Note here that $\max\{n, \chi_{n-1}(G)\}+1 = n+1$, because $\chi_{n-1}(G)\leq n$.) Particularly, the case $r = 1$ follows from Lemma 6. So, we focus on the case $1 < r\leq n$. To this end, let $\alpha = \max\{r, \, \chi_{r-1}(G)\}$.

Since the vertex $w_k$ is connected to every vertex in $G$, every proper coloring of $\mathrm{DS}(G)$ requires an exclusive color for $w_k$. As a consequence, the removal of this control node from $\mathrm{DS}(G)$ implies readily that every $r$-dynamic proper $\chi_r(\mathrm{DS}(G))$-coloring of $\mathrm{DS}(G)$ gives rise to an $(r-1)$-dynamic proper $\left(\chi_r(\mathrm{DS}(G))-1\right)$-coloring of $G$. Hence, $\chi_{r-1}(G)\leq \chi_r(\mathrm{DS}(G))-1$. Furthermore, since $n = \Delta(\mathrm{DS}(G))$, Lemma 1 implies that $\chi_r(\mathrm{DS}(G))\geq r+1$. As a consequence, $\chi_r(\mathrm{DS}(G))\geq\alpha+1$.

In order to prove the reciprocal, let $\overline{c}$ be an $(r-1)$-dynamic proper $\alpha$-coloring of $G$, and let $c$ be the proper coloring of $\mathrm{DS}(G)$ such that $c(v_i) = \overline{c}(v_i)$ for all $i\leq n$, and $c(w_k) = \alpha+1$. This map $c$ is an $r$-dynamic proper $\left(\alpha+1\right)$-coloring of $\mathrm{DS}(G)$ because the following assertions hold from Lemma 1.

a) For each $i\leq n$, we have that $|c(N_{\mathrm{DS}(G)}(v_i))| = |c(N_{G}(v_i))|+1\geq \min\{r-1, \, \mathrm{deg}_G(v_i)\}+1 =$ $\min\{r, \mathrm{deg}_{\mathrm{DS}(G)}(v_i)\}$.

b) $|c(N_{\mathrm{DS}(G)}(w_k))| = \alpha$= $\max\{r, \, \chi_{r-1}(G)\}\geq \max\left\{r, \, \min\{r-1, \, \Delta(G)\}+1\right\}$ = $\max\left\{r, \, \min\{r, \, k+1\}\right\} = r$= $\min\{r, n\} = \min\{r, \mathrm{deg}_{\mathrm{DS}(G)}(w_k)\}$.

Hence, $\chi_r(\mathrm{DS}(G))\leq\alpha+1$, and the result holds. □

The extra color for the control node implies that the solutions of both Problems 1 and 3 for any $(k, r+1)$-threshold secret sharing scheme, with $k\geq r+1$, which is based on the DSG of any regular communication network $G$, coincide for each of them with the solution of Problem 1 for any $(k-1, r)$-threshold secret sharing scheme based on $G$. That is, the minimum number of rounds of communication that are necessary so that all the participants in a regular communication network can recover the secret coincides with that associated with its DSG, once the threshold of the scheme is increased by one unity. Moreover, it does not matter whether the control node is also a participant of the scheme, or not. It is an advantage, because the inclusion of this control node prevents the appearance of dishonest participants, without thereby worsening the flow of communication.

We illustrate Proposition 7 by solving the dynamic coloring problem (and hence, Problem 2) for wheels and DSGs of cocktail party graphs. (Note that the $2$-dynamic chromatic number of a wheel was already established by Kaliraj et al. ^[24].)

Theorem 8. Let $r$ and $n > 2$ be two positive integers. Then,

Proof. The result holds readily from Lemma 1 and Proposition 7 once it is observed that every cycle is $2$-regular and $\mathrm{DS}(C_n) = W_{n+1}$ for all $n > 2$. □

Figure 6 illustrates the previous result, for different values of $r$ and $n$.

Except for the control node, every participant in a wheel communication network receives information from three distinct neighbors. Thus, based on the described dynamic coloring, only those cases in which $r\leq 3$ give rise to exactly one round of communication as a solution of both Problems 1 and 3. The remaining cases require two rounds of communications for both problems.

We focus now on the DSG of a cocktail party graph $\mathrm{Cp}_n$ of vertex set $V(\mathrm{Cp}_n) = \{v_0, \ldots, v_{2n-1}\}$ and edge set $E(\mathrm{Cp}_n) = \{v_iv_j\colon\, 0\leq i, j < 2n, \, i\not\equiv j\, (\mathrm{mod}\, n))\}$. First, the following lemma corrects a previous result concerning the $r$-dynamic chromatic number of any cocktail party graph, which was not accurate (see [21, Theorem 4.2]).

Lemma 9. Let $r$ and $n > 1$ be two positive integers. Then,

Proof. From Lemma 1, it is enough to prove the case $r\leq \Delta(\mathrm{Cp}_n) = 2n-2$. Since $\mathrm{Cp}_n$ contains an $n$-clique, we have that $\chi_r(\mathrm{Cp}_n)\geq n$. This lower bound is tight for all $r < n$ because of the $r$-dynamic $n$-proper coloring graph $c$ of $\mathrm{Cp}_n$ that is described so that $c(v_i) = c(v_{i+n}) = i$ for all $i < n$. Further, if $n\leq r\leq 2n-2 = \Delta(\mathrm{Cp}_n)$, then Lemma 1 implies that $\chi_r(\mathrm{Cp}_n)\geq r+1$. However, this lower bound is not reached. Otherwise, since $N(v_i) = N(v_{i+n})$ for all $i < n$, Condition (1.1) implies that both vertices $v_i$ and $v_{i+n}$ would be equally colored for all $i < n$. But then, $r+1\leq n$, which is a contradiction. So, $\chi_r(\mathrm{Cp}_n)\geq r+2$. This new lower bound is reached because of the $r$-dynamic $(r+2)$-proper coloring graph $c$ of the graph $\mathrm{Cp}_n$ that is described so that

□

Figure 8 illustrates the dynamic coloring described in the previous proof, for $n = 4$.

Since the graph $\mathrm{Cp}_{n}$ is $(2n-2)$-regular, the following result holds readily from Lemma 9 and Proposition 7.

Theorem 10. Let $r$ and $n > 1$ be two positive integers. Then,

Figure 8 illustrates the previous result for $n = 4$.

Except for the control node, every participant in the DSG of a cocktail party communication network $\mathrm{Cp}_n$ receives information from $2n$ distinct neighbors. Thus, based on the described dynamic coloring, only those cases in which $r < 2n$ give rise to exactly one round of communication as a solution of both Problems 1 and 3. The remaining case $r = 2n$ requires two rounds of communications for both problems.

4.   The non-regular case

In practice, the direct application of Condition (1.1) and Lemma 1 constitutes the most common way to start solving the dynamic coloring problem of a given graph. We illustrate this fact by focusing in this section on the DSGs of book, comb, fan and jellyfish graphs.

4.1.   Degree splitting of book graphs

For each non-negative integer $i < n$, let $\{v_0, v_1, v_2^i, v_3^i\}$ be the set of vertices of the $(i+1)^{\mathrm{th}}$ copy of the cycle $C_4$ within the book graph $B_n$. Its set of edges is $\{v_0v_1, \, v_1v_2^i, \, v_2^iv_3^i, \, v_0v_3^i\}$. The edge $v_0v_1$ is the unique common edge shared by all these copies. Moreover, let $w_2$ and $w_{n+1}$ be the additional vertices that are respectively joined to the sets of vertices $V_2(B_n) = \{v_2^i, v_3^i\colon\, 0\leq i < n\}$ and $V_{n-1}(B_n) = \{v_0, v_1\}$ in order to get $\mathrm{DS}(B_n)$.

Proposition 11. Let $n\geq 2$ be a positive integer. Then,

Proof. Lemma 1 enables us to focus on the case $r\leq \Delta(B_n) = 2n$. Let us study each case separately.

First, we consider the case $r\in\{1, 2\}$. Since the induced subgraph of $B_n$ with set of vertices $\{v_0, \, v_1, \, w_{n+1}\}$ constitutes a $3$-clique, it must be $3\leq \chi_r(\mathrm{DS}(B_n))$. This lower bound is tight because of the $r$-dynamic proper $3$-coloring $c$ of $\mathrm{DS}(B_n)$ that is described so that $c(w_2) = c(w_{n+1}) = 2$ and, for each non-negative integer $i < n$, it is $c(v_2^i) = c(v_0) = 0$ and $c(v_3^i) = c(v_1) = 1$.

Now, we suppose that $3 \leq r \leq 2n$. From Condition (1.1) applied to the vertex $w_{n-1}$, every $r$-dynamic proper coloring $c$ of the DSG $\mathrm{DS}(B_n)$ requires $r$ distinct colors for coloring the set of vertices $V_2(B_n)$. In addition, the set of vertices $\{v_0, \, v_1, \, w_2\}$ requires three extra distinct colors because of the adjacency of the graph together with the fact that $r\geq 3 = \mathrm{deg}_{\mathrm{DS}(B_n)}(v_j^i)$ for all $j\in\{2, 3\}$ and $0\leq i < n$. Hence, $r+3\leq \chi_r(\mathrm{DS}(B_n))$. This lower bound is tight because of the $r$-dynamic proper $(r+3)$-coloring $c$ of $\mathrm{DS}(B_n)$ that is described so that $c(v_0) = r$, $c(v_1) = r+1$, $c(w_2) = c(w_{n+1}) = r+2$ and $c(v_j^i) = (2i + j-2)\, \mathrm{mod}\, r$ for all $j\in\{2, 3\}$ and $0\leq i < n$. □

Figure 9 illustrates the dynamic coloring described in the previous proof, for $n = 4$.

Based on the described dynamic coloring, since $\mathrm{deg}_{\mathrm{DS}(B_n)}(w_2) = 2$, only the case $r\in\{1, 2\}$ gives rise to exactly one round of communication as a solution of Problem 1. The remaining cases requires two rounds of communications for this problem. Similarly to the regular case, since both control nodes are colored with the same extra color, it is readily verified that Problem 3 for $\mathrm{DS}(B_n)$ has exactly the same solution as Problem 1. Thus, it does not matter whether the control nodes are participants of the scheme or not.

4.2.   Degree splitting of comb graphs

Let $\mathrm{Cb}_n$, with $n > 2$, be the comb graph that results after connecting $n$ new vertices $v'_0, \ldots, v'_{n-1}$ to the path $P_n = \langle\, v_0, \ldots, v_{n-1}\, \rangle$ by means of the edges $v_iv'_i$ for all $i < n$. Moreover, let $w_2$ be the additional vertex that is joined to the set of vertices $V_2(\mathrm{Cb}_n) = \{v_0, \, v_{n-1}\}$ to get the graph $\mathrm{DS}(\mathrm{Cb}_n)$. Similarly, if $n > 3$, then let $w_3$ be the additional vertex associated to the set of vertices $V_3(\mathrm{Cb}_n) = \{v_1, \ldots, \, v_{n-2}\}$. In particular,

The following result holds.

Proposition 12. Let $n > 2$ be a positive integer. Then,

Proof. Lemma 1 enables one to focus on the case $r\leq \Delta(\mathrm{DS}(\mathrm{Cb}_n))$. The following study of cases arises.

● Case $r = 1$.

Lemma 1 implies that $2\leq \chi(\mathrm{DS}(\mathrm{Cb}_3))$. In addition, $3\leq \chi(\mathrm{DS}(\mathrm{Cb}_n))$ for all $n > 3$, because the set of vertices $\{v_1, v_2, w_3\}$ induces a $3$-clique in $\mathrm{DS}(\mathrm{Cb}_n)$. To see that both lower bounds are tight, it is enough to consider the proper coloring $c$ of $\mathrm{Cb}_n$ described in the proof of Lemma 5, together with either $c(w_2) = 1$, if $n = 3$, or $c(w_2) = c(w_3) = 2$, if $n > 3$. (Figure 10 illustrates the case $n\in\{3, 4\}$.)

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

Lemma 1 implies that $r+1\leq \chi_r(\mathrm{DS}(\mathrm{Cb}_n))$. Figure 12 (left) illustrates that this lower bound is reached for $r = n = 3$. For the remaining cases, it is enough to consider the $r$-dynamic proper $(r+1)$-coloring that is described so that $c(w_3) = r$ (only if $n > 3$),

and, for each non-negative integer $i < n$, we have that

and

(Figure 11 (right) illustrates the case $r = 2$ and $n\in\{3, 4\}$, while Figure 12 (right) illustrates the case $(r, n) = (3, 4)$.)

● Case $r = 4$ and $n > 3$.

Lemma 1 implies that $5\leq \chi_4(\mathrm{DS}(\mathrm{Cb}_n))$. If $n\neq 1\, (\mathrm{mod}\, 4)$, this lower bound is reached because of the proper coloring $c$ of $\mathrm{Cb}_n$ described in the proof of Lemma 5, together with $c(w_2) = c(w_3) = 4$. Otherwise, if $n = 1\, (\mathrm{mod}\, 4)$, it is enough to consider the same proper coloring, except that we interchange the colors of both vertices $v_{n-1}$ and $v'_{n-2}$. (Figure 13 illustrates the case $n\in \{4, 5\}$.)

● Case $4 < r\leq n-2$.

Lemma 1 implies that $r+1\leq \chi_r(\mathrm{DS}(\mathrm{Cb}_n))$. If $n\neq 1\, (\mathrm{mod}\, r)$, then this lower bound is tight because of the $r$-dynamic proper coloring that is described so that $c(w_2) = c(w_3) = r$, and, for each positive integer $i < n$, we have that $c(v_i) = i\, (\mathrm{mod}\, r)$ and $c(v'_i) = (i+r)\, (\mathrm{mod}\, r)$. Otherwise, if $n = 1\, (\mathrm{mod}\, r)$, it is enough to consider the same proper coloring, except that we interchange the colors of both vertices $v_{n-1}$ and $v'_{n-2}$. (Figures 14 and 15 illustrate, respectively, the cases $(r, n) = (5, 7)$ and $(r, n) = (5, 11)$.)

□

The existence of pendant vertices in any comb graph implies that only the case $r = 1$ gives rise to exactly one round of communication as a solution for both Problems 1 and 3. Moreover, it is readily verified from the described dynamic coloring that, in both problems, two rounds of communication are required for $r\in\{2, 3\}$, and three rounds for the remaining cases. Again, since both control nodes are colored with the same extra color, it does not matter whether the control nodes are participants of the scheme or not.

4.3.   Degree splitting of fan graphs

Let $m\in\{1, 2\}$ and $n > 2$ be two positive integers. We focus now on solving the dynamic coloring problem for the DSG of the fan graph $F_{m, n}$ of set of vertices $V(F_{m, n}) = \{u_0, u_{m-1}, v_0, \ldots, v_{n-1}\}$, which is associated to the path $P_n = \langle\, v_0, \ldots, v_{n-1}\, \rangle$. According to their degrees, these vertices are distributed into the following sets.

● The sets $V_n(F_{m, n}) = \{u_0, u_{m-1}, v_0, v_{n-1}\}$ and $V_{n+1}(F_{m, n}) = \{v_1,$ $\ldots, v_{n-2}\}$, if $n = m+1$.

● The sets $V_{n-1}(F_{m, n}) = \{v_0, v_{n-1}\}$ and $V_n(F_{m, n}) = \{u_0, u_{m-1}, v_1,$ $\ldots, v_{n-2}, \}$, if $n = m+2$.

● The sets $V_{m+1}(F_{m, n}) = \{v_0, v_{n-1}\}$, $V_{m+2}(F_{m, n}) = \{v_1, \ldots, v_{n-2}\}$ and $V_n(F_{m, n}) = \{u_0, u_{m-1}\}$, if $n\not\in\{m+1, m+2\}$.

Each set $V_k(F_{m, n})$ for which $|V_k(F_{m, n})| > 1$ is associated to an additional vertex $w_k$ to get the DSG $\mathrm{DS}(F_{m, n})$. A preliminary lemma is required to deal with the case $m = 1$.

Lemma 13. Let $n$ and $r$ be two positive integers such that $4\leq r\leq n$. Then,

Proof. Since $r\leq n$, Condition (1.1) implies that every $r$-dynamic proper coloring of the DSG $\mathrm{DS}(F_{1, n})$ requires $r$ distinct colors for coloring the set of vertices $\{v_0, \ldots, v_{n-1}\}$, and hence, an $(r+1)^{\mathrm{th}}$ color is necessary for the vertex $u_0$. Moreover, since $\mathrm{deg}_{\mathrm{DS}(F_{1, n})}(v_i) = 4$ for all positive integer $i < n-1$, an extra $(r+2)^{\mathrm{th}}$ color is required for the vertex $w_3$. □

The following result solves the dynamic coloring problem for the fan graph $F_{1, n}$.

Theorem 14. Let $n > 2$ and $r$ be two positive integers. Then,

Proof. Lemma 1 enables us to focus on the case $r\leq \Delta(\mathrm{DS}(F_{1, n}))$. This maximum degree is $4$, if $n = 3$, and it is $n$ otherwise. The following study of cases arises.

● Case $r = 1$.

Proposition 4 and Lemma 6 imply that $\chi(\mathrm{DS}(F_{1, n}))\in\{3, 4\}$. Thus, Figure 16 (left) illustrates that $\chi(\mathrm{DS}(F_{1, 3})) = 3$. Moreover, $\chi(\mathrm{DS}(F_{1, n})) = 3$ for all $n > 3$, because of the proper $3$-coloring of $\mathrm{DS}(F_{1, n})$ that is described so that $c(u_0) = c(w_2) = c(w_3) = 2$ and $c(v_i) = i\, \mathrm{mod}\, 2$ for all $i < n$.

● Case $r = 2$.

From Lemma 1, we have that $3\leq \chi_2(\mathrm{DS}(F_{1, n}))$. This lower bound is tight for $n$ even because of the same map $c$ described in the previous case. If $n$ is odd, then every $2$-dynamic proper coloring of the DSG $\mathrm{DS}(F_{1, n})$ requires two distinct colors for the set of vertices $N_{\mathrm{DS}(F_{1, n})}(w_2) = \{v_0, \, v_{n-1}\}$, and hence, at least four colors for the set of vertices $\{u_0, \, v_0, \ldots, v_{n-1}\}$. Hence, $4\leq \chi_2(\mathrm{DS}(F_{1, n}))$ when $n$ is odd. This lower bound is tight because of the proper coloring $c$ of $\mathrm{DS}(F_{1, n})$ that is described so that $c(w_3) = c(v_{n-1}) = 2$, $c(u_0) = c(w_2) = 3$ and $c(v_i) = i\, \mathrm{mod}\, 2$ for all $i < n-1$.

● Case $r = 3$.

From Condition (1.1), every $3$-dynamic proper coloring of $\mathrm{DS}(F_{1, n})$ satisfies that the four vertices $v_0$, $v_{n-1}$, $u_0$ and $w_2$ are pairwise distinct colored. In the case of being a proper $4$-coloring, if $n > 4$, then the vertex $w_3$ must be colored as $u_0$, while the vertex $v_i$ must be colored as $v_0$, if $i\equiv 0\, (\mathrm{mod}\, 3)$; as $v_{n-1}$, if $i\equiv 1\, (\mathrm{mod}\, 3)$; and as $w_2$ otherwise. Hence, this proper $4$-coloring is possible only if $4 < n\equiv 2\, (\mathrm{mod}\, 3)$.

In order to prove that $\chi_2(\mathrm{DS}(F_{1, n})) = 4$, whenever $4 < n\equiv 2\, (\mathrm{mod}\, 3)$, it is enough to consider the $3$-dynamic proper $4$-coloring $c$ of $\mathrm{DS}(F_{1, n})$ such that $c(w_2) = 2$, $c(u_0) = c(w_3) = 3$ and $c(v_i) = i\, \mathrm{mod}\, 3$ for all $i < n$. Furthermore, in order to prove that $\chi_2(\mathrm{DS}(F_{1, n})) = 5$, whenever $4 < n\not\equiv 2\, (\mathrm{mod}\, 3)$, it is enough to consider the same proper coloring $c$ that we have just described, except for $c(v_{n-1}) = 4$.

A fifth color is also required in the case of being $n\in\{3, 4\}$. It is due to the fact that Condition (1.1) implies that every $3$-dynamic proper coloring of $\mathrm{DS}(F_{1, n})$ requires at least three distinct colors for the set of vertices $\{v_0, \ldots, v_{n-1}\}$ and exactly four distinct colors for each one of the sets of vertices $\{u_0, v_0, v_{n-1}, w_2\}$, $\{u_0, v_0, v_1, w_2\}$ and $\{u_0, v_{n-2}, v_{n-1}, w_2\}$. Thus, Figure 16 (center and right) illustrates that $\chi_3(\mathrm{DS}(F_{1, n})) = 5$, whenever $n\in\{3, 4\}$.

● Case $(r, n) = (4, 3)$.

From Lemma 1, $5\leq \chi_4(\mathrm{DS}(F_{1, 3}))$. Figure 16 (center) shows that this lower bound is tight.

● Case $4\leq r\leq n$.

Lemma 13 implies that $r+2\leq \chi_r(\mathrm{DS}(F_{1, n}))$. This lower bound is tight because of the $r$-dynamic proper $(r+2)$-coloring $c$ such that $c(u_0) = r$, $c(w_2) = c(w_3) = r+1$ and

□

The just described dynamic coloring implies that every participant in a fan communication network $F_{1, n}$, which is distinct from a control node, can reconstruct the secret under consideration in just one round of communication only if $r\in\{1, 2, 3\}$. Control nodes do the same only for $r\in\{1, 2\}$. For the remaining cases, except for the control node $w_2$ when $r > 5$, all the participants receive all the pieces of information in two rounds. For $r > 5$, three rounds are enough for all the nodes.

Now, we solve the dynamic coloring problem for the fan graph $F_{2, n}$.

Theorem 15. Let $n > 2$ and $r$ be two positive integers. Then,

Proof. From Lemma 1, we only dealt with $r\leq \Delta(\mathrm{DS}(F_{2, n})) = n+1$. The following cases arise.

● Case $r = 1$.

Proposition 4 and Lemma 6 imply that $\chi(\mathrm{DS}(F_{2, n}))\in\{3, 4\}$. Figure 17 illustrates that $\chi(\mathrm{DS}(F_{2, 3})) = 3$. Further, it is readily verified that every proper coloring of $F_{2, 4}$ requires three distinct colors for the set of vertices $V_4(F_{2, 4})$. So, $\chi(\mathrm{DS}(F_{2, 4})) = 4$. Finally, if $n > 4$, then let us consider the proper $3$-coloring $c$ of the double fan graph $F_{2, n}$ that is described so that $c(w_n) = 0$, $c(u_0) = c(u_1) = c(w_3) = c(w_4) = 2$ and $c(v_i) = i\, \mathrm{mod}\, 2$ for every non-negative integer $i < n$. Condition (1.1) holds and hence, $\chi(\mathrm{DS}(F_{2, n})) = 3$ for all $n > 4$.

● Case $r = 2$.

From Lemma 1, we have that $\chi_2(\mathrm{DS}(F_{2, n}))\geq 3$. Figure 17 also illustrates that this lower bound is tight for $n = 3$. Further, Lemma 1 implies that $4 = \chi(\mathrm{DS}(F_{2, 4}))\leq \chi_2(\mathrm{DS}(F_{2, 4}))$. Figure 18 illustrates that this lower bound is indeed reached. Finally, if $n > 4$, then every $2$-dynamic proper coloring of $\mathrm{DS}(F_{2, n})$ requires four distinct colors for the set of vertices $\{u_0, u_1, v_0, v_{n-1}\}$. Moreover, if $n$ is odd, then it requires at least five distinct colors for the set of vertices $\{u_0, u_1, v_0, v_1, \ldots, v_{n-1}\}$. As a consequence, $\chi_2(\mathrm{DS}(F_{2, n}))\geq 4$ if $n$ is even, and $\geq 5$ otherwise. Both lower bounds are reached because of the $2$-dynamic proper coloring $c$ of $\mathrm{DS}(F_{2, n}))$ that is described so that $c(w_n) = 0$, $c(u_0) = c(w_3) = c(w_4) = 2$, $c(u_1) = 3$ and

● Case $r = 3$.

From Lemma 1, we have that $4\leq \chi_3(\mathrm{DS}(F_{2, n}))$. Figure 18 also illustrates that this lower bound is tight for $n = 4$. Further, every $3$-dynamic proper coloring of $\mathrm{DS}(F_{2, 3})$ requires five distinct colors for the set of vertices $\{u_0, u_1, v_0, v_1, w_3\}$ and hence, $5\leq \chi_3(\mathrm{DS}(F_{2, 3}))$. Figure 19 (left) illustrates that this lower bound is indeed reached. Finally, if $n > 4$, then $5\leq \chi_3(\mathrm{DS}(F_{2, n}))$, because every $3$-dynamic proper coloring of $\mathrm{DS}(F_{2, n})$ requires at least five distinct colors for the set of vertices $V_4(F_{2, n})\cup V_n(F_{2, n})$. In order to prove that this lower bound is tight, it is enough to consider the $3$-dynamic proper $5$-coloring $c$ of the DSG $\mathrm{DS}(F_{2, n})$ satisfying (4.1) and such that $c(w_n) = 0$, $c(u_0) = c(w_3) = c(w_4) = 3$, $c(u_1) = 4$

● Case $(r, n) = (4, 3)$.

It is readily verified that every $4$-dynamic proper coloring of $\mathrm{DS}(F_{2, 3})$ must color each one of its vertices in a unique way (see Figure 19 (right)). So, $\chi_4(\mathrm{DS}(F_{2, 3})) = 6$.

● Case $4 \leq r \leq n+1$.

Condition (1.1) implies that every $r$-dynamic proper coloring $c$ of the DSG $\mathrm{DS}(F_{2, n})$ satisfies that $c(u_0)\neq c(u_1)$. Then, since $N_{\mathrm{DS}(F_{2, n})}(u_0) = N_{\mathrm{DS}(F_{2, n})}(u_1)$ and $\mathrm{deg}_{\mathrm{DS}(F_{2, n})}(u_0) = \mathrm{deg}_{\mathrm{DS}(F_{2, n})}(u_1) = n+1 > r$, the same condition enables one to ensure that $r+2\leq \chi_r(\mathrm{DS}(F_{2, n}))$. Figures 20 illustrates that this lower bound is reached for $(r, n)\in\{(4, 4), \, (5, 4), \, (4, 5)\}$.

Furthermore, the following subcases arise for $n > 4$.

– Subcase $r = 4\leq n-2$.

In order to prove that the lower bound $6\leq \chi_4(\mathrm{DS}(F_{2, n}))$ is tight, it is enough to consider the $4$-dynamic proper $6$-coloring of $\mathrm{DS}(F_{2, n})$ satisfying (4.1) and such that $c(w_n) = 0$, $c(w_3) = 2$, $c(u_0) = c(w_4) = 4$, $c(u_1) = 5$.

– Subcase $5\leq r\leq n$.

From Condition (1.1), it is readily deduced that every $r$-dynamic proper coloring of the DSG $\mathrm{DS}(F_{2, n})$ requires at least $r+3$ distinct colors for the set of vertices $V(F_{2, n})\setminus\{w_3, \, w_n\}$. This lower bound is tight because of the $r$-dynamic proper $(r+3)$-coloring $c$ of $\mathrm{DS}(F_{2, n})$ satisfying (4.1) and such that $c(u_0) = r$, $c(u_1) = r+1$, $c(w_3) = c(w_4) = c(w_n) = r+2$.

– Subcase $5\leq r = n+1$.

It is readily verified from Condition (1.1) that every $r$-dynamic proper coloring of $\mathrm{DS}(F_{2, n})$ requires at least $n+3$ distinct colors for $V(F_{2, n})\setminus\{w_3, \, w_n\}$. This lower bound is tight because of the $(n+1)$-dynamic proper $(n+3)$-coloring $c$ of $\mathrm{DS}(F_{2, n})$ that is described so that $c(w_3) = c(w_4) = c(w_n) = n$, $c(u_0) = n+1$, $c(u_1) = n+2$ and $c(v_i) = i$ for all $i < n$.

□

The just described dynamic coloring implies that every participant in a fan communication network $F_{2, n}$ can reconstruct the secret under consideration in just one round of communication only if either $n = 3$ and $r\leq 4$, or $n > 3$ and $r\leq 2$. In any other case, two rounds are always necessary as a solution of both Problems 1 and 3.

4.4.   Degree splitting of jellyfish graphs

Let $m$ and $n$ be two positive integers such that $m\leq n$. Let us finish this section by solving the dynamic coloring problem for the jellyfish graph $J_{m, n}$ of set of vertices arising from the cycle $C_4 = \langle\, v_0, v_1, v_2, v_3\, \rangle$ in the way described in the preliminary section. Particularly, let $\{v_1^0, \ldots, v_1^{m-1}\}$ and $\{v_3^0, \ldots, v_3^{n-1}\}$ be the sets of pendant vertices that are respectively added to the vertices $v_1$ and $v_3$. The following sets of vertices play a fundamental role in the description of the DSG $\mathrm{DS}(J_{m, n})$.

● The set $V_3(J_{1, 1}) = \{v_0, v_1, v_2, v_3\}$, if $1 = m = n$.

● The set $V_3(J_{1, n}) = \{v_0, v_1, v_2\}$, if $1 = m < n$.

● The sets $V_3(J_{n, n}) = \{v_0, v_2\}$ and $V_{n+2}(J_{n, n}) = \{v_1, v_3\}$, if $1 < m = n$.

● The set $V_3(J_{m, n}) = \{v_0, v_2\}$, if $1 < m < n$.

Each one of these sets $V(J_{m, n})$ is associated to an additional vertex $w_k$ to get $\mathrm{DS}(J_{m, n})$. The following result establishes the $r$-dynamic chromatic number of the DSG $\mathrm{DS}(J_{1, n})$.

Proposition 16. Let $n$ and $r$ be two positive integers. Then,

Proof. Let $\alpha = \max\{4, \, r+1\}$. Lemma 1 allows for a focus on the case $r\leq \Delta(\mathrm{DS}(J_{1, n}))$. This maximum degree is $4$, if $n = 1$, and it is $n+2$ otherwise. Since the induced subgraph of $J_{1, n}$ arising from the set of vertices $\{v_0, v_1, v_2, w_3\}$ is a $4$-clique, we have from Lemmas 1 and 2 that $\alpha\leq\chi_r(\mathrm{DS}(J_{1, n}))$. In order to prove that this lower bound is tight, we describe an appropriate $r$-dynamic proper $\alpha$-coloring $c$ of $\mathrm{DS}(J_{1, n})$. The following cases arise.

● If either $r\leq n$ or $(r, n)\in\{2, 3\}\times\{1\}$, then we define the map $c$ so that $c(v_i) = i$ for all $i\in\{0, 1, 2\}$, $c(w_3) = 3$, $c(v_1^0) = \max\{3, \, r\}$ and $c(v_3^j) = j\, \mathrm{mod}\, r$ for all non-negative integer $j < n$. In addition, $c(v_3) = 1$, if $n = 1$, and $c(v_3) = c(v_1^0)$ otherwise.

● If $(r, n) = (4, 1)$, then it is enough to consider the same map $c$ described in the previous case, except for $c(v_3^0) = 1$ and $c(v_3) = 4$.

● If $n > 1$ and $r\in\{n+1, \, n+2\}$, then the map $c$ is defined so that $c(v_3^i) = i$ for all $i < n$, $c(v_3) = c(v_1^0) = n$, $c(v_0) = n+1$ and $c(v_1) = 0$. In addition, if $r = n+1$, then $c(v_2) = 1$ and $c(w_3) = 2$. Otherwise, if $r = n+2$, then $c(v_2) = n+2$ and $c(w_3) = 1$.

□

Figure 21 illustrates the dynamic coloring described in the previous proof.

The existence of pendant vertices in the DSG of any jellyfish graph $J_{1, n}$ implies that only the case $r = 1$ gives rise to exactly one round of communication as a solution for both Problems 1 and 3. The dynamic coloring described in the proof of Proposition 16 implies that, for $r > 1$, two rounds of communications are enough for both problems.

Now, we solve the dynamic coloring problem for $\mathrm{DS}(J_{m, n})$, with $1 < m\leq n$.

Proposition 17. Let $m$ and $n$ be two positive integers such that $1 < m\leq n$. Then,

Proof. Lemma 1 enables us to focus on the case $r\leq \Delta(\mathrm{DS}(J_{m, n}))$. This maximum degree is $n+2$, if $m < n$, and $n+3$, if $m = n$. The following study of cases arises.

● Case $r = 1$ or ($r = 2$ and $m < n$).

Since the set of vertices $\{v_0, v_1, v_2\}$ describes a $3$-clique within $\mathrm{DS}(J_{m, n})$, we have that $3\leq\chi_r(\mathrm{DS}(J_{m, n}))$. In order to prove that this lower bound is tight for $r = 1$ and also for $r = 2$ and $m < n$, it is enough to consider the proper $3$-coloring $c$ of $\mathrm{DS}(J_{m, n})$ that is described so that $c(v_1^i) = c(v_3^j) = 0$ for all $i < m$ and $j < n$, $c(v_3) = c(w_3) = 1$ and $c(v_k) = k$ for all $k\in\{0, 1, 2\}$. In addition, if $r = 1$ and $m = n$, then $c(w_{n+2}) = 2$.

● Case $r = 2$ and $m = n$.

Condition (1.1) applied to the vertex $w_{n+2}$, together with the already mentioned $3$-clique, implies that every $2$-dynamic proper coloring of $\mathrm{DS}(J_{m, n})$ requires four distinct colors for the set of vertices $\{v_0, \, v_1, \, v_2, \, v_3, \}$. Hence, $4\leq\chi_r(\mathrm{DS}(J_{n, n}))$. This lower bound is tight because of the $2$-dynamic proper $4$-coloring $c$ of $\mathrm{DS}(J_{m, n})$ that is described so that $c(v_0^i) = c(v_3^i) = c(w_{n+2}) = 0$ for all $i < n$, $c(w_3) = 1$ and $c(v_j) = j$ for all $j\leq 3$.

● Case $3\leq r \leq \Delta(\mathrm{DS}(J_{m, n}))$.

From Lemma 1, we have that $r+1\leq\chi_r(\mathrm{DS}(J_{m, n}))$. In order to prove that this lower bound is tight, it is enough to define an appropriate $r$-dynamic proper $(r+1)$-coloring $c$ of $\mathrm{DS}(J_{m, n})$. The following subcases arise. (See Figure 22 for some illustrations of the proposed maps.)

– Subcase $3\leq r \leq m+2$.

We consider the map $c$ that is described so that

* $c(v_0) = m\, \mathrm{mod}\, r$;

* $c(v_1) = r$;

* $c(v_2) = (m+1)\, \mathrm{mod}\, r$

* $c(v_3) = (m+2)\, \mathrm{mod}\, r$;

* $c(w_3) = (m-1)\, \mathrm{mod}\, r$;

* if $m = n$, then $c(w_{n+2}) = m\, \mathrm{mod}\, r$;

* $c(v_1^i) = i\, \mathrm{mod}\, r$ for all $i < m$; and

* $c(v_3^i) = \begin{cases} i\, \mathrm{mod}\, r, & \text{ if } i\not\equiv (m+2)\, \mathrm{mod}\, r, \\ r, & \text{ otherwise}. \end{cases}$

– Subcase $m = n$ and $r = n+3$.

We consider the same map $c$ described in the previous subcase, except for $c(w_{n+2}) = (m+2)\, \mathrm{mod}\, r$ and $c(v_3) = 0$.

– Subcase $m+3\leq r\leq n+2$. (In particular, $m < n$.)

Similarly to the first subcase, we define the map $c$ so that

* $c(v_0) = n\, \mathrm{mod}\, r$;

* $c(v_1) = (n+2)\, \mathrm{mod}\, r$;

* $c(v_2) = (n+1)\, \mathrm{mod}\, r$

* $c(v_3) = r$;

* $c(w_3) = (n-1)\, \mathrm{mod}\, r$;

* $c(v_3^i) = i\, \mathrm{mod}\, r$ for all $i < n$; and

* $c(v_1^i) = \begin{cases} i\, \mathrm{mod}\, r, & \text{ if } i\not\equiv (n+2)\, \mathrm{mod}\, r, \\ r, & \text{ otherwise}. \end{cases}$

□

Again, the existence of pendant vertices implies that every node in a jellyfish communication network $J_{m, n}$, with $1 < m\leq n$, can reconstruct the secret under consideration in exactly one round of communication only if $r = 1$. The dynamic coloring in the proof of Proposition 17 implies that, for $r > 1$, all the nodes, except for the control node $w_3$, can recover all the secret shares in two rounds. (Note here the relevance of both nodes $v_1$ and $v_3$.) This control node would require two rounds to this end only if $r\in\{2, 3, 4\}$, and three rounds if $r > 4$. Hence, the solution of Problem 1 is $1$, if $r = 1$; $2$, if $r\in\{2, 3, 4\}$, and $3$, if $4 < r\leq n+3$. That of Problem 3 is $1$ if $r = 1$, and $2$ if $1 < r\leq n+3$.

5.   A new lower bound

To fit much better a lower bound for the dynamic chromatic number of a DSG, and similarly to Lemma 6, this section delves into the relationship among the dynamic chromatic number of a given graph $G$ and that of $\mathrm{DS}(G)$.

Lemma 18. Let $r > 1$ be a positive integer and let $G$ be a finite simple graph. Then,

Proof. Let $c$ be an $r$-dynamic proper coloring of $\mathrm{DS}(G)$ and let $k > 1$ be a positive integer such that $|V_k(G)| > 1$. From Condition (1.1), we have that $|c(N(w_k))|\geq\min\{r, |V_k(G)|\}$. Hence, $\min_{k > 1}\{r, \, |V_k(G)|\colon\, 1 < |V_k(G)|\}+1\leq \chi_r(\mathrm{DS}(G))$. Further, let $c'$ denote the restriction of the map $c$ to the vertices within $V(G)$. Then, for each vertex $v\in V(G)$, the following assertions hold.

● If $\mathrm{deg}_G(v)\leq 1$ or $|V_{\mathrm{deg}_G(v)}(G)| = 1$, then $N_{G}(v) = N_{\mathrm{DS}(G)}(v)$ and hence, it is $|c'(N_{G}(v))| = |c(N_{\mathrm{DS}(G)}(v))|\geq\min\{r, \mathrm{deg}_{\mathrm{DS}(G)}(v)\}$=$\min\{r, \mathrm{deg}_G(v)\}\geq \min\{r-1, \mathrm{deg}_G(v)\}$.

● If $\mathrm{deg}_G(v) > 1$ and $|V_{\mathrm{deg}_G(v)}(G)| > 1$, then it is verified that $|c'(N_{G}(v))|\geq$$|c(N_{\mathrm{DS}(G)}(v))|-1\geq \min\{r, \mathrm{deg}_{\mathrm{DS}(G)}(v)\}-1$= $\min\{r-1, \mathrm{deg}_G(v)\}$.

Thus, Condition (1.1) holds and hence, $\chi_{r-1}(G)\leq \chi_r(\mathrm{DS}(G))$. □

In order to illustrate how the previous lemma may be used to solve the dynamic coloring problem of DSGs, let us finish our study by determining the $r$-dynamic chromatic number of the DSG of windmill and barbell graphs.

Proposition 19. Let $r$ and $m, n\geq 2$ be three positive integers. Then,

Proof. From Lemma 1, we may focus on the case $r\leq \Delta(\mathrm{DS}(\mathrm{Wd}_{m, n})) = m(n-1)$. For each non-negative integer $j < m$, let $\{w, v_i^j\colon\, 0\leq i < n-1\}$ be the set of vertices of the $(j+1)^{\mathrm{th}}$ copy of the complete graph $K_n$ within the windmill graph $\mathrm{Wd}_{m, n}$. Here, $w$ denotes the vertex that all of these copies have in common. In addition, let $w_{n-1}$ denote the additional vertex that is uniquely joined to all the vertices within $V_{n-1}(\mathrm{Wd}_{m, n})$ to get $\mathrm{DS}(\mathrm{Wd}_{m, n})$. From Lemmas 3, 6 and 18, we have that

Then, the following study of cases arises.

● Case $1\leq r < n$.

In order to prove that the previous lower bound is tight, let $c$ be an $r$-dynamic proper $n$-coloring of the windmill graph $\mathrm{Wd}_{m, n}$. Then, it is enough to consider the proper $n$-coloring $c'$ of $\mathrm{DS}(\mathrm{Wd}_{m, n})$ such that $c'(v) = c(v)$ for all $v\in V(\mathrm{Wd}_{m, n})$ and $c'(w_{n-1}) = c(w)$. Condition (1.1) holds and hence, $\chi_r(\mathrm{DS}(\mathrm{Wd}_{m, n})) = n$. (Figure 23 (left) illustrates the case $(m, n) = (3, 4)$.)

● Case $n\leq r\leq m(n-1)$.

Let $c$ be an $r$-dynamic proper coloring of $\mathrm{DS}(\mathrm{Wd}_{m, n})$. Then, Condition (1.1) implies that

because $\mathrm{deg}_{\mathrm{DS}(\mathrm{Wd}_{m, n})}(w_{n-1}) = m(n-1)\geq r$ and $c(w)\neq c(w_{n-1})$. (For the last inequality, note that $\mathrm{deg}_{\mathrm{DS}(\mathrm{Wd}_{m, n})}(v_1^1) = n\leq r$ and $\{w, w_n\}\subset N_{\mathrm{DS}(\mathrm{Wd}_{m, n})}(v_1^1)$.) As a consequence, $\chi_r(\mathrm{DS}(\mathrm{Wd}_{m, n}))\geq r+2$. This lower bound is tight because of the proper coloring $c$ of $\mathrm{DS}(\mathrm{Wd}_{m, n})$ such that $c(w) = r$, $c(w_n) = r+1$ and, for each pair of non-negative integers $i < n-1$ and $j < m$,

(Figure 23 (right) illustrates the case $(m, n, r) = (4, 3, 5)$.)

□

The just described dynamic coloring implies that every participant in a windmill communication network $\mathrm{Wd}_{m, n}$ can reconstruct the secret under consideration in just one round for all $r\leq m(n-1)$. Two rounds will be necessary for $r = m(n-1)+1$ because of both vertices $w$ and $w_{n-1}$.

We finish our study by solving the dynamic coloring problem for barbell graphs.

Proposition 20. Let $n > 2$ be a positive integer. Then,

Proof. Lemma 1 enables us to focus on the case $r\leq \Delta(\mathrm{DS}(\mathrm{Ba}_n)) = 2n-2$. For each $j\in\{0, 1\}$, let $\{v_i^j\colon\, 0\leq i < n\}$ be the set of vertices of the $(j+1)^{\mathrm{th}}$ copy of the complete graph $K_n$ within $\mathrm{Ba}_n$ so that $v_{n-1}^0v_{n-1}^1$ constitutes its bridge. In addition, let $w_{n-1}$ and $w_n$ denote the additional vertices that are respectively joined to all the vertices within $V_{n-1}(\mathrm{Ba}_n) = \{v_i^j\colon\, 0\leq i < n-1, j\in\{0, 1\}\}$ and $V_n(\mathrm{Ba}_n) = \{v_{n-1}^0, \, v_{n-1}^1\}$ to get $\mathrm{DS}(\mathrm{Ba}_n)$. From Lemmas 3, 6 and 18, we have that

Then, the following study of cases arises.

● Case $1\leq r\leq n$.

Let us suppose the existence of an $r$-dynamic proper $n$-coloring $c$ of $\mathrm{DS}(\mathrm{Ba}_n)$. In particular, for each $j\in\{0, 1\}$, both sets $\{c(v_i^j)\colon\, 0\leq i < n\}$ and $\{c(v_i^j), c(w_n)\colon\, 0\leq i < n-1\}$ are formed by $n$ distinct colors. Hence, it must be $c(v_{n-1}^0) = c(w_n) = c(v_{n-1}^1)$, which is not possible because the map $c$ is a proper coloring and $v_{n-1}^0v_{n-1}^1$ constitutes the bridge within $\mathrm{Ba}_n$. As a consequence, $\chi_r(\mathrm{DS}(\mathrm{Ba}_n)) \geq n + 1$. This lower bound is tight because of the proper $(n+1)$-coloring $c$ of $\mathrm{DS}(\mathrm{Ba}_n)$ such that $c(v_i^0) = c(v_{n-1-i}^1) = i$ for all $i < n$, and $c(w_n) = c(w_{n-1}) = n$. (Figure 24 (left) illustrates the case $n = 4$.)

● Case $n < r\leq 2n-2$.

Let $c$ be an $r$-dynamic proper coloring of $\mathrm{DS}(\mathrm{Ba}_n)$. From Condition (1.1), we have, for each $j\in\{0, 1\}$, that $|c(N(v_{n-1}^j))| = d_{\mathrm{DS}(\mathrm{Ba}_n)}(v_{n-1}^j) = n+1\leq r$. Then, the underlying adjacency, together with the mentioned Condition (1.1), implies that the set

is formed by at least $r+3$ distinct colors. Hence, $\chi_r(\mathrm{DS}(\mathrm{Ba}_n))\geq r+3$. This lower bound is tight because of the proper $(r+3)$-coloring $c$ of $\mathrm{DS}(\mathrm{Ba}_n)$ such that $c(w_n) = c(w_{n-1}) = r+2$ and, for each pair of non-negative integers $i < n$ and $j\in\{0, 1\}$,

(Figure 24 (right) illustrates the case $(n, r) = (4, 5)$.)

□

The just described dynamic coloring implies that, except for the control node $w_n$, every participant in a barbell communication network $\mathrm{Ba}_n$ can reconstruct the secret under consideration in just one round for all $r\leq n$. For the remaining cases, two rounds are necessary for all the participants, except for the control node $w_{n-1}$, which only requires two rounds for $r = 2n$. The control node $w_n$ would require just one round for $r\in\{1, 2\}$, and two rounds otherwise. Hence, the solution of Problem 1 is $1$, if $r\in\{1, 2\}$, and $2$, if $2 < r\leq 2n$. That of Problem 3 is $1$ if $r\leq n$, and $2$ if $n < r\leq 2n$.

6.   Conclusion and further work

The dynamic coloring of DSGs constitutes a valuable approach to improve cryptographic protocols based on secret sharing. First, the dynamic coloring enables the dealer to distribute secret shares so that all the participants can recover the secret after a minimum number of rounds of communication. Second, DSGs enable the dealer to avoid dishonesty by adding control nodes supervising participants with the same influence in the communication network. This paper has delved into this topic by solving completely the dynamic chromatic problem for DSGs (Problem 2) of regular graphs. To this end, we have established the relationship among the dynamic chromatic number of a regular graph and that of its DSG. In addition, the dynamic coloring problem for DSGs (Problem 2) of non-regular graphs has partially been solved by establishing a new lower bound for the dynamic chromatic number under consideration. More precisely, we have solved the dynamic coloring problem for DSGs of eight families of graphs: cycles, cocktail, book, comb, fan, jellyfish, windmill and barbell graphs. Whenever it has been possible, we have detailed the dynamic coloring of each graph, so that they can naturally be translated to describe optimal secret share distributions in secret sharing schemes defined on this type of graphs. These colorings have enabled us to establish the minimum number of rounds of communications that are necessary so that all the participants of a communication network defined on such graphs can reconstruct the secret under consideration. To this end, we have distinguished whether the control nodes are also participants of the scheme (Problem 1), or not (Problem 3). Table 2 collects the solution of both problems for all the DSGs that have been studied throughout the paper. Those cases in which the solution of both problems coincide have been indicated by the symbol $=$ in the third column of Table 2.

The methodology here used may indeed be considered as a starting point to deal similarly with the dynamic coloring problem of other DSGs. Of particular interest is the study of Problems 1 and 3 for DSGs of graph products, which give rise to more complex graphs, more representative of real communication networks. Note in this regard that the dynamic chromatic problem has already been considered for different graph products ^{[22,23,24,34]}, but the implementation into a secret sharing scheme, together with the corresponding study of minimum rounds of communications to reconstruct the secret, has still not being dealt with.

Another aspect to study is the relationship between the respective dynamic chromatic numbers of a $\{k_1, k_2\}$-regular graph (and, more generally, of a $\{k_1, \ldots, k_n\}$-regular graph) and its DSG would constitute a subsequent stage for generalizing Proposition 7. It is established as further work. A main weakness to note here is the fact that, before solving Problems 1 and 3, it is necessary to solve the corresponding dynamic chromatic problem, which is by itself an NP-complete problem, as it has been indicated in the introductory section.

Finally, note that the minimum number of rounds of communication in both Problems 1 and 3 refer to any $\left(\chi_r\left(\mathrm{DS}(G)\right), \, r+1\right)$-threshold secret sharing scheme based on the DSG of the communication network $G$ under consideration. This number could be decreased if the secret splits into more pieces of information. That is, if we consider a $\left(k, \, r+1\right)$-threshold secret sharing scheme, with $k > \chi_r\left(\mathrm{DS}(G)\right)$. In this regard, the following question could be of interest for futher studies on the topic.

Problem 4. What is the minimum positive integer greater than $\chi_r\left(\mathrm{DS}(G)\right)$ into which the secret has to split for improving the solutions of Problems 1 and 3?

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The authors want to express their gratitude to the anonymous referees for the comprehensive reading of the paper and their pertinent comments and suggestions, which helped improve the manuscript. Falcón's work is partially supported by the research project FQM-016 from Junta de Andalucía.

Conflict of interest

Raúl M. Falcón is an editorial board member for [Networks and Heterogeneous Media] and was not involved in the editorial review or the decision to publish this article. All authors declare that there are no competing interests.