# Product Antimagic Labeling of Caterpillars

Authors: Shengze Wang; Yuping Gao
Journal: Journal of Mathematics
 (2021)

---

## Abstract

LetG be a graph with m edges. A product antimagic labeling of G is a bijection from the edge set EG to the set 1,2,…,m such that the vertex-products are pairwise distinct, where the vertex-product of a vertex v is the product of labels on the incident edges of v. A graph is called product antimagic if it admits a product antimagic labeling. In this paper, we will show that caterpillars with at least three edges are product antimagic by an Omlogm algorithm.


---

## Body

## 1. Introduction

Letb>a be two integers. We use a,b to denote the set a,a+1,…,b and simply write 1,a as a. All graphs considered in this paper are simple and finite. Let G be a graph with m edges. The vertex set and edge set of G are denoted by VG and EG, respectively. For two vertex sets X,Y⊂VG, the set of edges with one end in X and the other end in Y is denoted by EX,Y. An antimagic labeling of G is a bijection τ from EG to m such that for any two distinct vertices u and v in G, the sum of labels on the edges incident with u differs from that of v. A graph is said to be antimagic if it admits an antimagic labeling. The concept of antimagic labeling was proposed by Hartsfield and Ringel in 1990 [1]. In the same paper, they conjectured that every connected graph other than K2 is antimagic. This topic was investigated by many researchers; for instance, see [2–6]. Recently, Lozano et al. [7] proved that caterpillars are antimagic, where a caterpillar is a tree with at least three vertices such that the removal of its leaves produces a path.In 2000, Figueroa-Centeno et al. [8] introduced multiplicative variation of antimagic labeling. A product antimagic labeling of a graph G with m edges is a bijection φ from EG to m such that the vertex-products are pairwise distinct, where the vertex-product pv of a vertex v is the product of labels on the incident edges of v. A graph G is called product antimagic if there is a product antimagic labeling of G. In [8], the authors proved that paths with at least four vertices and 2-regular graphs are product antimagic. Furthermore, they proposed the following conjecture.Conjecture 1.
A connected graph with at least three edges is product antimagic.Kaplan et al. [9] proved that the following graphs are product antimagic: the disjoint union of cycles and paths where each path has at least three edges; connected graphs with n vertices and m edges where m≥4nlnn; graphs G where each component has at least two edges and the minimum degree of G is at least 8lnElnlnE; and all complete k-partite graphs except K2 and K1,2. In [10], Pikhurko characterizes all large graphs that are product antimagic. More precisely, it is shown that there is an integer n0 such that a graph with n≥n0 vertices is product antimagic if and only if it does not belong to any of the following four classes: graphs that have at least one isolated edge; graphs that have at least two isolated vertices; unions of vertex-disjoint of copies of K1,2; graphs consisting of one isolated vertex; and graphs obtained by subdividing some edges of the star K1,k+ℓ.In this paper, we prove that Conjecture1 is affirmative for caterpillars with at least three edges.Theorem 1.
Every caterpillar with at least three edges is product antimagic.There are some other variations of antimagic labeling, such as antimagic orientation; see [11–14] for some results of trees. For more types of labelings, refer to the survey of Joseph [15]. The remainder of this paper is organized as below. In the next section, we prove Theorem 1. In Section 3, we write the labeling procedure of Theorem 1 as an algorithm.


## 2. Proof of Theorem1

LetT be a caterpillar. A leaf of T is a vertex of degree one in T, a spine of T is a longest path of T, and a leg of T is an edge that does not belong to the spine of T.Proof.
of Theorem1. Let T be a caterpillar with m≥3 edges. Since it is proved that paths with at least three edges are product antimagic, we may assume that T is not a path. Let P=v0v1,…,vℓ be a spine of T. Let U=vh1,vh2,…,vht⊂VP be the set of vertices of degree at least three in T, where h1<h2<⋯<ht. Define(1)X=x∈VT\VP|xis adjacent to a vertex inU.
In fact, a vertex inX is a leaf incident with a leg in T. Note that VP∪X=VT. Let M be a maximum matching in EU,X. Therefore, M is a matching of size U that saturates all vertices in U. We define a product antimagic labeling of T in three steps in the following, and see Figure 1 for example.Figure 1
Examples of product antimagic labelings of caterpillars: (a) a caterpillar with the spine containing odd number of edges; (b) a caterpillar with the spine containing even number of edges.
(a)(b)Step 1.
Label the edges inEP. If ℓ is odd, starting from the edge v0v1, we label the edges in EP consecutively with 2,m−ℓ−1/2+1,3,m−ℓ−1/2+2,…,ℓ−1/2+1,m,ℓ−1/2+2, respectively.
Ifℓ is even, starting from the edge v0v1, we label the edges in EP consecutively with m−ℓ/2+1,2,m−ℓ/2+2,3,…,m−1,ℓ/2,m,ℓ/2+1, respectively.
The current labeling is denoted byφ1, and the vertex-product of a vertex x in VT is denoted by p1x. It can be seen that(2)φ1vivi+1=i2+2,i≡0mod2,m−ℓ−12+i+12,i≡1mod2,where i∈0,ℓ−1, in which ℓ is odd.
And(3)φ1vivi+1=m−ℓ2+i2+1,i≡0mod2,i+12+1,i≡1mod2,where i∈0,ℓ−1, in which ℓ is even.Claim 1.
For any two distinct vertices,vi,vj∈VP and p1vi≠p1vj.Proof.
By the definition of vertex-product,(4)p1vi=φ1v0v1,i=0,φ1vi−1vi⋅φ1vivi+1,i∈1,ℓ−1,φ1vℓ−1vℓ,i=ℓ.
By equations (2) and (3), it is easy to verify that(5)p1v1<p1v2<⋯<p1vℓ−1.
Furthermore,p1v0<p1v1, p1vℓ<p1v1, and p1v0≠p1vℓ. So, for any two distinct vertices, vi,vj∈VP and p1vi≠p1vj.Step 2.
Label edges inEU,X∖EM if it is not an empty set.
Ifℓ is odd, label the edges in EU,X∖EM using numbers in 1∪ℓ−1/2+3,m−ℓ−1/2−t one by one arbitrarily (we reserve numbers in m−ℓ−1/2−t+1,m−ℓ−1/2 for edges in M).
Ifℓ is even, label the edges in EU,X∖EM using numbers in 1∪ℓ/2+2,m−ℓ/2−t one by one arbitrarily (we reserve numbers in m−ℓ/2−t+1,m−ℓ/2 for edges in M).
Denote the current labeling byφ2 and the partial vertex-product of a vertex x∈VT by p2x.Step 3.
Label edges inM.Case 1.
EU,X∖EM≠∅.
Assume thatp2vi1≤p2vi2≤⋯≤p2vit, where i1,i2,…,it=h1,h2,…,ht. Label edges in M incident with vi1,vi2,…,vit with m−⌊ℓ/2⌋−t+1,…,m−⌊ℓ/2⌋, respectively, in this order. The resulting labeling is denoted by φ3, and the current vertex-product of a vertex x∈VT is denoted by p3x.Claim 2.
φ3 is a product antimagic labeling of T.Proof.
By the way of assigning labels to edges inM, we have(6)p3vi1<p3vi2<⋯<p3vit.
It is easy to see thatφ3 is a bijection from ET to m. We show that φ3 is a product antimagic labeling of T in the following. Let V1 and V2 be the sets of vertices of degree 1 and 2, respectively. Then, VT=V1∪V2∪U. For each vertex x∈V1∖VP, we know that p3x≤m−⌊ℓ/2⌋ by Step 3. Combining with Claim 1 and the labeling steps, it follows that no vertex in V1 receives the same vertex-product as other vertices in T. Also, by Claim 1 and equation (5), it suffices to prove that for any vertex u∈V2 and any vertex v∈U, p3u≠p3v.
Ifℓ is odd, then(7)p3u≤m⋅ℓ−12+2,p3v≥2⋅m−ℓ−12+1⋅ℓ−12+3,since ℓ−1/2+2<ℓ−1/2+3 and m<2⋅m−ℓ−1/2+1 if and only if ℓ<m+3. It follows that p3u<p3v.
Ifℓ is even, then(8)p3u≤m⋅ℓ2+1,p3v≥m−ℓ2+1⋅2⋅ℓ2+2,since ℓ/2+1<ℓ/2+2 and m<2⋅m−ℓ/2+1 if and only if ℓ<m+2. It follows that p3u<p3v.
By the above discussion,φ3 is a product antimagic labeling of T.Case 2.
EU,X=EM.
In this case, Step2 does not exist. We assign the remaining labels 1,⌈ℓ/2⌉+2,⌈ℓ/2⌉+3,…,m−⌊ℓ/2⌋ to the edges in EM incident with vh1,vh2,…,vht one by one, respectively. The resulting labeling is denoted by φ′, and the vertex-product of a vertex x∈VT is denoted by p′x.Claim 3.
φ′ is a product antimagic labeling of T.Proof.
By equation (5) in the proof of Claim 1 and the labeling φ1, p1v1<p1v2<⋯<p1vℓ−1≤m⋅⌈ℓ/2⌉+1. By the labeling of edges in EM, we know that p′vh1=p1vh1 and 2⋅m−⌊ℓ/2⌋+1⋅⌈ℓ/2⌉+2≤p′vh2<p′vh3<⋯<p′vht. It can be seen that ⌊ℓ/2⌋+1<⌈ℓ/2⌉+2 and m<2⋅m−⌊ℓ/2⌋+1. So, m⋅⌈ℓ/2⌉+1<2⋅m−⌊ℓ/2⌋+1⋅⌈ℓ/2⌉+2. It follows that no two vertices in VT receive the same vertex-product and φ′ is a product antimagic labeling of T.


## 3. An Algorithm

In this section, we will write the steps of labeling a caterpillar as Algorithm1. The notation follows from the last section.Finally, we show that Algorithm1 runs in time Omlogm. Assignments in Step 1 of the algorithm can be done in constant time. Therefore, the cost of Step 1 is the result of the linear loop at lines 5 and 6 and the assignments at line 7, that is, Om. Note that if each vertex in U is of degree three, Step 2 does not run. Otherwise, Step 2 visits at most m edges and assigns a random label to each of them, but labels can be chosen increasingly from the unused labels in 1∪⌈ℓ/2⌉+2,m−⌊ℓ/2⌋, thus giving a cost Om. Step 3 requires time Omlogm due to the fact that the partial vertex-products must be sorted (line 10). The total cost of the algorithm is, then, Omlogm. Since T is a tree, the vertex number n=m+1, so the cost can be also expressed as Onlogn.Algorithm 1: Product antimagic labeling of a caterpillar.
Input: A caterpillar T with m edgesOutput: A product antimagic labeling of TStep 1: Label the edges in path P(1)
2⟶φv0v12)
m−⌊ℓ/2⌋+1⟶φv1v2ifℓ is even then(3)
Exchangeφv0v1 and φv1v2(4)
fori=2 to ℓ−1do(5)
φvi−2vi−1+1⟶φvivi+1Step 2: Label the edges in the legs except one incident with each vertex in U(6)
for allv∈Udo(7)
for all legs e incident with v except one do(8)
a random label from1∪⌈ℓ/2⌉+2,m−⌊ℓ/2⌋\φET⟶φeStep 3: Label the remaining edges(9)
Sort the vertices inU as u1,…,ut s.t. pui≤pui+1 for all i∈1,t−1(10)
Sort the labels in1∪⌈ℓ/2⌉+2,m−⌊ℓ/2⌋\φET as l1,…,lt in increasing order(11)
fori=1 to tdo(12)
li⟶φei∗, where φei∗ is the unlabeled leg incident with ui



---

*Source: 3493941-2021-10-16.xml*