Constructing the antimagic labelings for double stars union paths on three vertices

Wei-Tian Li, Po-Wen Yang · 2025

Read Constructing the antimagic labelings for double stars union paths on three vertices by Wei-Tian Li, Po-Wen Yang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-15296.txt.

Introduction

Wei-Tian Li and Po-Wen Yang work on a labeling puzzle in graph theory in 2025. In an antimagic labeling, edges get the numbers one through the total, and every vertex must end with a different sum of its edge labels. A famous conjecture says every connected graph has such a labeling. But adding many three-vertex paths to a graph can break the property.

The authors pin down exactly how many such paths can join a double star before the union stops being antimagic. They give constructions for the labelings that work. They also show special labelings whose vertex sums run neatly from one upward. The result sharpens the border of the conjecture.

Catalog record

CREATORWei-Tian Li, Po-Wen Yang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE33 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-15296

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Constructing the antimagic labelings for double stars union paths on three vertices Wei-Tian Li, Po-Wen Yang Abstract For a graph on m m edges, a bijective function between the edge set of the graph and { 1 , 2 , … , m } \{1,2,\ldots,m\} is an antimagic labeling provided that when adding the labels of the edges incident to the same vertex, the sums are pairwise distinct. Hartsfield and Ringel conjectured that every connected graph has antimagic labeling. On the other hand, it is known that for any graph G G , the disjoint union of G G and many P 3 P_{3} , a path on 3 vertices, is not antimagic. In this paper, we determined the exact number of P 3 P_{3} ’s such that the disjoint union of a double star with the number of P 3 P_{3} ’s is antimagic. In addition, we provide some examples of ( 1 , 1 ) (1,1) -antimagic labelings. That is, the antimagic labelings have vertex sums 1 through the number of vertices of the graphs. keywords: antimagic, (a,d) -antimagic, disconnected graphs, Pell equation 1 Introduction All graphs in this paper are simple graphs. Let G be a graph on m edges and [a,b] be the set of integers a\leq x\leq b . An antimagic labeling for G is a bijection f between E(G) and [1,m] such that all vertices sums are pairwise distinct, where the vertex sum \phi(v) of a vertex v in V(G) is the sum of the labels f(e) for all edges e incident to v . We say that a graph G is antimagic if there exists an antimagic labeling for G . It is clear that this kind of labeling does not exist if G=K_{2} . Hartsfield and Ringel [ 13 ] initiated the study of the antimagic problem of graphs. They gave the following two conjectures and confirmed the validity for some types of graphs. Conjecture 1 . [ 13 ] Every connected graph G\neq K_{2} is antimagic. Conjecture 2 . [ 13 ] Every tree T\neq K_{2} is antimagic. Although many significant classes of graphs such as dense graphs [ 1 ] , regular graphs [ 11 , 8 ] , trees with at most one vertex of degree two [ 14 , 19 ] , and caterpillars [ 20 ] have been proved to be antimagic, the above conjectures remain widely open. Besides, various types of antimagic problems have been come up with and studied. In [ 12 ] , a comprehensive dynamic survey of the related results and the latest developments is maintained. Notice that the assumption of connectedness in Conjecture 1 cannot be dropped. There exist disconnected graphs which are not antimagic. In [ 7 ] , Chang, Chen, Pan, and the first author showed that for any graph G , the disjoint union of G and sufficiently many P_{3} ’s, a path on 3 vertices, is not antimagic. Chaves, Le, Lin, Liu, and Shurman [ 9 ] formulated the following parameter for graphs and studied it for many graphs. Definition 1 . [ 9 ] For a graph G , let \tau(G) be the maximum integer such that the disjoint union of G and c copies of P_{3} , is antimagic for 0\leq c\leq\tau(G) . If G is not antimagic, then \tau(G)=-\infty . Given a graph G , let n , m , \ell , and t be the number of vertices, edges, internal edges, and components of G isomorphic to P_{3} , respectively. Define \beta(G)=\min\{\lfloor(3+2\sqrt{2})(m-n)+(1+\sqrt{2})(m+\tfrac{1}{2})\rfloor,2m+5(\ell-t)+1\}.\} Chaves et al . [ 9 ] proved the following Theorem 1 and proposed several problems. Theorem 1 (Corollary 2, [ 9 ] ) . For a graph G , \tau(G)\leq\beta(G) . Conjecture 3 (Conjecture 4, [ 9 ] ) . For a graph G , the union of G and c copies of P_{3} is antimagic if and only if c\leq\tau(G) . A jellyfish J(C_{k},r) is a graph obtained by attaching r pendent edges to each vertex of the cycle C_{k} , In [ 9 ] , Chaves et al . proved that \tau(C_{n})=\beta(C_{n}) for 3\leq n\leq 9 and also \tau(J(C_{3},r))=\beta(J(C_{3},r)) for r\geq 11 . In addition, Conjecture 3 holds for these graphs. A star S_{n} is a tree with n pendent edges incident to a common vertex. Much earlier, Chen, Huang, Lin, Shang, and Lee [ 10 ] determined the value of \tau(S_{n}) . They showed not only \tau(S_{n})=\beta(S_{n}) , but also that S_{n} satisfies Conjecture 3 . A double star S_{a,b} is a tree consisting of an internal edge with a edges incident to one endpoint and b edges incident to the other endpoint of the internal edge. Li [ 18 ] proved that every balanced double star S_{a,a} satisfies both \tau(S_{a,a})=\beta(S_{a,a}) and Conjecture 3 in his master thesis. The graphs G for which \tau(G) is known to date all satisfy \tau(G)=\beta(G) . Therefore, Cheves et al. asked the following question. Question 4 (Question 2, [ 9 ] ) . Does there exist a graph G without isolated vertices or P_{2} as components with \beta(G)\geq 0 and \tau(G)<\beta(G) ? In this paper, we continue the study of the antimagicness of S_{a,b} union the P_{3} ’s. We have completely determined \tau(S_{a,b}) for all a and b , and also have proved that Conjecture 3 holds for double stars by constructing all the antimagic labelings. Notice that Theorem 1 gives that \tau(S_{a,b})\leq 2m+6. (1) for m\geq 26 , and \tau(S_{a,b})\leq(1+\sqrt{2})(m-\tfrac{3}{2})-1 (2) for m\leq 25 , where m=a+b+1 is the number of edges of S_{a,b} . It turns out that Inequalities ( 1 ) and ( 2 ) are strict for certain a and b . As a consequence, we provide examples for which \tau(S_{a,b})<\beta(S_{a,b}) , which answer Question 4 . Our main result is the following theorem. Theorem 2 . For the double star S_{a,b} with a\leq b and m=a+b+1 , define \tau_{0}=\lfloor(1+\sqrt{2})(m-\tfrac{3}{2})\rfloor-1\mbox{ and }\tau_{i}=2m+i\mbox{ for }1\leq i\leq 6. Then we have \tau(S_{a,b})=\left\{\begin{array}[]{ll}\min\{\tau_{0},\tau_{1}\},&1\leq a\leq 2\\ \min\{\tau_{0},\tau_{a-1}\},&2\leq a\leq 6\\ \min\{\tau_{0},\tau_{5}\},&a=7\mbox{ and }b\leq 21\\ \min\{\tau_{0},\tau_{6}\},&a=7\mbox{ and }b\geq 22\mbox{ or }a\geq 8\\ \end{array}\right. Table 1 is the list of all \tau(S_{a,b}) and the numerical values of \tau_{0} for small m . In each row, the number in the cell in the most right is the upper bound of \tau(S_{a,b}) obtained from Inequalities ( 1 ) and ( 2 ). The gray cells show the improvement of the bounds for small a . We will derive the new upper bounds for \tau(S_{a,b}) in the next section. The construction methods of the antimagic labelings for 1\leq c\leq\tau(S_{a,b}) will be given in Section 3. Particularly, some of our antimagic labelings have the property that all vertex sums are exactly 1 through the number of vertices. We will present these special cases and discuss the corresponding research in the last section. 1 2 3 4 5 6 7 8 9 10 11 12 13 \geq 14 3 \tau_{0} 4 \tau_{0} 5 \tau_{0} \tau_{0} 6 \tau_{0} \tau_{0} 7 \tau_{0} \tau_{0} \tau_{0} 8 \tau_{0} \tau_{0} \tau_{0} 9 \tau_{0} \tau_{0} \tau_{0} \tau_{0} 10 \tau_{0} \tau_{0} \tau_{0} \tau_{0} 11 \tau_{0} \tau_{0} \tau_{0} \tau_{0} \tau_{0} 12 \tau_{0} \tau_{0} \tau_{0} \tau_{0} \tau_{0} 13 \tau_{0} \tau_{0} \tau_{0} \tau_{0} \tau_{0} \tau_{0} 14 \tau_{1}^{*} \tau_{1}^{*} \tau_{1}^{*} \tau_{1}^{*}

Read the complete text