Processing math: 100%
 

Optimal control problems with time delays: Two case studies in biomedicine

  • Received: 30 April 2017 Accepted: 18 March 2018 Published: 01 October 2018
  • MSC : Primary: 49K15, 49M37; Secondary: 92C50

  • There exists an extensive literature on delay differential models in biology and biomedicine, but only a few papers study such models in the framework of optimal control theory. In this paper, we consider optimal control problems with multiple time delays in state and control variables and present two applications in biomedicine. After discussing the necessary optimality conditions for delayed optimal control problems with control-state constraints, we propose discretization methods by which the delayed optimal control problem is transformed into a large-scale nonlinear programming problem. The first case study is concerned with the delay differential model in [21] describing the tumour-immune response to a chemo-immuno-therapy. Assuming L1-type objectives, which are linear in control, we obtain optimal controls of bang-bang type. In the second case study, we introduce a control variable in the delay differential model of Hepatitis B virus infection developed in [7]. For L1-type objectives we obtain extremal controls of bang-bang type.

    Citation: Laurenz Göllmann, Helmut Maurer. Optimal control problems with time delays: Two case studies in biomedicine[J]. Mathematical Biosciences and Engineering, 2018, 15(5): 1137-1154. doi: 10.3934/mbe.2018051

    Related Papers:

    [1] Naqash Sarfraz, Muhammad Bilal Riaz, Qasim Ali Malik . Some new characterizations of boundedness of commutators of p-adic maximal-type functions on p-adic Morrey spaces in terms of Lipschitz spaces. AIMS Mathematics, 2024, 9(7): 19756-19770. doi: 10.3934/math.2024964
    [2] Tingting Xu, Zaiyong Feng, Tianyang He, Xiaona Fan . Sharp estimates for the p-adic m-linear n-dimensional Hardy and Hilbert operators on p-adic weighted Morrey space. AIMS Mathematics, 2025, 10(6): 14012-14031. doi: 10.3934/math.2025630
    [3] Babar Sultan, Mehvish Sultan, Aziz Khan, Thabet Abdeljawad . Boundedness of an intrinsic square function on grand p-adic Herz-Morrey spaces. AIMS Mathematics, 2023, 8(11): 26484-26497. doi: 10.3934/math.20231352
    [4] Pham Thi Kim Thuy, Kieu Huu Dung . Hardy–Littlewood maximal operators and Hausdorff operators on p-adic block spaces with variable exponents. AIMS Mathematics, 2024, 9(8): 23060-23087. doi: 10.3934/math.20241121
    [5] Naqash Sarfraz, Muhammad Aslam . Some weighted estimates for the commutators of p-adic Hardy operator on two weighted p-adic Herz-type spaces. AIMS Mathematics, 2021, 6(9): 9633-9646. doi: 10.3934/math.2021561
    [6] Qianjun He, Xiang Li . Necessary and sufficient conditions for boundedness of commutators of maximal function on the p-adic vector spaces. AIMS Mathematics, 2023, 8(6): 14064-14085. doi: 10.3934/math.2023719
    [7] Heng Yang, Jiang Zhou . Compactness of commutators of fractional integral operators on ball Banach function spaces. AIMS Mathematics, 2024, 9(2): 3126-3149. doi: 10.3934/math.2024152
    [8] Javeria Younas, Amjad Hussain, Hadil Alhazmi, A. F. Aljohani, Ilyas Khan . BMO estimates for commutators of the rough fractional Hausdorff operator on grand-variable-Herz-Morrey spaces. AIMS Mathematics, 2024, 9(9): 23434-23448. doi: 10.3934/math.20241139
    [9] Wanjing Zhang, Suixin He, Jing Zhang . Boundedness of sublinear operators on weighted grand Herz-Morrey spaces. AIMS Mathematics, 2023, 8(8): 17381-17401. doi: 10.3934/math.2023888
    [10] Chenchen Niu, Hongbin Wang . N-dimensional fractional Hardy operators with rough kernels on central Morrey spaces with variable exponents. AIMS Mathematics, 2023, 8(5): 10379-10394. doi: 10.3934/math.2023525
  • There exists an extensive literature on delay differential models in biology and biomedicine, but only a few papers study such models in the framework of optimal control theory. In this paper, we consider optimal control problems with multiple time delays in state and control variables and present two applications in biomedicine. After discussing the necessary optimality conditions for delayed optimal control problems with control-state constraints, we propose discretization methods by which the delayed optimal control problem is transformed into a large-scale nonlinear programming problem. The first case study is concerned with the delay differential model in [21] describing the tumour-immune response to a chemo-immuno-therapy. Assuming L1-type objectives, which are linear in control, we obtain optimal controls of bang-bang type. In the second case study, we introduce a control variable in the delay differential model of Hepatitis B virus infection developed in [7]. For L1-type objectives we obtain extremal controls of bang-bang type.


    Let G be a nontrivial connected graph with vertex set V=V(G). The distance between two vertices u and v in graph G is the length of the shortest path between u and v, denoted as dG(u,v) and abbreviated as d(u,v). The maximum distance between any two vertices in graph G is called the diameter of the graph, denoted as d. Let S be a subset of t vertices in graph G, where t2 and t is a positive integer. If S is an independent set and every two vertices in S have the same neighborhood, or if S is a clique and every two vertices in S have the same closed neighborhood, then the t vertices in S are called t-tuplets. In particular, if t=2, then these two vertices are called twins, and if t=3, then these three vertices are called triplets. Let the diameter be d2 of the graph G. The red-white coloring c of the graph G is defined as assigning each vertex in the graph G to be either red or white with at least one vertex assigned to be red, and the color of the vertex v is denoted as c(v). Each vertex v is associated with a d-vector d(v)=(a1,a2,,ad), called the code of v, where the ith coordinate of the d-vector is the number of red vertices at distance i from vertex v, where 1id. If aj=aj+1==aj+s, the subsequence (aj,aj+1,aj+s) is denoted as (as+1j). Specifically, if a1=a2==an=1, the sequence (1,1,,1) is abbreviated as (1n). If a red-white coloring of a graph G such that every vertex in the graph G has a different code, the coloring is said to be an identification coloring or an ID-coloring of the graph G. A graph possessing an ID-coloring is said to be an ID-graph. The number of red vertices in the ID-coloring is called the identification coloring number, and the smallest identification coloring number of a graph G is called the ID-number of the graph, or simply ID(G). A lollipop graph Tm,n+1 is a graph obtained by coinciding a vertex on the cycle Cm(m3) with a vertex of degree 1 on the path Pn+1 (n1). Then, the order of graph Tm,n+1 is m+n, and m and n are positive integers.

    Over the last decades, there has been an increasing interest in studying methods for uniquely identifying vertices in graphs, and one of the best known methods is combining distance and coloring. For example, for metric dimension for a nontrivial connected graph of order n, find an ordered set W={w1,w2,,wk} of k vertices in the graph G, 1kn, with each vertex v in the graph G associated with a k-vector(a1,a2,ak), where the ith coordinate ai represents the distance d(v,wi) between the vertex v and wi, such that different vertices in the graph G have different k-vectors, which can be usually chosen to be W=V(G), and the smallest dimension of such a set W is called the metric dimension of the graph G. Equivalently, the metric dimension of a connected graph G can be defined as the minimum number of vertices of the same color, for example, red, in the graph G such that for any two vertices u and v in the graph G, there exists a red vertex that satisfies d(u,w)d(v,w). These concepts were independently introduced by Slater [1] and Harary and Melter [2], and have been studied by many people, such as [3,4]. In 1988, Slater [1,5] described the usefulness of these concepts when dealing with the US Coast Guard's Loran stations (remote navigation aids.) and Johnson of Upjohn Pharmaceuticals used this concept in an attempt to develop the capability of large chemical map datasets [6,7]. These concepts have been investigated by people in many different applications, for example, [8,9,10,11,12,13].

    In recent years, scholars have increasingly studied vertex identification and achieved results. Compared to general graphs, special classes of graphs are more favored by scholars. In [14], Gary Chartrand et al. introduced ID-coloring and studied the identification coloring numbers of cycles and paths. Yuya Kono and Ping Zhang studied the identification coloring numbers of special trees [15], caterpillars [16], as well as prism graphs and grid graphs [17]. Inspired by these, this paper uses d-vectors to study the identification coloring numbers of lollipop graphs.

    Lemma 2.1. [14] Let c be a red-white coloring of a connected graph G where there is at least one vertex of each color. If x is a red vertex and y is a white vertex, then d(x)d(y).

    Lemma 2.2. [14] There is no ID-coloring of a connected graph with exactly two red vertices.

    Lemma 2.3. [14] A nontrivial connected graph G has ID(G)=1 if, and only if, G is a path.

    Lemma 2.4. [14] For each integer n4, there is an ID-coloring of Pn+1 with exactly r red vertices if, and only if, r=1 or 3rn.

    Lemma 2.5. [14] For each integer n6, there is an ID-coloring of Cm with exactly r red vertices if, and only if, 3rm3. Consequently, ID(Cm)=3 for n6.

    From the proof procedure of Theorems 3.1 and 4.4 in the literature [14], Lemmas 2.6 and 2.7 are obtained, respectively.

    Lemma 2.6. [14] Assuming the path Pn+1=w0w1w2wn(n3), a red-white coloring c is defined on Pn+1, where the r vertices wi, where nrin2 and i=n, are assigned as red, and the remaining vertices are assigned as white. It is then proven that this coloring is an ID-coloring of the path Pn+1.

    Lemma 2.7. [14] Assuming the cycle Cm=v0v1v2vi1vivm2vm1v0(m6), a red-white coloring c is defined on Cm, where the r vertices vi, where mr1im3 and i=m1, are assigned as red, and the remaining vertices are assigned as white. It is then proven that this coloring is an ID-coloring of the cycle Cm.

    Lemma 2.8. [14] A connected graph G of diameter 2 is an ID-graph if, and only if, G=P3.

    Lemma 2.9. [14] Let c be an ID-coloring of a connected graph G. If u and v are twins of G, then c(u)c(v). Consequently, if G is an ID-graph, then G is triplet free.

    Lemma 2.10. [15] Let G be a connected graph with an ID-coloring c. If H is a connected subgraph of G such that (i) H contains all red vertices in G and (ii) dH(x,y)=dG(x,y) for every two vertices x and y of H, then the restriction of c to H is an ID-coloring of H.

    In a lollipop graph Tm,n+1, if all of its vertices are assigned as red, then due to the symmetry of the cycle Cm, it is known that there must be at least two vertices on the cycle Cm with the same d-vector. Therefore, there is no ID-coloring of Tm,n+1 with an identification coloring number of m+n.

    Since the diameter of the graph T3,2 is d=2, it is known from Lemma 2.8 that T3,2 is not an ID-graph.

    Theorem 3.1. The lollipop graph T3,n+1(n2) has an identification coloring number of r for an ID-coloring if, and only if, 3rn+1.

    Proof. In T3,n+1, let C3=v0v1v2v0 and Pn+1=v0w1w2wn1wn. First, we prove the necessity, by Lemmas 2.2 and 2.3, 3rn+1. Suppose r=n+2. At this point, there is only one white vertex in the graph if there exists an ID-coloring in T3,n+1, because v1 and v2 are twins. By Lemma 2.9, v1 and v2 have different color assignments and one can assign v2 as white, then the rest of the vertices are assigned as red, and, at this point, d(v1)=d(wn)=(1n+1), that is, there exists no ID-coloring of T3,n+1 with exactly n+2 red vertices.

    The following is a proof of sufficiency. Assume that 3rn+1, and define a red-white coloring c of the graph T3,n+1 by assigning v1 and wi to red, where 1ir1, and the rest of the vertices to white, and the following proof that this coloring is an ID-coloring. By Lemma 2.1, the d-vectors of the red vertices are different from those of the white vertices, so we only consider the d-vectors of the two vertices with the same color. From Lemmas 2.6 and 2.10, all red vertices on T3,n+1 have different d-vectors and all white vertices on Pn+1 have different d-vectors. Moreover, v0 is the only white vertex whose first coordinate of the d-vector is 2, so we only need to consider whether the d-vector of v2 is the same as that of the white vertices on Pn+1. d(v2)=(1r,0nr+1), the only white vertex in wi(1in) that satisfies the first coordinate of the d-vector is wr, and with d(wr)=(1r1,0,1,0nr), it is clear that d(v2)d(wi). Thus, c is an ID-coloring.

    Theorem 3.2. The lollipop graph T4,n+1(n1) has an identification coloring number of r for an ID-coloring when n=1 or n=2 if, and only if, r=3; when n3 if, and only if, 3rn+2.

    Proof. In T4,n+1, let C4=v0v1v2v3v0 and Pn+1=v0w1w2wn1wn. Since v1 and v3 are twins, if there exists an ID-coloring, according to Lemma 2.9, v1 and v3 must be assigned different colors. From Figure 1, when n=1 or n=2, if, and only if, r=3. Now, consider n3.

    Figure 1.  The red-white coloring of T4,2 and T4,3.

    First, we prove the necessity. It is known from Lemmas 2.2 and 2.3 that 3rn+3. Assuming r=n+3, then there is only one white vertex in the graph, denoted as v3. In this case, we have d(v2)=d(wn)=(1n+2). Therefore, there does not exist an ID-coloring in T4,n+1 with exactly r=n+3 red vertices.

    The sufficiency is proved below. Assuming 3rn+1, define a red-white coloring c of the graph T4,n+1, where v1 and wi are assigned red, with 1ir1, and the remaining vertices are assigned white. It is to be proven that this coloring is an ID-coloring. By Lemma 2.1, it is known that the d-vectors of red vertices and white vertices are different, so we only need to consider the vectors of vertices of the same color. By Lemmas 2.6 and 2.10, it is known that the vectors of all red vertices in T4,n+1 are different, and the d-vectors of all white vertices on Pn+1 are different. Additionally, v0 is the unique white vertex with a d-vector whose first coordinate is 2, so we only need to consider whether v2 and v3 have the same d-vector as the white vertices on Pn+1. The subsequence formed by the first two coordinates of d(v2) is (1,0), and the subsequence formed by the first two coordinates of d(v3) is (0,2). If the first coordinate of d(wi) is 1, then its subsequence formed by the first two coordinates is (1,1); if the first coordinate of d(wi) is 0, then its subsequence formed by the first two coordinates is (0,1) or (0,0). Therefore, the d-vector of v2, v3, and all white vertices on Pn+1 are also different. In conclusion, it is known that the d-vectors of all vertices in T4,n+1 are different, and, therefore, c is an ID-coloring.

    Theorem 3.3. The lollipop graph T5,n+1(n1) has an identification coloring number of r for an ID-coloring. When n=1 if, and only if, r=3 or r=4. When n2 if, and only if, 3rn+4.

    Proof. In T5,n+1, let C5=v0v1v2v3v4v0 and Pn+1=v0w1w2wn1wn. From Figure 2, it is known that when n=1, the condition holds if, and only if, r=3 or r=4. Now, we consider the case when n2.

    Figure 2.  The red-white coloring of T5,2.

    First, it is necessary to prove that 3rn+4 based on Lemmas 2.2 and 2.3. Then, we proceed to prove sufficiency. By Lemma 2.1, it is known that the d-vectors of red vertices and white vertices are different, so we only need to consider the d-vectors of vertices of the same color.

    Case 1. 3rn+2.

    Define the red-white coloring c of graph T5,n+1. Assign vi and wj to white, where i{1,3,4}, r1jn, and the remaining vertices are assigned to red. We will now prove that this coloring is an ID-coloring. By Lemmas 2.6 and 2.10, all red vertices have different d-vectors and all white vertices on Pn+1 have different d-vectors. Moreover, v1 is the only white vertex whose first coordinate of the d-vector is 2, so we only need to consider whether the d-vectors of v3 and v4 are the same as those of the white vertices on Pn+1. Since d(v3)=(1r,0n+2r) and d(v4)=(1,2,1r3,0nr+3), if the first coordinate of d(wj) is 1, then we have j=r1, at which point d(wr1)=(1r1,0,1,0nr+1), so d(v3)d(v4) and d(v3)d(wj), d(v4)d(wj). Thus, c is an ID-coloring.

    Case 2. r=n+3.

    We define a red-white coloring c of the graph T5,n+1, where v0 and v4 are assigned white, and the remaining vertices are assigned red. It is to be proven that this coloring is an ID-coloring.

    To start, the first coordinate of d(v0) is 2, while the first coordinate of d(v4) is 1, so d(v0)d(v4). Now, we consider the d-vectors of the red vertices.

    d(v1)=(1,2,1n1,0), d(v2)=(2,0,1n), d(v3)=(1n+2). It is obvious that the d-vectors of all red vertices on C5 are different.

    Next, we prove that the d-vectors of red vertices on cycles and paths are different. If the first coordinate of the d-vector of vertex wj on the path is 1, then j=1 or j=n. When j=1, the subsequence formed by the first three coordinates of d(w1) is (1,1,2) or (1,2,2) or (1,2,3), and it is obvious that d(w1)d(vi). When j=n, then d(wn)=(1n1,0,1,2), and it is obvious that d(wn)d(vi). If the subsequence formed by the first two coordinates of the d-vector of vertex wj is (2,0), then j=2 and n=3. In this case, d(w2)=(2,0,1,2), and it is obvious that d(w2)d(vi).

    We prove that the d-vectors of red vertices on paths are different, with d(wi)=(a1,a2,,an+2), d(wj)=(b1, b2, , bn+2). When 1i<jn+12, ai=1, and bi=2, then d(wi)d(wj); when n+12i<jn, an+1j=2, and bn+1j=1, then d(wi)d(wj); when 1i<n+12 and n+12<jn, d(wi)=(2i1,1,) and d(wj)=(2nj,1,), if i1nj, obviously, there is d(wi)d(wj), if i1=nj; when wi and wj are adjacent, ai+1=1 and bi+1=0; when wi and wj are not adjacent, ai+1=2 and bi+1=1, that is, d(wi)d(wj). Therefore, c is an ID-colored.

    Case 3. r=n+4.

    Define the red-white coloring c of the graph T5,n+1, with v4 assigned as white and the remaining vertices assigned as red. We will now prove that this coloring is an ID-coloring. We consider the d-vector of the red vertices.

    d(v0)=(2,3,1n2,0,0), d(v1)=(2,2,1n1,0), d(v2)=(2,1n+1), d(v3)=(1,2,1n). Therefore, the d-vectors of all red vertices on C5 are distinct.

    Next, we prove that the d-vectors of red vertices on cycles and paths are distinct. By contradiction, assume d(vi)=d(wj). Let the last nonzero coordinate of d(vi) be at and the last nonzero coordinate of d(wj) be bs. Then, s=t, and it is obvious that t=d(vi,wn)=d(vi,v0)+n, so s=d(wj,v2). In this case, at=1 and bt=2, so d(vi)d(wj), which is a contradiction.

    We also prove that the d-vectors of red vertices on paths are distinct. Let d(wi)=(a1,a2, , an+2), d(wj)=(b1,b2, , bn+2). When 1i<jn12, ai+2=3 and bi+2=2, so d(wi)d(wj). When n12i<jn, an+1j=2 and bn+1j=1, so d(wi)d(wj). When 1i<n12 and n12<jn, d(wi)=(2i+1,3,) and d(wj)=(2nj,1,), and it is clear that d(wi)d(wj). Therefore, c is an ID-coloring.

    Theorem 3.4. The lollipop graph T6,n+1(n1) has an ID-coloring with identification coloring number r. When n=1 if, and only if, 3r5. When n=2 or n=3 if, and only if, 3r7. When n4 if, and only if, 3rn+5.

    Proof. In T6,n+1, let C6=v0v1v2v3v4v5v0, Pn+1=v0w1w2wn1wn. To begin, prove the necessity. By Lemmas 2.2 and 2.3, we know that 3rn+5, assuming that r=n+5. At this point in time, the graph T6,n+1 has only one white vertex, and if any vertex wi on Pn+1 is assigned to be white.By the symmetry of the cycle, at this point, there must be d(v1)=d(v5). If v0 or v3 is assigned to be white, there is also d(v1)=d(v5). Therefore, if there exists a ID-coloring of T6,n+1, only vi can be assigned as white, where i{1,2,4,5}. From Figure 3, when n=1, if, and only if, 3r5; when n=2 or n=3, if, and only if, 3r7.

    Figure 3.  The red-white coloring of T6,2 and T6,3 and T6,4.

    The following proof of sufficiency only requires consideration of n4. From Lemma 2.1, we know that red vertices have different d-vectors to white vertices, so we only need to consider two vertices of the same color.

    Case 1. 3rn+3.

    Define the red-white coloring c of the graph T6,n+1, where vi and wj are assigned as white, where i{2,4,5}, r2jn, and the remaining vertices are assigned as red. It is to be proved that this coloring is an ID-coloring.

    From Lemmas 2.6 and 2.10, it is known that all d-vectors of the red vertices are different, and all d-vectors of the white vertices on Pn+1 are different. Additionally, v2 is the only white vertex with the first coordinate of its d-vector being 2. Therefore, we only need to consider whether the d-vectors of v4, v5, and the white vertices on Pn+1 are the same. First, any white vertex wj on Pn+1 definitely has the subsequence (0,1), while v4 and v5 do not have the subsequence (0,1). Hence, it is clear that d(v4)d(wj) and d(v5)d(wj). Second, the second coordinate of d(v4) is 1, while the second coordinate of d(v5) is 3, so d(v4)d(v5). Therefore, c is an ID-coloring.

    Case 2. r=n+4.

    In this case, there are only two white vertices in the graph. Define the red-white coloring c of the graph T6,n+1, where wn1 and v5 are assigned as white, and the remaining vertices are assigned as red. It is to be proved that this coloring is an ID-coloring.

    Since the second coordinate of d(v5) is 3 and the second coordinate of d(wn1) is 1, it follows that d(v5)d(wn1). Next, consider the d-vectors of the red vertices.

    Only d(wn) has the first coordinate as 0, while the first coordinate of the d-vectors of the other red vertices is 1 or 2. Therefore, the d-vector of wn is different from the d-vectors of the other red vertices.

    d(v0)=(2,3,), d(v1)=(2,2,2,), d(v2)=(2,2,1,), d(v3)=(2,1,1,), d(v4)=(1,2,2,). It is evident that the d-vectors of all red vertices on C6 are different.

    It is to be proved that the d-vectors of the red vertices on the cycle and path are different. By contradiction, assume d(vi)=d(wj). Let at be the last non-zero coordinate of d(vi) and bs be the last non-zero coordinate of d(wj). Then s=t, and it is clear that t=d(vi,wn)=d(vi,v0)+n, so s=d(wj,v3). In this case, at1{0,1} while bt1{2,3}, so d(vi)d(wj), which is a contradiction.

    It is also to be proved that the d-vectors of the red vertices on the path are different. Let d(wi)=(a1,a2,,an+3) and d(wj)=(b1,b2, , bn+3). When 1i<jn32, ai+2=3 while bi+2=2, so d(wi)d(wj). When n32i<jn2, an1j=2 and bn1j=1, so d(wi)d(wj). When 1i<n32 and n32<jn2, d(wi)=(2i+1,3,) and d(wj)=(2nj1,1,), and it is clear that d(wi)d(wj). Therefore, c is an ID-coloring.

    Case 3. r=n+5.

    Define the red-white coloring c of the graph T6,n+1, where v5 is assigned as white and the remaining vertices are assigned as red. It is to be proved that this coloring is an ID-coloring. Consider the d-vectors of the red vertices.

    The d-vectors of v0, v1, v2, v3, and v4 have subsequences consisting of the first three coordinates, which are (2,3,2), (2,2,2), (2,2,1), (2,1,1), and (1,2,2), respectively. Therefore, it is evident that the d-vectors of all red vertices on C6 are different.

    It is to be proved that the d-vectors of the red vertices on the cycle and path are different. By contradiction, assume d(vi)=d(wj). Let at be the last nonzero coordinate of d(vi) and bs be the last nonzero coordinate of d(wj). Then, s=t, and it is clear that t=d(vi,wn)=d(vi,v0)+n, so s=d(wj,v3). In this case, at1=1 while bt1{2,3}, so d(vi)d(wj), which is a contradiction.

    It is also to be proved that the d-vectors of the red vertices on the path are different. Let d(wi)=(a1,a2,,an+3) and d(wj)=(b1,b2, , bn+3). When 1i<jn12, ai+2=3 while bi+2=2, so d(wi)d(wj). When n12i<jn, an+1j=2 and bn+1j=1, so d(wi)d(wj). When 1i<n12 and n12<jn, d(wi)=(2i+1,3,) and d(wj)=(2nj,1,), and it is clear that d(wi)d(wj). Therefore, c is an ID-coloring.

    Theorem 3.5. The lollipop graph Tm,n+1(m7,n1) has an identification coloring number of r as an ID-coloring when nm2 if, and only if, 3rm+n1. When n=m2, it has an identification coloring number of r as an ID-coloring if, and only if, 3rm+n2.

    Proof. Let the vertex where Cm and Pn+1 overlap be denoted as v0 in Tm,n+1. Suppose Cm=v0v1v2 vi1 vivm2vm1v0, Pn+1=v0w1w2wn1wn, and the diameter of the cycle Cm be denoted as d1. First, we prove the necessity. From Lemmas 2.2 and 2.3, it is known that 3rm+n1. When n=m2, the graph Tm,n+1 has only one white vertex. If we assign any vertex wi on Pn+1 as white, by the symmetry of the cycle, it is certain that d(v1)=d(vm1). If we assign v0 or vm2 as white, we also have d(v1)=d(vm1). Therefore, if Tm,n+1 has an ID-coloring, only vi, where 1id11 or d1+1im1, can be assigned as white. In this case, d(v1)=d(w1)=(0,1i1,0,1d1i1,0d1)+(2d11,1,1,0d11), which means when m7 and nm2, there does not exist an ID-coloring of Tm,n+1 with exactly m+n1 red vertices.

    Next, we prove the sufficiency. From Lemma 2.1, it is known that the d-vectors of the red vertices are different from those of the white vertices, so we only need to consider vertices of the same color. We consider the following four cases: (1) 3rm3; (2) r=m2; (3) m1rm+n2; (4) r=m+n1.

    Case 1. 3rm3.

    Define the red-white coloring c of the graph Tm,n+1, assigning r vertices as red. When d1+rm, assign vi as red, where d1+2id1+r and i=d1, and the remaining vertices as white. When d1+r>m, assign vi as red, where 0id1+rm, i=d1, and d1+2im1, and assign the remaining vertices as white. It is then proven that this coloring is an ID-coloring. From Lemmas 2.7 and 2.10, it is known that the d-vectors of all red vertices in Tm,n+1 are different, and the d-vectors of all white vertices on Cm are different. Next, it is proven that the d-vectors of the white vertices on Cm and Pn+1 are different. Let t be the position of the last nonzero coordinate in the d-vector of vi, and let s be the position of the last nonzero coordinate in the d-vector of wj. In this case, td1 and s>d1, which implies d(vi)d(wj). Therefore, c is an ID-coloring.

    Case 2. r=m2.

    Define the red-white coloring c of the graph Tm,n+1, assigning vi and wj as white, where 2jn, i{0,m3,m2}, and the remaining vertices as red. It is then proven that this coloring is an ID-coloring. First, consider the d-vectors of the white vertices. Only d(v0) has the first coordinate as 3, while the first coordinates of the d-vectors of the other white vertices are 0 or 1, so the d-vector of v0 is different from the d-vectors of the other white vertices.

    d(vm3)=(1,2,), d(vm2)=(1,1,), therefore, d(vm3)d(vm2). The only white vertex wi(2in) with a d-vector whose first coordinate is 1 is w2, and d(w2)=(1,0,), so it is obvious that d(vm2)d(wi) and d(vm3)d(wi), where 2jn.

    Next, it is proven that the d-vectors of the white vertices on the path are different. Let d(wi)=(a1,a2,,ad1+n), d(wj)=(b1, b2, ,bd1+n), where ai1 is the first nonzero coordinate of d(wi) and bj1 is the first nonzero coordinate of d(wj). Since i<j, it follows that d(wi)d(wj).

    Furthermore, consider the d-vectors of the red vertices. The d-vectors of w1 and vm1 have the first coordinate as 0, while the first coordinates of the d-vectors of the other red vertices are 1 or 2, so the d-vectors of w1 and vm1 are different from the d-vectors of the other red vertices. Additionally, the last nonzero coordinate of d(w1) is at position d1+1, while the last nonzero coordinate of d(vm1) is at position d1, so d(w1)d(vm1).

    It is also proven that the d-vectors of the red vertices on the cycle are all different. Let d(vi)=(a1,a2,,ad1+n), d(vj)=(b1,b2,,bd1+n), when 1i<jm32, ai=1, and bi=2. In this case, d(vi)d(vj); when m32i<jm4, am3j=2 and bm3j=1, so d(vi)d(vj); when 1i<m32 and m32<jm4, d(vi)=(2i1,1,) and d(vj)=(2mj4,1,); if i1m4j, then d(vi)d(vj); if i1=m4j, when x and y are adjacent, ai+1=2 and bi+1=0; when x and y are not adjacent, ai+1=3, bi+1=1; in this case, d(vi)d(vj). Therefore, c is an ID-coloring.

    Case 3. m1rm+n2.

    Subcase 3.1. rm+2m2.

    Define the red-white coloring c of the graph Tm,n+1, assigning vi and wj as white, where i{0,m1}, and rm+3jn, and the remaining vertices as red. Let k=rm+2. It is then proven that this coloring is an ID-coloring.

    Considering the d-vectors of the white vertices, d(v0) has the first coordinate as 2, while the first coordinates of the d-vectors of the other white vertices are 1 or 0. It is then proven that vm1 and the d-vectors of wi(k+1in) on the path are different. As d(vm1)=(1,3,), if i=k+1, then d(wi)=(1,1,) or d(wi)=(1,0,), and it is clear that d(wi)d(vm1). If i>k+1, then the first coordinate of d(wi) is 0, and again, d(wi)d(vm1). When x=wi and y=wj, the first nonzero coordinate of d(wi) is aik, and the first nonzero coordinate of d(vm1) is bjk, because ij, d(wi)d(wj). Thus, all the d-vectors of the white vertices are different. Next, it is considered the d-vectors of the red vertices.

    It is also proven that the d-vectors of the red vertices on the cycle are all different. Let d(vi)=(a1,a2,,ad1+n), d(vj)=(b1,b2,,bd1+n); when 1i<jm12, ai=1 and bi=2; in this case, d(vi)d(vj); when m12i<jm2, am1j=2 and bm1j=1, so d(vi)d(vj); when 1i<m12 and m32<jm2, d(vi)=(2i1,1,) and d(vj)=(2mj2,1,); if i1m2j, then d(vi)d(vj); if i1=m2j, when x and y are adjacent, ai+1=1 and bi+1=0; when x and y are not adjacent, ai+1=2 and bi+1=1; in this case, d(vi)d(vj).

    It is to be proved that the d-vectors of the red vertices on the cycle and path are different. By contradiction, assume d(vi)=d(wj). Let at be the last nonzero coordinate of d(vi) and bs be the last nonzero coordinate of d(wj). Then, s=t, and it is clear that t=d(vi,wn)=d(vi,v0)+n, so s=d(wj,vd1). If m is odd, then at=1 and bt=2, which gives d(vi)d(wj). If m is even, then d(vi,vd1)=d(wj,wk). In this case, at1{1,2} and bt1{2,3}. If at1=1 or bt1=3, it is clear that d(vi)d(wj). Next, consider the case at1=bt1=2. When at1=2, then t1=d1, which means j=1. If k=1, then i=d1, and in this case, the first coordinate of d(w1) is 0, while the first coordinate of d(vd1) is 2, which leads to a contradiction. If k2, then the first coordinate of d(w1) is 1. If the first coordinate of d(vi) is 1, then i=1 or i=m2. When i=1, then k=d1=m2, leading to a contradiction. When i=m2, the subsequence formed by the first three coordinates of d(vm2) is (1,1,3), while the subsequence formed by the first three coordinates of d(w1) is (1,1,2) or (1,2,2) or (1,2,3). It is evident that d(vi)d(wj).

    It is also to be proved that the d-vectors of the red vertices on the path are different. Let d(wi)=(a1,a2,,ad1+n), d(wj)=(b1,b2,,bd1+n). When 1i<jk+12, ai=1 while bi=2, so d(wi)d(wj). When k+12i<jk, ak+1j=2 and bk+1j=1, so d(wi)d(wj). When 1i<k+12 and k+12<jk, d(wi)=(2i1,1,) and d(wj)=(2k+1j,1,), if i1k+1j, then d(wi)d(wj); if i1=k+1j, when x and y are adjacent, ai+1=1 and bi+1=0, when x and y are not adjacent, ai+1=2 and bi+1=1, in this case d(wi)d(wj). Therefore, c is an ID-coloring.

    Subcase 3.2. rm+2=m2.

    Define the red-white coloring c of the graph Tm,n+1, assigning vm2 and wj as white, where d1+1jn and j=d11, and the remaining vertices as red. Let k=rm+2. In this case, m8, which means k4. It is then proven that this coloring is an ID-coloring.

    Considering the d-vectors of the white vertices. First, the first coordinate of d(vm2) and d(wd11) is 2, while the first coordinate of the d-vectors of the other white vertices is 1 or 0. Hence, vm2 and wd11 are different from the d-vectors of the other white vertices. Second, d(vm2)=(2,2,), and d(wd11)=(2,1,), and it is evident that d(vm2)d(wd11). Lastly, it is proven that the d-vectors of the white vertices on the path are all different. Let d(wi)=(a1,a2,,ad1+n), and d(wj)=(b1,b2,,bd1+n). In this case, the first nonzero coordinate of d(wi) is aik, and the first nonzero coordinate of d(wj) is bjk. Since ij, d(wi)d(wj). Therefore, all the d-vectors of the white vertices are different. Next, it is considered the d-vectors of the red vertices.

    Only d(wd1) has the first coordinate as 0, and only d(v0) has the first coordinate as 3, while the first coordinates of the d-vectors of the other red vertices are 1 or 2. Additionally, vm1 is the only red vertex with a subsequence of the first two coordinates as (1,3), so v0, vm1, and wd1 have d-vectors that are all different from those of the other red vertices.

    It is also proven that the d-vectors of the red vertices on the cycle are all different. Let d(vi)=(a1,a2,,ad1+n), d(vj)=(b1,b2,,bd1+n); when 1i<jm32, ai+1=3 and bi+1=2; in this case, d(vi)d(vj); when m32i<jm3, am2j=2 and bm2j=1, so d(vi)d(vj); when 1i<m32 and m32<jm3, d(vi)=(2i,3,) and d(vj)=(2mj3,1,), then d(vi)d(vj).

    It is to be proved that the d-vectors of the red vertices on the cycle and path are different. By contradiction, assume d(vi)=d(wj). Let at be the last nonzero coordinate of d(vi) and bs be the last nonzero coordinate of d(wj). Then, s=t, and it is clear that t=d(vi,wn)=d(vi,v0)+n, so s=d(wj,vd1). In this case, at1{0,1} while bt1{2,3}, so d(vi)d(wj), which is a contradiction.

    It is also to be proved that the d-vectors of the red vertices on the path are different. Let d(wi)=(a1,a2,,ad1+n) and d(wj)=(b1,b2,,bd1+n). When 1i<jk22, ai+1=3 while bi+1=2, so d(wi)d(wj). When k22i<jk2, ak1j=2 and bk1j=1, so d(wi)d(wj). When 1i<k22 and k22<jk2, d(wi)=(2i,3,) and d(wj)=(2k1j,1,), and it is clear that d(wi)d(wj). Therefore, c is an ID-coloring.

    Case 4. r=m+n1.

    The ID-coloring of T8,3 and T12,3 with m+n1 red vertices is shown in Figure 4. Now, consider the red-white coloring of Tm,n+1, if n=2, m8 and m12.

    Figure 4.  The ID-coloring of T8,3 and T12,3.

    When nm2, define the red-white coloring c of the graph Tm,n+1, assigning vm2 as white and the remaining vertices as red. It is then proven that this coloring is an ID-coloring. Consider the d-vectors of the red vertices.

    Only the first coordinate of d(v0) is 3, while the first coordinates of the d-vectors of the other red vertices are 1 or 2. Additionally, vm1 is the only red vertex with a subsequence of the first two coordinates as (1,3), so v0, vm1, and the d-vectors of the other red vertices are all different.

    It is also proven that the d-vectors of the red vertices on the cycle are all different. Let d(vi)=(a1,a2,,ad1+n), d(vj)=(b1,b2,,bd1+n); when 1i<jm32, ai+1=3 and bi+1=2; in this case, d(vi)d(vj); when m32i<jm3, am2j=2 and bm2j=1, so d(vi)d(vj); when 1i<m32 and m32<jm3, d(vi)=(2i,3,) and d(vj)=(2mj3,1,), then d(vi)d(vj).

    It is to be proved that the d-vectors of the red vertices on the cycle and path are different. By contradiction, assume d(vi)=d(wj). Let at be the last nonzero coordinate of d(vi) and bs be the last nonzero coordinate of d(wj). Then, s=t, and it is clear that t=d(vi,wn)=d(vi,v0)+n, so s=d(wj,vd1). If m is odd, then at=1 and bt=2, which gives d(vi)d(wj). If m is even, then d(vi,vd1)=d(wj,wn). In this case, at1{1,2} and bt1{2,3}. If at1=1 or bt1=3, it is clear that d(vi)d(wj). Next, consider the case at1=bt1=2. When at1=2, then t1=d1, which means j=1. If n=1, then i=d1, and in this case, the first coordinate of d(w1) is 1, while the first coordinate of d(vd1) is 2, which leads to a contradiction. If n=2, then d(w1)=(2,2,1,), and in this case, either i=d11 or i=d1+1. When i=d11, if a3=1, then d(vd11,vm2)=3, which leads to m=8, a contradiction. When i=d1+1, if a3=1, then d(vd1+1,vm2)=3, which leads to m=12, a contradiction. If n3, then the first two coordinates of d(w1) form the subsequence (2,3). If the second coordinate of d(vi) is 3, then i=1, and in this case, n=m2, a contradiction. Therefore, d(vi)d(wj).

    It is also to be proved that the d-vectors of the red vertices on the path are different. Let d(wi)=(a1,a2,,ad1+n) and d(wj)=(b1,b2,,bd1+n). When 1i<jn2, ai+1=3 while bi+1=2, so d(wi)d(wj). When n2i<jn, an+1j=2 and bn+1j=1, so d(wi)d(wj). When 1i<n2 and n2<jn, d(wi)=(2i,3,) and d(wj)=(2nj,1,), and it is clear that d(wi)d(wj). Therefore, c is an ID-coloring.

    This study established the identification coloring number for lollipop graphs by constructing explicit vertex colorings, determining the minimum number of red vertices required for unique vertex identification. The results contribute to the growing body of research on ID-graphs, providing insights into the structural properties that enable efficient distinguishing colorings. Future work could extend these methods to other graph classes or explore algorithmic approaches to optimal ID-colorings.

    Gaixiang Cai: Conceptualization, Methodology, Formal analysis, Writing–review and editing; Fengru Xiao: Investigation, Visualization, Writing–original draft; Guidong Yu: Funding acquisition, Supervision. All authors have read and agreed to the published version of the manuscript.

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

    This work was jointly supported by the key project of natural science research in universities of Anhui Province (2024AH051088), Anqing Normal University Graduate Education Quality Engineering Project (2022xxsfkc038), the Natural Science Foundation of China (No.11871077), the NSF of Anhui Province (No.1808085MA04), the NSF of Anhui Provincial Department of Education (KJ2020A0894; KJ2021A0650).

    The authors declare no conflicts of interest.

    [1] [ B. Buonomo,M. Cerasuolo, The effect of time delay in plant-pathogen interactions with host demography, Math. Biosciences and Engineering, 12 (2015): 473-490.
    [2] [ C. Büskens, Optimierungsmethoden und Sensitivitätsanalyse für optimale Steuerprozesse mit Steuer- und Zustands-Beschränkungen, PhD thesis, Institut für Numerische Mathematik, Westfälische Wilhelms-Universität Münster, Germany, 1998.
    [3] [ C. Büskens,H. Maurer, SQP methods for solving optimal control problems with control and state constraints: adjoint variables, sensitivity analysis and real-time control, J. Comput. Appl. Math., 120 (2000): 85-108.
    [4] [ C. Büskens and M. Gerdts, WORHP: Large-Scale Sparse Nonlinear Optimization Solver, http://www.worhp.de.
    [5] [ Q. Chai,R. Loxton,K. L. Teo,C. Yang, A class of optimal state-delay control Problems, Nonlinear Analysis: Real World Applications, 14 (2013): 1536-1550.
    [6] [ R. V. Culshaw,S. Ruan, A delay-differential equation model of HIV infection of CD4+ T-cells, Mathematical Biosciences, 165 (2000): 27-39.
    [7] [ S. Eikenberry,S. Hews,J. D. Nagy,Y. Kuang, The dynamics of a delay model of Hepatitis B virus infection with logistic hepatocyte growth, Mathematical Biosciences, 6 (2009): 283-299.
    [8] [ R. Fourer, D. M. Gay and B. W. Kernighan, AMPL: A Modeling Language for MathematicalProgramming, The Scientific Press, South San Francisco, California, 1993.
    [9] [ L. Göllmann,D. Kern,H. Maurer, Optimal control problems with delays in state and control and mixed control-state constraints, Optimal Control Applications and Methods, 30 (2009): 341-365.
    [10] [ L. Göllmann,H. Maurer, Theory and applications of optimal control problems with multiple time-delays, Journal of Industrial and Management Optimization, 10 (2014): 413-441.
    [11] [ T. Guinn, Reduction of delayed optimal control problems to nondelayed problems, Journal of Optimization Theory and Applications, 18 (1976): 371-377.
    [12] [ R. F. Hartl,S. P. Sethi,R. G. Vickson, A survey of the maximum principles for optimal control problems with state constraints, SIAM Review, 37 (1995): 181-218.
    [13] [ M. R. Hestenes, Calculus of Variations and Optimal Control Theory, John Wiley, New York, 1966.
    [14] [ S. C. Huang, Optimal Control problems with retardations and restricted phase coordinates, Journal of Optimization Theory and Applications, 3 (1969): 316-360.
    [15] [ J. Klamka,H. Maurer,A. Swierniak, Local controllability and optimal control for a model of combined anticancer therapy with control delays, Mathematical Biosciences and Engineering, 14 (2017): 195-216.
    [16] [ Y. Kuang, Delay Differential Equations with Applications in Population Dynamics, Academic Press, San Diego, 1993.
    [17] [ H. Maurer,C. Büskens,J.-H. R. Kim,Y. Kaya, Optimization methods for the verification of second-order sufficient conditions for bang-bang controls, Optimal Control Methods and Applications, 26 (2005): 129-156.
    [18] [ R. M. May, Time-delay versus stability in population models with two and three tropic levels, Ecology, 54 (1973): 315-325.
    [19] [ N. P. Osmolovskii and H. Maurer, Applications to Regular and Bang-Bang Control: Second-Order Necessary and Sufficient Optimality Conditions in Calculus of Variations and Optimal Control, SIAM Advances in Design and Control, Vol. DC 24, SIAM Publications, Philadelphia, 2012.
    [20] [ L. S. Pontryagin, V. G. Boltyanskii, R. V. Gamkrelidze and E. F. Mishchenko, The Mathematical Theory of Optimal Processes, Translation by K. N. Trirogoff, Wiley, New York, 1962.
    [21] [ F. Rihan, D. H. Abdelrahman, F. Al-Maskari, F. Ibrahim and M. A. Abdeen, Delay differential model for tumour-immune-response with chemoimmunotherapy and optimal control. Computational and Mathematical Methods in Medicine, Hindawi Publishing Corporation, Vol. 2014, Article ID 982978, (2014).
    [22] [ H. Schättler,U. Ledzewicz,H. Maurer, Sufficient conditions for strong local optimality in optimal control problems with L2-type objectives and control constraints, Discrete Contin. Dyn. Syst. Ser. B, 19 (2014): 2657-2679.
    [23] [ C. Silva,H. Maurer,D.F.M. Torres, Optimal control of a tuberculosis model with state and control delays, Mathematical Biosciences and Engineering, 14 (2017): 321-337.
    [24] [ C. T. Sreeramareddy,K. V. Panduru,J. Menten,J. V. den Ende, Time delays in diagnosis of pulmonary tuberculosis: A systematic review of literature, BMC Infectious Diseases, 9 (2009): 91-100.
    [25] [ J. Stoer and R. Bulirsch, Introduction ot Numerical Analysis, Third Edition, Texts in Applied Mathematics, Springer-Verlag, Berlin, 1990.
    [26] [ D. G. Storla,S. Yimer,G. A. Bjune, A systematic review in delay in the diagnosis and treatment of tuberculosis, BMC Public Health, 8 (2008): p15.
    [27] [ P. van den Driessche, Some Epidemiological Models with Delays, Report DMS-679-IR, University of Victoria, Department of Mathematics, 1994.
    [28] [ A. Wächter,L. T. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Mathematical Programming, 106 (2006): 25-57.
    [29] [ H. Yang,J. Wei, Global behaviour of a delayed viral kinetic model with general incidence rate, Discrete Contin. Dyn. Syst. Ser. B, 20 (2015): 1573-1582.
  • Reader Comments
  • © 2018 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(5535) PDF downloads(1248) Cited by(10)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog