
In this paper we study a ratio-dependent predator-prey model with a free boundary caused by predator-prey interaction over a one dimensional habitat. We study the long time behaviors of the two species and prove a spreading-vanishing dichotomy; namely, as t goes to infinity, both prey and predator successfully spread to the whole space and survive in the new environment, or they spread within a bounded area and eventually die out. The criteria governing spreading and vanishing are obtained. Finally, when spreading occurs we provide some estimates to the asymptotic spreading speed of the moving boundary h(t).
Citation: Lingyu Liu, Alexander Wires. A free boundary problem with a Stefan condition for a ratio-dependent predator-prey model[J]. AIMS Mathematics, 2021, 6(11): 12279-12297. doi: 10.3934/math.2021711
[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 |
In this paper we study a ratio-dependent predator-prey model with a free boundary caused by predator-prey interaction over a one dimensional habitat. We study the long time behaviors of the two species and prove a spreading-vanishing dichotomy; namely, as t goes to infinity, both prey and predator successfully spread to the whole space and survive in the new environment, or they spread within a bounded area and eventually die out. The criteria governing spreading and vanishing are obtained. Finally, when spreading occurs we provide some estimates to the asymptotic spreading speed of the moving boundary h(t).
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 t≥2 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 d≥2 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 1≤i≤d. 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(m≥3) with a vertex of degree 1 on the path Pn+1 (n≥1). 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, 1≤k≤n, 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 n≥4, there is an ID-coloring of Pn+1 with exactly r red vertices if, and only if, r=1 or 3≤r≤n.
Lemma 2.5. [14] For each integer n≥6, there is an ID-coloring of Cm with exactly r red vertices if, and only if, 3≤r≤m−3. Consequently, ID(Cm)=3 for n≥6.
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=w0w1w2…wn(n≥3), a red-white coloring c is defined on Pn+1, where the r vertices wi, where n−r≤i≤n−2 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=v0v1v2…vi−1vi…vm−2vm−1v0(m≥6), a red-white coloring c is defined on Cm, where the r vertices vi, where m−r−1≤i≤m−3 and i=m−1, 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(n≥2) has an identification coloring number of r for an ID-coloring if, and only if, 3≤r≤n+1.
Proof. In T3,n+1, let C3=v0v1v2v0 and Pn+1=v0w1w2…wn−1wn. First, we prove the necessity, by Lemmas 2.2 and 2.3, 3≤r≤n+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 3≤r≤n+1, and define a red-white coloring c of the graph T3,n+1 by assigning v1 and wi to red, where 1≤i≤r−1, 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,0n−r+1), the only white vertex in wi(1≤i≤n) that satisfies the first coordinate of the d-vector is wr, and with →d(wr)=(1r−1,0,1,0n−r), it is clear that →d(v2)≠→d(wi). Thus, c is an ID-coloring.
Theorem 3.2. The lollipop graph T4,n+1(n≥1) has an identification coloring number of r for an ID-coloring when n=1 or n=2 if, and only if, r=3; when n≥3 if, and only if, 3≤r≤n+2.
Proof. In T4,n+1, let C4=v0v1v2v3v0 and Pn+1=v0w1w2…wn−1wn. 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 n≥3.
First, we prove the necessity. It is known from Lemmas 2.2 and 2.3 that 3≤r≤n+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 3≤r≤n+1, define a red-white coloring c of the graph T4,n+1, where v1 and wi are assigned red, with 1≤i≤r−1, 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(n≥1) has an identification coloring number of r for an ID-coloring. When n=1 if, and only if, r=3 or r=4. When n≥2 if, and only if, 3≤r≤n+4.
Proof. In T5,n+1, let C5=v0v1v2v3v4v0 and Pn+1=v0w1w2…wn−1wn. 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 n≥2.
First, it is necessary to prove that 3≤r≤n+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. 3≤r≤n+2.
Define the red-white coloring c of graph T5,n+1. Assign vi and wj to white, where i∈{1,3,4}, r−1≤j≤n, 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+2−r) and →d(v4)=(1,2,1r−3,0n−r+3), if the first coordinate of →d(wj) is 1, then we have j=r−1, at which point →d(wr−1)=(1r−1,0,1,0n−r+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,1n−1,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)=(1n−1,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 1≤i<j≤n+12, ai=1, and bi=2, then →d(wi)≠→d(wj); when n+12≤i<j≤n, an+1−j=2, and bn+1−j=1, then →d(wi)≠→d(wj); when 1≤i<n+12 and n+12<j≤n, →d(wi)=(2i−1,1,…) and →d(wj)=(2n−j,1,…), if i−1≠n−j, obviously, there is →d(wi)≠→d(wj), if i−1=n−j; 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,1n−2,0,0), →d(v1)=(2,2,1n−1,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 1≤i<j≤n−12, ai+2=3 and bi+2=2, so →d(wi)≠→d(wj). When n−12≤i<j≤n, an+1−j=2 and bn+1−j=1, so →d(wi)≠→d(wj). When 1≤i<n−12 and n−12<j≤n, →d(wi)=(2i+1,3,…) and →d(wj)=(2n−j,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(n≥1) has an ID-coloring with identification coloring number r. When n=1 if, and only if, 3≤r≤5. When n=2 or n=3 if, and only if, 3≤r≤7. When n≥4 if, and only if, 3≤r≤n+5.
Proof. In T6,n+1, let C6=v0v1v2v3v4v5v0, Pn+1=v0w1w2…wn−1wn. To begin, prove the necessity. By Lemmas 2.2 and 2.3, we know that 3≤r≤n+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, 3≤r≤5; when n=2 or n=3, if, and only if, 3≤r≤7.
The following proof of sufficiency only requires consideration of n≥4. 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. 3≤r≤n+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}, r−2≤j≤n, 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 wn−1 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(wn−1) is 1, it follows that →d(v5)≠→d(wn−1). 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, at−1∈{0,1} while bt−1∈{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 1≤i<j≤n−32, ai+2=3 while bi+2=2, so →d(wi)≠→d(wj). When n−32≤i<j≤n−2, an−1−j=2 and bn−1−j=1, so →d(wi)≠→d(wj). When 1≤i<n−32 and n−32<j≤n−2, →d(wi)=(2i+1,3,…) and →d(wj)=(2n−j−1,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, at−1=1 while bt−1∈{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 1≤i<j≤n−12, ai+2=3 while bi+2=2, so →d(wi)≠→d(wj). When n−12≤i<j≤n, an+1−j=2 and bn+1−j=1, so →d(wi)≠→d(wj). When 1≤i<n−12 and n−12<j≤n, →d(wi)=(2i+1,3,…) and →d(wj)=(2n−j,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(m≥7,n≥1) has an identification coloring number of r as an ID-coloring when n≠m2 if, and only if, 3≤r≤m+n−1. When n=m2, it has an identification coloring number of r as an ID-coloring if, and only if, 3≤r≤m+n−2.
Proof. Let the vertex where Cm and Pn+1 overlap be denoted as v0 in Tm,n+1. Suppose Cm=v0v1v2… vi−1 vi…vm−2vm−1v0, Pn+1=v0w1w2…wn−1wn, 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 3≤r≤m+n−1. 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(vm−1). If we assign v0 or vm2 as white, we also have →d(v1)=→d(vm−1). Therefore, if Tm,n+1 has an ID-coloring, only vi, where 1≤i≤d1−1 or d1+1≤i≤m−1, can be assigned as white. In this case, →d(v1)=→d(w1)=(0,1i−1,0,1d1−i−1,0d1)+(2d1−1,1,1,0d1−1), which means when m≥7 and n≠m2, there does not exist an ID-coloring of Tm,n+1 with exactly m+n−1 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) 3≤r≤m−3; (2) r=m−2; (3) m−1≤r≤m+n−2; (4) r=m+n−1.
Case 1. 3≤r≤m−3.
Define the red-white coloring c of the graph Tm,n+1, assigning r vertices as red. When d1+r≤m, assign vi as red, where d1+2≤i≤d1+r and i=d1, and the remaining vertices as white. When d1+r>m, assign vi as red, where 0≤i≤d1+r−m, i=d1, and d1+2≤i≤m−1, 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, t≤d1 and s>d1, which implies →d(vi)≠→d(wj). Therefore, c is an ID-coloring.
Case 2. r=m−2.
Define the red-white coloring c of the graph Tm,n+1, assigning vi and wj as white, where 2≤j≤n, i∈{0,m−3,m−2}, 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(vm−3)=(1,2,…), →d(vm−2)=(1,1,…), therefore, →d(vm−3)≠→d(vm−2). The only white vertex wi(2≤i≤n) with a d-vector whose first coordinate is 1 is w2, and →d(w2)=(1,0,…), so it is obvious that →d(vm−2)≠→d(wi) and →d(vm−3)≠→d(wi), where 2≤j≤n.
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 ai−1 is the first nonzero coordinate of →d(wi) and bj−1 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 vm−1 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 vm−1 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(vm−1) is at position d1, so →d(w1)≠→d(vm−1).
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 1≤i<j≤m−32, ai=1, and bi=2. In this case, →d(vi)≠→d(vj); when m−32≤i<j≤m−4, am−3−j=2 and bm−3−j=1, so →d(vi)≠→d(vj); when 1≤i<m−32 and m−32<j≤m−4, →d(vi)=(2i−1,1,…) and →d(vj)=(2m−j−4,1,…); if i−1≠m−4−j, then →d(vi)≠→d(vj); if i−1=m−4−j, 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. m−1≤r≤m+n−2.
Subcase 3.1. r−m+2≠m2.
Define the red-white coloring c of the graph Tm,n+1, assigning vi and wj as white, where i∈{0,m−1}, and r−m+3≤j≤n, and the remaining vertices as red. Let k=r−m+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 vm−1 and the d-vectors of wi(k+1≤i≤n) on the path are different. As →d(vm−1)=(1,3,…), if i=k+1, then →d(wi)=(1,1,…) or →d(wi)=(1,0,…), and it is clear that →d(wi)≠→d(vm−1). If i>k+1, then the first coordinate of →d(wi) is 0, and again, →d(wi)≠→d(vm−1). When x=wi and y=wj, the first nonzero coordinate of →d(wi) is ai−k, and the first nonzero coordinate of →d(vm−1) is bj−k, because i≠j, →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 1≤i<j≤m−12, ai=1 and bi=2; in this case, →d(vi)≠→d(vj); when m−12≤i<j≤m−2, am−1−j=2 and bm−1−j=1, so →d(vi)≠→d(vj); when 1≤i<m−12 and m−32<j≤m−2, →d(vi)=(2i−1,1,…) and →d(vj)=(2m−j−2,1,…); if i−1≠m−2−j, then →d(vi)≠→d(vj); if i−1=m−2−j, 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, at−1∈{1,2} and bt−1∈{2,3}. If at−1=1 or bt−1=3, it is clear that →d(vi)≠→d(wj). Next, consider the case at−1=bt−1=2. When at−1=2, then t−1=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 k≥2, then the first coordinate of →d(w1) is 1. If the first coordinate of →d(vi) is 1, then i=1 or i=m−2. When i=1, then k=d1=m2, leading to a contradiction. When i=m−2, the subsequence formed by the first three coordinates of →d(vm−2) 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 1≤i<j≤k+12, ai=1 while bi=2, so →d(wi)≠→d(wj). When k+12≤i<j≤k, ak+1−j=2 and bk+1−j=1, so →d(wi)≠→d(wj). When 1≤i<k+12 and k+12<j≤k, →d(wi)=(2i−1,1,…) and →d(wj)=(2k+1−j,1,…), if i−1≠k+1−j, then →d(wi)≠→d(wj); if i−1=k+1−j, 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. r−m+2=m2.
Define the red-white coloring c of the graph Tm,n+1, assigning vm−2 and wj as white, where d1+1≤j≤n and j=d1−1, and the remaining vertices as red. Let k=r−m+2. In this case, m≥8, which means k≥4. 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(vm−2) and →d(wd1−1) is 2, while the first coordinate of the d-vectors of the other white vertices is 1 or 0. Hence, vm−2 and wd1−1 are different from the d-vectors of the other white vertices. Second, →d(vm−2)=(2,2,…), and →d(wd1−1)=(2,1,…), and it is evident that →d(vm−2)≠→d(wd1−1). 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 ai−k, and the first nonzero coordinate of →d(wj) is bj−k. Since i≠j, →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, vm−1 is the only red vertex with a subsequence of the first two coordinates as (1,3), so v0, vm−1, 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 1≤i<j≤m−32, ai+1=3 and bi+1=2; in this case, →d(vi)≠→d(vj); when m−32≤i<j≤m−3, am−2−j=2 and bm−2−j=1, so →d(vi)≠→d(vj); when 1≤i<m−32 and m−32<j≤m−3, →d(vi)=(2i,3,…) and →d(vj)=(2m−j−3,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, at−1∈{0,1} while bt−1∈{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 1≤i<j≤k−22, ai+1=3 while bi+1=2, so →d(wi)≠→d(wj). When k−22≤i<j≤k−2, ak−1−j=2 and bk−1−j=1, so →d(wi)≠→d(wj). When 1≤i<k−22 and k−22<j≤k−2, →d(wi)=(2i,3,…) and →d(wj)=(2k−1−j,1,…), and it is clear that →d(wi)≠→d(wj). Therefore, c is an ID-coloring.
Case 4. r=m+n−1.
The ID-coloring of T8,3 and T12,3 with m+n−1 red vertices is shown in Figure 4. Now, consider the red-white coloring of Tm,n+1, if n=2, m≠8 and m≠12.
When n≠m2, define the red-white coloring c of the graph Tm,n+1, assigning vm−2 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, vm−1 is the only red vertex with a subsequence of the first two coordinates as (1,3), so v0, vm−1, 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 1≤i<j≤m−32, ai+1=3 and bi+1=2; in this case, →d(vi)≠→d(vj); when m−32≤i<j≤m−3, am−2−j=2 and bm−2−j=1, so →d(vi)≠→d(vj); when 1≤i<m−32 and m−32<j≤m−3, →d(vi)=(2i,3,…) and →d(vj)=(2m−j−3,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, at−1∈{1,2} and bt−1∈{2,3}. If at−1=1 or bt−1=3, it is clear that →d(vi)≠→d(wj). Next, consider the case at−1=bt−1=2. When at−1=2, then t−1=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=d1−1 or i=d1+1. When i=d1−1, if a3=1, then d(vd1−1,vm−2)=3, which leads to m=8, a contradiction. When i=d1+1, if a3=1, then d(vd1+1,vm−2)=3, which leads to m=12, a contradiction. If n≥3, 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 1≤i<j≤n2, ai+1=3 while bi+1=2, so →d(wi)≠→d(wj). When n2≤i<j≤n, an+1−j=2 and bn+1−j=1, so →d(wi)≠→d(wj). When 1≤i<n2 and n2<j≤n, →d(wi)=(2i,3,…) and →d(wj)=(2n−j,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] |
Y. Kuang, E. Beretta, Global qualitative analysis of a ratio-dependent predator-prey system, J. Math. Biol., 36 (1998), 389-406. doi: 10.1007/s002850050105
![]() |
[2] | P. A. Abrams, L. R. Ginzburg, The nature of predation: Prey dependent, ratio dependent or neither? Trends Ecol. Evol., 15 (2000), 337-341. |
[3] |
N. G. Hairston, F. E. Smith, L. B. Slobodkin, Community structure, population control, and competition, Am. Nat., 94 (1960), 421-425. doi: 10.1086/282146
![]() |
[4] |
F. L. Robert, Evaluation of natural enemies for biological control: A behavioral approach, Trends Ecol. Evol., 5(1990), 196-199. doi: 10.1016/0169-5347(90)90210-5
![]() |
[5] |
R. Arditi, L. R. Ginzburg, Coupling in predator-prey dynamics: Ratio-dependence, J. Theor. Biol., 139 (1989), 311-326. doi: 10.1016/S0022-5193(89)80211-5
![]() |
[6] | L. I. Rubensteĭn, The Stefan problem, Translations of Mathematical Monographs, Vol. 27, Rhode Island: American Mathematical Society Providence, 1971. |
[7] |
X. F. Chen, A. Friedman, A free boundary problem arising in a model of wound healing, SIAM J. Math. Anal., 32 (2000), 778-800. doi: 10.1137/S0036141099351693
![]() |
[8] |
Y. H. Du, L. Ma, Logistic type equations on RN by a squeezing method involving boundary blow-up solutions, J. Lond. Math. Soc., 64 (2001), 107-124. doi: 10.1017/S0024610701002289
![]() |
[9] |
Y. H. Du, Z. G. Lin, Spreading-vanishing dichotomy in the diffusive logistic model with a free boundary, SIAM J. Math. Anal., 42 (2010), 377-405. doi: 10.1137/090771089
![]() |
[10] |
Y. H. Du, Z. M. Guo, Spreading-vanishing dichotomy in a diffusive logistic model with a free boundary, II, J. Differ. Equations, 250 (2011), 4336-4366. doi: 10.1016/j.jde.2011.02.011
![]() |
[11] |
Y. H. Du, Z. M. Guo, R. Peng, A diffusive logistic model with a free boundary in time-periodic environment, J. Funct. Anal., 265 (2013), 2089-2142. doi: 10.1016/j.jfa.2013.07.016
![]() |
[12] | Y. H. Du, B. D. Lou, Spreading and vanishing in nonlinear diffusion problems with free boundaries, Mathematics, 17 (2015), 2673-2724. |
[13] |
G. Bunting, Y. H. Du, K. Krakowski, Spreading speed revisited: Analysis of a free boundary model, Networks Heterog. Media, 7 (2012), 583-603. doi: 10.3934/nhm.2012.7.583
![]() |
[14] |
Y. H. Du, Z. M. Guo, The Stefan problem for the Fisher-KPP equation, J. Differ. Equations, 253 (2012), 996-1035. doi: 10.1016/j.jde.2012.04.014
![]() |
[15] |
M. X. Wang, J. F. Zhao, A free boundary problem for the predator-prey model with double free boundaries, J. Dyn. Differ. Equations, 29 (2017), 957-979. doi: 10.1007/s10884-015-9503-5
![]() |
[16] |
M. X. Wang, J. F. Zhao, Free boundary problems for a Lotka-Volterra competition system, J. Dyn. Differ. Equations, 26 (2014), 655-672. doi: 10.1007/s10884-014-9363-4
![]() |
[17] |
M. X. Wang, Y. G. Zhao, A semilinear parabolic system with a free boundary, Z. Angew. Math. Phys., 66 (2015), 3309-3332. doi: 10.1007/s00033-015-0582-2
![]() |
[18] |
M. X. Wang, Y. Zhang, Two kinds of free boundary problems for the diffusive prey-predator model, Nonlinear Anal.-Real, 24 (2015), 73-82. doi: 10.1016/j.nonrwa.2015.01.004
![]() |
[19] |
M. X. Wang, Spreading and vanishing in the diffusive prey-predator model with a free boundary, Commun. Nonlinear Sci. Numer. Simul., 23 (2015), 311-327. doi: 10.1016/j.cnsns.2014.11.016
![]() |
[20] |
M. X. Wang, On some free boundary problems of the prey-predator model, J. Differ. Equations, 256 (2014), 3365-3394. doi: 10.1016/j.jde.2014.02.013
![]() |
[21] |
M. X. Wang, Y. Zhang, Dynamics for a diffusive prey-predator model with different free boundaries, J. Differ. Equations, 264 (2018), 3527-3558. doi: 10.1016/j.jde.2017.11.027
![]() |
[22] |
J. F. Zhao, M. X. Wang, A free boundary problem of a predator-prey model with higher dimension and heterogeneous environment, Nonlinear Anal.-Real, 16 (2014), 250-263. doi: 10.1016/j.nonrwa.2013.10.003
![]() |
[23] | N. N. Pelen, M. E. Koksal, Necessary and sufficient conditions for the existence of periodic solutions in a predator-prey model, Electron. J. Differ. Equations, 3 (2017), 1-12. |
[24] | L. Y. Liu, A free boundary problem for a ratio-dependent predator-prey system, 2020. Available from: https://arXiv.org/abs/2006.13770. |
[25] |
Y. Zhang, M. X. Wang, A free boundary problem of the ratio-dependent prey-predator model, Appl. Anal., 94 (2015), 1-21. doi: 10.1080/00036811.2014.992104
![]() |