# On Elegant Labelling and Magic Labelling of Large-Scale Graphs

Authors: Jing Su; Hongyu Wang; Bing Yao
Journal: Discrete Dynamics in Nature and Society
 (2022)

---

## Abstract

In this paper, we deduce the equivalence relationship among strongly c-elegant labelling, super-edge magic total labelling, edge antimagic total labelling, and supert,1-magical labelling. We study some properties of the graph with a strongly c-elegant labelling. On the basis of small-scale graphs with strongly c-elegant labelling, several types of large-scale graphs are constructed through graph operations, and we further prove the existence of their strongly c-elegant labelling. In addition, we also define a transformation of strongly c-elegant labelling, which provides a method for the transformation between several strongly c-elegant labellings of a graph.


---

## Body

## 1. Introduction

Topological authentication is a new technology based on topological coding to solve the problem that text passwords are easily deciphered, and it is used for user identity authentication of smartphones [1, 2], mobile ad hoc networks [3], picture signature passwords [4], and so on. Topological authentication is an interdisciplinary research topic of graph theory, algebra, discrete mathematics, and other disciplines. Wang et al. [5, 6] designed a class of topology code composed of topology structure and graph labellings, and its difficulty is based on some mathematical problems such as graph isomorphism and graceful tree conjecture. Yao et al. [7, 8] proposed a new type of matrix combined with graph labelling technology to generate complex forms and longer byte text passwords. Tian et al. [9] proved that the password generated by the labelling of the graph can resist brute force attacks, copy attacks, and other attacks.Graph labellings including the term offu+fvuv∈EG were used in many problems. An example, studied first by Graham and Sloane, is the harmonious graphs of modular versions of additive base problems stemming from error-correcting codes in the paper [10] in which the authors collected over 600 papers on various graph labellings. In 1981, Chang, Hsu, and Rogers [11] defined a strongly c-elegant labelling of a p,q-graph G. Shee [12] has proved that Km,n is strongly c-elegant for a particular value of c and obtained several more specialized results pertaining to graphs formed from complete bipartite graphs. Seoud and Elsakhawi [13] have shown that Km,nm≤n with an edge joining two vertices of the same partite set is strongly c-elegant for c=1,3,5,…,2n+2. The strongly c-elegant labelling and some magic labelling involved in this paper all exist in the form of fu+fv for edge uv in a graph.The security of topological cryptography can be increased by using larger-scale graphs or richer graph coloring; therefore, it is worth studying to find the connections or conversion methods between graph labellings and how to construct large-scale graphs. In this paper, we study the relationships between strongly c-elegant labelling, super-edge magic total labelling, edge antimagic total labelling, and supert,1-magical labelling; we also give a necessary condition for a graph with a strongly c-elegant labelling. Based on small-scale graphs with strongly c-elegant labelling, several kinds of large-scale graphs are constructed and the existence of their strongly c-elegant labelling is proved. Also, we present a transformation method for several strongly c-elegant labellings of a graph.


## 2. Preliminary

We list the symbols commonly used in this paper in Table1; let VG and EG denote the vertex set and edge set of a graph G, and other symbols can be found in [14, 15].Table 1
Symbol and definition table.
Symbol/definitionMeaningp,q-GraphAn undirected graph withp vertices and q edgesa,bA setx∈Z:a≤x≤b with a,b∈N, a<bk-setA set containsk elementsCaterpillarA caterpillar refers to a tree whose graph obtained is a path after deleting all the leavesLobsterA lobster is a tree whose resultant graph is a caterpillar after removing all leavesSpiderA spider is a tree whose vertices have at most degree 2, except only one vertexu0 whose degree is not less than 3 and u0 is called the center of the spiderDefinition 1.
(see [11]). A mapping f: VG⟶0,q such that the label fuv of each edge uv in G is defined by fuv=fu+fv, and the resultant edge labels are distinct. If fVG=fu|u∈VG=0,q and(1)fEG=fuv|uv∈EG=c,c+q−1,where c is a nonnegative integer, we say f to be a strongly c-elegant labelling of G; then, the graph G is called strongly c-elegant. When G is a bipartite graph, that is, VG=V1∪V2 and V1∩V2=∅, if maxfu<minfv for all u∈V1 and v∈V2, we call f a set-ordered strongly c-elegant labelling of G (see an example in Figure 1(a)).
In 1970, Kotzig and Rosa defined the concept of edge magic total labelling (abbreviated as EMT labelling) of ap,q-graph G as follows.Figure 1
(a) The Petersen graph has a strongly c-elegant labelling. (b) The Petersen graph has SEMT labelling with a magic constant 29. (c) The Petersen graph has a super15,2-EAT labelling that is also a super −7,1-magical labelling.
(a)(b)(c)Definition 2.
(see [16]). A bijective mapping f from VG∪EG to 1,p+q such that for any edge uv,(2)fu+fuv+fv=C,where C is a fixed constant, called a magic constant. Enomoto, Llad o´, Nakamigawa, and Ringel [17] called a graph G with an edge magic total labelling that has the fVG=1,p super-edge magic total labelling (SEMT labelling), and an example is shown in Figure 1(b).Definition 3.
(1)
(see [10]). A k,d-edge antimagic total labelling (abbreviated as k,d-EAT labelling) is a bijection f: VG∪EG⟶1,p+q having the set(3)fu+fuv+fv|uv∈EG=k,k+q−1d,for certain integers k and d; analogously, a k,d-EAT labelling f of G is super if fVG=1,p.(2)
A bijectionf of a p,q-graph G from VG∪EG to 1,p+q is regarded as a k,λ-magical labelling of G if and only if(4)fu+fv=k+λfuvfor uv∈EG,for integers k and λ≠0. Especially, if fu≤p for any vertex u∈VG, we say that f is a super k,λ-magical labelling of G (see Figure 1(c)).Definition 4.
(see (4)). Let f: VG⟶0,q. The dual labelling f′ of f is defined by(5)f′x=maxu∈VGfu+minu∈VGfu−fxforx∈VG.


## 3. Main Results

In this section, we prove that the strongly c-elegant labelling and SEMT labelling are pairwise equivalents via some superk,λ-magical labellings. There is a way of getting some graphs having EMT labellings from some strongly c-elegant graphs. Then, we show that a p,q-graph G admits a strongly c-elegant labelling and q≤2p−3.


### 3.1. The Elegant Labelling and Magic Labelling

In order to achieve the purpose of mutual conversion between labellings, we firstly give the relationship between strongly c-elegant labelling and super-edge magic total labelling and we will show that the problem of determining those trees having EMT labellings can be reduced to the problem of finding strongly c-elegant labellings.Theorem 1.
A graphG admits a strongly c-elegant labelling if and only if G has SEMT labelling of G.The proof of Theorem1 can be divided into the proofs of Lemmas 2 and 3.Lemma 2.
Ap,q-graph G admits a strongly c-elegant labelling f if and only if f corresponds a super k,1-magical labelling of G for some integer k.Proof.
⇒) Let f be a strongly c-elegant labelling of G, so we have fVG=0,p−1 and fEG=c,c+q−1 for an integer c. We define another labelling h of G as hu=fu+1 for u∈VG and huv=p+i if fuv=c−1+i with 1≤i≤q. Let k=c+1−p, and we have(6)hu+hv=fu+fv+2=fuv+2=c+i+1=c+i−p+i+p+i+1=k+huv.We notice that hVG=1,p, and it shows that h is a super k,1-magical labelling of G.
⇐) Conversely, assume that f1 is a super t,1-magical labelling of G. We have f1VG=1,p and f1EG=p+1,p+q. Similar to the way above, we define a strongly c-elegant labelling h1 of G by h1u=f1u−1 for u∈VG. Thereby, we define the label h1uv of each edge uv in G as the following form:(7)h1uv=h1u+h1v=f1u+f1v−2=t+f1uv−2,such that h1VG=0,p−1 and h1EG=c,c+q−1 where c=t+p−1, as desired.Lemma 3.
A supert,1-magical labelling of a graph G can induce SEMT labelling of G.Proof.
Letf be a super t,1-magical labelling of G. Hence, fVG=1,p, fEG=p+1,p+q. According to the definition of k,λ-magical labelling, we have(8)fu+fuv+fv=fuv+t+fuv=t+2fuv,which gives us that(9)fu+fuv+fv|uv∈EG=k,k+2⋅1,k+2⋅2,…,k+2⋅q−1,where k=t+2p+1; it turns out that f is a super k,2-EAT labelling of G. Hence, fVG=1,p and f(u+f(uv)+fv|uv∈EG=k,k+2,k+4,…,k+2(q−1). Since f is a super t,1-magical labelling of G by Lemma 3, and there are fu+fv=t+fuv for any edge uv∈EG, where t=k−2p+1.
We define another labellingh of G as hu=fu for u∈VG and huv=2p+q+1−fuv for uv∈EG. Thereby, we have(10)hu+huv+hv=fu+2p+q+1−fuv+fv=t+2p+q+1=k+q−1,which implies that h is SEMT labelling of G since k+q−1 is a constant.


### 3.2. Some Properties on Elegant Labellings

Theorem 4.
A connectedp,q-graph G admits a strongly c-elegant labelling; then, q≤2p−3. If G is a set-ordered strongly c-elegant, then q=p−1.Proof.
Since a strongly c-elegant labellingf of G with fuk=k−1, where uk∈VG=u1,u2,…,up, we have a matrix A=aijp×p as follows: aij=i+j if i≠j and aij=0 if i=j. Clearly, any entry aij is an element of the set a1i|2≤i≤p∪ajp|2≤j≤p−1. Thereby, we have q≤p−1+p−2=2p−3.
Assume thatf is a strongly c-elegant labelling of G, so that G is bipartite and VG=V1∪V2 with V1∩V2=∅ and maxfV1<minfV2. We can define a matrix B=bijp×p by bij=i+j when 1≤i≤V1 and V1+1≤j≤p; otherwise, bij=0. Therefore, the number of different entries bij is at most equal to p−V1+1+1+V1−1=p−1, which means q=p−1 since G is connected.Corollary 5.
LetG be a t-regular p,q-graph with p>6; if G admits a strongly c-elegant labelling, then t=2,3. Especially, p is odd when t=2 and p is even if t=3.Proof.
Letf be a strongly c-elegant labelling of the t-regular p,q-graph G and fEG=c,c+q−1. We compute(11)kq+qq−12=∑uv∈EGfuv=∑uv∈EGfu+fv=t∑u∈VGfu=pp+12tand 2k+q=2p+3 since tp=2q. By Theorem 4, we have t≤4−6/p, which gives t=2,3. When t=2, we have 2k+p=2p+1; thus, p=2k−3. For t=3, we have 4k+3p=4p+6 and then p=22k−3.


## 3.1. The Elegant Labelling and Magic Labelling

In order to achieve the purpose of mutual conversion between labellings, we firstly give the relationship between strongly c-elegant labelling and super-edge magic total labelling and we will show that the problem of determining those trees having EMT labellings can be reduced to the problem of finding strongly c-elegant labellings.Theorem 1.
A graphG admits a strongly c-elegant labelling if and only if G has SEMT labelling of G.The proof of Theorem1 can be divided into the proofs of Lemmas 2 and 3.Lemma 2.
Ap,q-graph G admits a strongly c-elegant labelling f if and only if f corresponds a super k,1-magical labelling of G for some integer k.Proof.
⇒) Let f be a strongly c-elegant labelling of G, so we have fVG=0,p−1 and fEG=c,c+q−1 for an integer c. We define another labelling h of G as hu=fu+1 for u∈VG and huv=p+i if fuv=c−1+i with 1≤i≤q. Let k=c+1−p, and we have(6)hu+hv=fu+fv+2=fuv+2=c+i+1=c+i−p+i+p+i+1=k+huv.We notice that hVG=1,p, and it shows that h is a super k,1-magical labelling of G.
⇐) Conversely, assume that f1 is a super t,1-magical labelling of G. We have f1VG=1,p and f1EG=p+1,p+q. Similar to the way above, we define a strongly c-elegant labelling h1 of G by h1u=f1u−1 for u∈VG. Thereby, we define the label h1uv of each edge uv in G as the following form:(7)h1uv=h1u+h1v=f1u+f1v−2=t+f1uv−2,such that h1VG=0,p−1 and h1EG=c,c+q−1 where c=t+p−1, as desired.Lemma 3.
A supert,1-magical labelling of a graph G can induce SEMT labelling of G.Proof.
Letf be a super t,1-magical labelling of G. Hence, fVG=1,p, fEG=p+1,p+q. According to the definition of k,λ-magical labelling, we have(8)fu+fuv+fv=fuv+t+fuv=t+2fuv,which gives us that(9)fu+fuv+fv|uv∈EG=k,k+2⋅1,k+2⋅2,…,k+2⋅q−1,where k=t+2p+1; it turns out that f is a super k,2-EAT labelling of G. Hence, fVG=1,p and f(u+f(uv)+fv|uv∈EG=k,k+2,k+4,…,k+2(q−1). Since f is a super t,1-magical labelling of G by Lemma 3, and there are fu+fv=t+fuv for any edge uv∈EG, where t=k−2p+1.
We define another labellingh of G as hu=fu for u∈VG and huv=2p+q+1−fuv for uv∈EG. Thereby, we have(10)hu+huv+hv=fu+2p+q+1−fuv+fv=t+2p+q+1=k+q−1,which implies that h is SEMT labelling of G since k+q−1 is a constant.


## 3.2. Some Properties on Elegant Labellings

Theorem 4.
A connectedp,q-graph G admits a strongly c-elegant labelling; then, q≤2p−3. If G is a set-ordered strongly c-elegant, then q=p−1.Proof.
Since a strongly c-elegant labellingf of G with fuk=k−1, where uk∈VG=u1,u2,…,up, we have a matrix A=aijp×p as follows: aij=i+j if i≠j and aij=0 if i=j. Clearly, any entry aij is an element of the set a1i|2≤i≤p∪ajp|2≤j≤p−1. Thereby, we have q≤p−1+p−2=2p−3.
Assume thatf is a strongly c-elegant labelling of G, so that G is bipartite and VG=V1∪V2 with V1∩V2=∅ and maxfV1<minfV2. We can define a matrix B=bijp×p by bij=i+j when 1≤i≤V1 and V1+1≤j≤p; otherwise, bij=0. Therefore, the number of different entries bij is at most equal to p−V1+1+1+V1−1=p−1, which means q=p−1 since G is connected.Corollary 5.
LetG be a t-regular p,q-graph with p>6; if G admits a strongly c-elegant labelling, then t=2,3. Especially, p is odd when t=2 and p is even if t=3.Proof.
Letf be a strongly c-elegant labelling of the t-regular p,q-graph G and fEG=c,c+q−1. We compute(11)kq+qq−12=∑uv∈EGfuv=∑uv∈EGfu+fv=t∑u∈VGfu=pp+12tand 2k+q=2p+3 since tp=2q. By Theorem 4, we have t≤4−6/p, which gives t=2,3. When t=2, we have 2k+p=2p+1; thus, p=2k−3. For t=3, we have 4k+3p=4p+6 and then p=22k−3.


## 4. Constructing Large-Scale Trees

Next, we construct several classes of large-scale trees having strongly c-elegant labellings through graph operations that connect edges between two vertices or overlap two vertices to form a new vertex.Lemma 6.
A treeT on p vertices admits a set-ordered strongly c-elegant labelling f with fET=c,c+q−1; then,ic=V1 where VT=V1∪V2 and V1∩V2=∅, as well as fs<ft for s∈V1 and t∈V2iiThe dual labelling h of f is a set-ordered strongly c-elegant labelling of T with hET=a,a+p−2, where a=p−cProof.
i Let f be a set-ordered strongly c-elegant labelling with fET=c,c+q−1 and maxfs<maxft for s∈V1 and t∈V2; therefore, fs≤V1−1. Since there are two vertices x and y such that fx=p−1=q, fy=c−1, and xy∈ET, we have that c−1≤V1−1. If c−1=V1−1, we are done. Otherwise, c−1<V1−1, so there is an edge st of T with fs=c−1−l≥0 for 0≤l≤c−1 such that fs+ft=c, and moreover, ft=1+l and c<V1≤ft=1+l, which means that c−l<1, a contradiction. ii Since huv=2p−1−fuv, then(12)hET=2p−1−c+q−1,2p−1−c=a,a+p−2,where a=p−c.Lemma 7.
Given two treesTi on pi vertices with VTi=V1i∪V2i and V1i∩V2i=∅, each Ti admits a set-ordered strongly c-elegant labelling fi for i=1,2.(1)
Adjoin a certain vertex inT1 to a certain vertex in T2 such that the resultant graph H admits a set-ordered strongly c-elegant labelling h with hEH=V11+V22,V11+V22+p1+p2−2(2)
Identity a certain vertex inT1 to a certain vertex in T2 such that the resultant graph H′ admits a set-ordered strongly c-elegant labelling g with gEH′=V11+V12−1,V11+V12+V22+p2−2Proof.
LetfiETi=V1i,V1i+pi−2 for i=1,2, by Lemma 6. Since fis<fit when s∈V1i and t∈V2i for i=1,2, there are p1−1=f1u>f1x for u,x∈V21 and V12−1=f2v>f2y for v,y∈V12 and V11−1=f1w>f1x′ for w,x′∈V11 and 0=f2z<f2y′ for z,y′∈V12:(1)
We have a treeH obtained by adjoining u of T1 to v of T2 with an edge uv, and we give a set-ordered strongly c-elegant labelling h as follows: hs=f1s if s∈V11; hs=V11+V12−1−f2s if s∈V12; hs=V11+V12−1+f1s−V11+1=V12+f1s if s∈V21; hs=V12+p1−1+p2−1−f2s+1=V12+p1+p2−1−f2s if s∈V12. For an edge st∈ET1 of H, we notice that(13)huv=hu+hv=V12+f1u+V11+V12−1−f2v=V11+V12+p1−1.Thus, hst=hs+ht=V12+f1s+f1t=f1st+V12. It turns out that hET1=V11+V12,V11+V12+p1−2, where T1⊂H. If edge st∈ET2, s∈V12 and t∈V22, and hst=hs+ht=V11+V12−1−f2s+p1+p2−f2t−1+V12=2V12+V11+p1+p2−2−f2st, there is(14)hET2=V11+V22+p1,V11+V22+p1+p2−2,so hEH=V11+V22,V11+V22+p1+p2−2. We set V1=V11∪V12 and V2=V21∪V22; then, V1,V2 is a vertex partition of H, which proves that h is a set-ordered strongly c-elegant labelling of the graph H.(2)
We can obtain another treeH′ by identifying vertex w of T1 to vertex z of T2 into a vertex. Next, we give a set-ordered strongly c-elegant labelling g of H′ as follows: gs=f1s if s∈V11; gs=f2s+V11−1 if s∈V12; gs=f1s+V12−1 if s∈V21; gs=f2s+V21+1 if s∈V22.
Forst∈ET1, we have gst=V12−1+f1st and gET1=V11+V12−1,V11+V12+p1−3. If st∈ET2, then gst=V11+V21+f2st=f2st+p1, which leads that gET2=V11+V12+V22,V11+V12+V22+p2−2. V11∪12V12,V21∪V22 is a vertex partition of H′, and gEH′=V11+V12−1,V11+V12+V22+p2−2Theorem 8.
Given two treesTi on pi vertices with VTi=V1i∪V2i and V1i∩V2i=∅, each Ti has a strongly c-elegant labelling fi with fiETi=bi+1,bi+pi−1 for i=1,2. If f2 is a set-ordered strongly c-elegant labelling and if there is an edge uv of T1 with f1u<f1v such that two components H1 and H2 of T1−uv satisfy that(1)
f1EH1=c1,f1uv−1 and f1EH2=f1uv+1,c1+q1−1, where f1ET1∖f1uv=c1,f1uv−1∪f1uv+1,c1+q1−1.(2)
SinceHii=1,2 are bipartite, VHi=S1i∪S2i and S1i∩S2i=∅ for i=1,2; there is f1VT1=0,p1−1=f1S11∪f1S21∪f1S12∪f1S22, where f1S11=0,f1u−1, f1S21∪S12=f1u,f1v, f1S22=f1v+1,p1−1, and u∈S12 and v∈S21.Then, there are two verticesx and y of T2 such that the graph H obtained by adjoining u to x with the edge ux and adjoining v to y with the edge vy between T1 and T2 and then deleting the edge uv has a strongly c-elegant labelling h with hEH=V12+c1,V12+c1+p1+p2−2.Proof.
Letf2 be a set-ordered strongly c-elegant labelling of the bipartite graph T2 on p2 vertices from f2VT2=0,p2−1, such that maxf2s<minf2t for s∈V12 and t∈V22 and f2ET2=V12,V12+p2−2.
Therefore, there are two verticesx and y of T2 such that 0=f2y≤f2z≤f2x=p2−1 for z∈VT2. We construct the graph H by adjoining ux and vy between T1 and T2 and then deleting the edge uv. Clearly, H is a tree with p1+p2 vertices and q1+q2+1 edges. Consequently, we define another labelling h of H as follows: hs=f1s if s∈S11; here, S11=f1u; hs=f1u+f2s if s∈V12; hs=f1s+V12 if s∈S21∪S12; hs=f1v+f2s+1 if s∈V22; and hs=p2+f1s if s∈S22.
Obviously,hVH=0,p1+p2−1. In the following discussion, we shall estimate hEH=hst=hs+ht under this labelling h.Case 1.
Forst∈EH1, there is s∈S11 and t∈S21. Thereby, we have(15)hst=hs+ht=f1s+f1t+V12=V12+f1st.Hence, hEH1=V12+c1,V12+c1+1/2q1−1−1.Case 2.
hvy=v+hy=f1v+V12+f1u=V12+f1uv.Case 3.
For an edgest∈ET2 with respect to s∈V12 and t∈V22, we can obtain hET2=V12+f1uv+1,V12+f1uv+p2−1 since(16)hst=hs+ht=f1u+f2s+f1v+f2t+1=f1uv+f2st+1and f2ET2=V12,V12+p2−2 by Lemma 6.Case 4.
hux=hu+hx=f1u+V12+f1v+f2x+1=V12+f1uv+p2.Case 5.
Forst∈EH2, there is s∈S12 and t∈S22; thereby, we have(17)hst=hs+ht=f1s+V12+f1t+p2=V12+f1st+p2.It turns out that hEH2=V12+f1uv+p2+1,V12+p2+c1+p1−2.
We have shown thathEH=V12+c1,V12+c1+p1+p2−2 through Case 1 to Case 5, namely, h is a strongly c-elegant labelling of H.
An example illustrating Theorem8 is shown in Figure 2.Figure 2
(a) A treeT1 admits a strongly c-elegant labelling. (b) Another tree T2 admits a set-ordered strongly c-elegant labelling. (c) An example of Theorem 8 based on two graphs shown in 2a.
(a)(b)(c)


### 4.1. Generalized Caterpillars

Theorem 9.
A caterpillar withp vertices admits a set-ordered strongly c-elegant labelling.Proof.
LetℒT be the set of all leaves of a caterpillar T with p vertices. By the definition of caterpillars, the graph T−ℒT is a path P=u1u2⋯um for m≥1. Let Si=u1i,u2i,…,unii be the set of all leaves adjacent to ui∈VP with 1≤i≤m. Clearly, ℒT=∪i=1mSi.
Ifm=1, the caterpillar T becomes a star; we have a set-ordered strongly c-elegant labelling h of T as follows: hu1=0 and huj1=j for 1≤j≤p−1 and hu1uj1=hu1+huj1=j for 1≤j≤p−1.
Ifm≥2, we define a set-ordered strongly c-elegant labelling f of the caterpillar T as follows. Let ∑l=10n2l=0 and s=⌊m+1/2⌋. We define(18)fu2t−1=t−1+∑l=1t−1n2l,fuj2t=fu2t−1+j,with respect to 1≤j≤n2t and 1≤t≤s−ε where ε=0 if m is even and ε=1 if m is odd.(1)
For even integerm, we let Q=fun2s2s=fu2s−1+n2s and label fuj1=Q+j for 1≤j≤n1, and(19)fu2t=Q+t+∑l=1tn2l−1,fuj2t+1=fu2t+j,with respect to 1≤j≤n2t+1 and 1≤t≤s−1. Thereby, we label fum=fu2s=q. We set X=u2t−1∪S2t and Y=u2t∪S2t−1.(2)
For odd integerm, we let R=fum=s+∑l=1s−1n2l−1 and set fuj1=R+j for 1≤j≤n1,(20)fu2t=R+t+∑l=1tn2l−1,fuj2t+1=fu2t+j,with respect to 1≤j≤n2t+1 and 1≤t≤s−1; therefore, fun2s−12s−1=funmm=q.
The rest part of the proof is to verify the edge labels ofT. If the path P=u1u2⋯um has the even number of vertices, fET=Q+1,Q+p−1 where(21)Q+1=fu1u11=0+fu11,Q+p−1=fumunmm=fum+fumunmm.
Whenm is odd, there is fET=R+1,R+p−1, where(22)R+1=fu1u11=0+fu11,R+p−1=fumunmm=fum+fumunmm.
In this case, we setX=u2t−1∪um∪S2t and Y=u2t∪S2t−1∪Sm, so X,Y is vertex bipartite of caterpillar T and maxfX<minfY; therefore, we show f is a set-ordered strongly c-elegant labelling of T.
Adjoin a vertexu of tree Ti and a vertex v of tree Ti+1 with an edge uv for 1≤i≤m−1; the resulting tree is denoted as PmT1,T2,…,Tm.Theorem 10.
IfTi is a caterpillar for 1≤i≤m, then PmT1,T2,…,Tm admits a set-ordered strongly c-elegant labelling.Proof.
Each treeTi with pi vertices and qi edges has a set-ordered strongly c-elegant labelling fi such that fis<fit for s∈V1i and t∈V2i where VTi=V1i∪V2i and V1i∩V2i=∅ for i∈1,m. Let m1i=V1i and m2i=V2i, and we define a labelling h on these m trees by relabelling each vertex of Ti, when i=1: hu=f1u if u∈V11; hu=f1u+∑j=1mV1j+1−V11 if u∈V21.
Generally, for1<i≤m, we have hu=fiu+∑j=1i−1V1j=fiu+∑j=1i−1m1j if u∈V1i and hu=∑j=1mm1j+∑j=1i−1m2j−m1i+fiu if u∈V2i.
Ifuv∈ET1 and u∈V11 and v∈V21, then huv=hu+hv=f1u+f1v+∑j=1mm1j+1−m11=f1uv+∑j=2mm1j+1, so hET1=m11+∑j=2mm1j+1,m11+q1+∑j=2mm1j. We compute huv for uv∈ETi, where 2≤i≤m, and we obtain huv=fiuv+∑j=1i−1m1j+m2i+∑j=1mm1j−m1i, so hETi=∑j=1i−1qj+∑j=1mm1j,∑j=1i−1qj+∑j=1mm1j+qi−1.
We usefiui=maxfiV1i to represent the maximum vertex label in V1i and fi+1vi+1=minfi+1V2i+1 is the minimum vertex label in V2i+1. We get graph PmT1,T2,…,Tm by connecting vertices ui and vi+1, and the label of edge uivi+1 is huivi+1=hui+hvi+1=fiui+fi+1vi+1+∑j=1i−1m1j∑j=1mm1j+∑j=1im2j−m1i+1; obviously, huv<huivi+1<hst for uv∈ETi and st∈ETi+1. In addition, we set X=V11∪V12V1m∪⋯V1m and Y=V21∪V22∪⋯V2m, so X,Y is a vertex bipartite of tree PmT1,T2,…,Tm; it can be calculated that the largest label of the edge in Tm is ∑j=1m−1qj+∑j=1mm1j+qm−1=∑j=1mm1j+∑j=1mqj−1. Based on the above content, we obtain h is a set-ordered strongly c-elegant labelling of PmT1,T2,…,Tm (see an example in Figure 3).Figure 3
A caterpillarP4T1,T2,T3,T4 with 67 vertices.


### 4.2. Generalized Lobsters

InPmT1,T2,…,Tm, when each tree Ti is a star K1,ni, then we have known that each lobster PmK1,n1,K1,n2,…,K1,nm admits a set-ordered strongly c-elegant labelling and the symbol PmK1,n denotes PmK1,n,K1,n,…,K1,n. A spider is a tree whose vertices have at most degree 2, except only one vertex u0 whose degree is not less than 3, and u0 is called the center of the spider. Thereby, we can depict this spider by linking u0 to an initial vertex of a path (called a leg of the spider) with li vertices, i=1,2,…,n, and write this spider by Sl1,l2,…,ln; each li indicates the length of i th leg. If l1=l2=⋯=ln=k, abbreviate it as Snk and name it in term of nk-regular spider. We will use some particular spiders to construct some large scale of lobsters.Corollary 11.
LobsterPmK1,n admit a set-ordered strongly c-elegant labelling.For1≤j≤m, let Skj denote a spider Sln1,ln2,…,lnkj with the center vertices uj and kj≠0 and legs Pij=ui,1jui,2j⋯ui,nij, where ui,1j is the initial vertex of the leg Pij for 1≤i≤kj. A spider-lobster LSk1,Sk2,…,Skm is obtained by adjoining each pair of center vertices uj and uj+1 between spiders Skj and Skj+1 with an edge ujuj+1 for 1≤j≤m−1. We say u1 and um the initial vertex and terminal vertex of the spider-lobster LSk1,Sk2,…,Skm. If any ni is equal to k for 1≤i≤kj and 1≤j≤m, we denote this spider-lobster by LkSk1,Sk2,…,Skm. Moreover, if kj=n for 1≤j≤m in LkSk1,Sk2,…,Skm, thus we use a simple notation Tm×nk to replace LkSk1,Sk2,…,Skm.Lemma 12.
Each lobsterT2×n2 has a strongly c-elegant labelling.Proof.
The number of vertices of lobsterT2×n2 is 4n+2, and we have the i th leg Pij=ui,1jui,2j of each spider Sn2j for j=1,2. We define a labelling f of the lobster T2×n2 as follows: fui,11=i−1 and fui,12=3n+1+i for 1≤i≤n; further, fui,22=3n−2i+1 and fui,21=fui,22+1 for 1≤i≤n. Again, we set fu02=n and fu01=3n+1. Thereby, fVT2×n2=0,4n+1 since fu1,11=0 and fun,12=4n+1. Furthermore, we have fui,11ui,21=fui,11+fui,21=i−1+3n−2i+1+1=3n−i+1,1≤i≤n; fui,11u01=fui,11+fu01=i+3n,1≤i≤n; fu01u02=fu01+fu02=4n+1; fui,12u02=fui,12+fu02=3n+1+i+n=4n+1+i,1≤i≤n; and fui,12ui,22=fui,12+fui,22=3n+1+i+3n−2i+1=6n+2−i,1≤i≤n, so fET2×n2=2n+1,6n+1, and it is easy to see that f is a strongly c-elegant labelling of the lobster T2×n2.
In spider-lobstersLSk1,Sk2,…,Skm, we allow some spider Skj to be an isolated vertex. We will find some strongly c-elegant labellings for two particular classes of spider-lobsters Lk(Sk1,Sk2,… , Skm). Let m be even and n be a positive integer. The first class of lobsters Hm,nk0 can be defined by setting kj=n if j is odd; otherwise, kj=0 in LkSk1,Sk2,…,Skm. Similarly, the second class of lobsters Hm,nk1 is constructed by letting kj=n if j is odd; otherwise, kj=1 in LkSk1,Sk2,…,Skm.Lemma 13.
Both lobstersH4,n20 and H4,n21 have a set-ordered strongly c-elegant labelling.Proof.
Notice thatH4,n20=L2Sk1,Sk2,Sk3,Sk4 is a lobster on n+1 vertices, where k1=k3=n and k2=k4=0. Hence, for j=1,3, we have VSkj=uj∪∪i=1nVPij where VPij=ui,1j,ui,2j for 1≤i≤n, and when j=2,4, we have VSkj=uj. A labelling f of the lobster H4,n20 can be defined in following forms:(1)
fu1=0, fu2=3n+2, fu3=2n+1, and fu4=4n+3(2)
fui,11=fu3+i and fui,13=fu2+i for 1≤i≤n(3)
fun−i+1,23=2i−1 and fun−i+1,21=2i for 1≤i≤n
It is not hard to obtainfVH4,n20=0,4n+3 and fEH4,n20=2n+2,6n+4; we set X=u1,u3∪un−i+1,21∪un−i+1,23 and Y=u2,u4∪ui,11∪ui,13, and maxfX<minfY, and it shows that f is truly a set-ordered strongly c-elegant labelling of H4,n20.
We have known the lobsterH4,n21=L2Sk1,Sk2,Sk3,Sk4 where k1=k3=n and k2=k4=1. When j=1,3, VSkj is the same as that of H4,n20. For j=2,4, VSkj=uj∪ui,1j. We construct a set-ordered strongly c-elegant labelling h for the lobster H4,n21 as follows:(1)
hu1=0, hu2=3n+4, hu3=2n+2, hu4=4n+5;(2)
hui,12=1, hui,14=2n+3, hui,11=hui,14+i, and hui,13=hu2+i for 1≤i≤n(3)
hun−i+1,23=2i and hun−i+1,21=2i+1 for 1≤i≤n
Notice thatH4,n21 has 4n+6 vertices, and we can easily compute hVH4,n21=0,4n+5 and hEH4,n21=2n+4,6n+8; we set X′=u1,u3∪un−i+1,21∪un−i+1,23∪ui,12,ui,14, Y′=u2,u4∪ui,11∪ui,13, and maxhX′<minhY′, so h is a set-ordered strongly c-elegant labelling of H4,n21.Theorem 14.
Supposet lobsters H4,ns2js, where js=0 or 1 and 1≤s≤t. A lobster Gt is determined by adjoining successively the initial vertex of H4,ni+12j to the terminal vertex of H4,ni2j for 1≤i≤t−1; this admits a set-ordered strongly c-elegant labelling.Proof.
SinceH4,ns2js admits a set-ordered strongly c-elegant labelling fss=1,2 shown as in the proof of Lemma 13, we have VH4,ns2js=V1s∪V2s and fsu<fsv for all u∈V1s and v∈V2s for s=1,2.
LetVH4,ns2js=ps for s=1,2. Adjoining the terminal vertex u with f1u=p1−1 to the initial vertex v with f2v=0, we have a lobster G2. We define a set-ordered strongly c-elegant labelling h of G2 as hx=f1x whenever x∈V11; hy=f2y+V11−1 if y∈V12; hx=f1x+V11+V12−1 whenever x∈V21; and hy=f2y+p1+V12−1 if y∈V22. By the induction, the rest part of the proof of this theorem is obvious and we omit it.Corollary 15.
Suppose two lobsters having set-ordered strongly c-elegant labellings. A lobster constructed by adjoining the terminal vertex of a lobster to the initial vertex of the rest lobster has a set-ordered strongly c-elegant labelling.


### 4.3. Transformation on Strongly c-Elegant Labellings

Letf be a strongly c-elegant labelling of a tree T with p vertices such that fET=c,c+q−1. Obviously, for an edge uv∉ET, the graph T+uv obtained by adding the edge uv to T contains the uniquely cycle C. We have three concepts in the following:(1)
If there is an edgeu′v′ in C such that fu+fv=fu′+fv′, another tree T′=T+uv−u′v′ admits this strongly c-elegant labelling f and keeps fET′=c,c+q−1. It is convenient to say T′ as a left transformation of T under f and write T′=LT. We are easy to define the inverse transformation L−1 of a left transformation L, that is, T=L−1T′ by T=T′+u′v′−uv under f.(2)
Analogously, foruv,xy∉ET, the graph H=T+uv,xy has two cycles C1 and C2 such that fu+fv=fx′+fy′ and fx+fy=fu′+fv′ where uv,u′v′∈EC1 and xy,x′y′∈EC2 and uv,u′v′,xy,x′y′∉EC1∩EC2. Thereby, we have a tree H′=H−u′v′,x′y′ which admits this strongly c-elegant labelling f and fEH′=c,c+q−1. We say H′ to be a right transformation of T under f, denoted by H′=TR. Clearly, T=H′R−1 where R−1 is the inverse transformation of a right transformation R.(3)
If there is an edgeu′v′ in C such that fu+fv=c and fu′+fv′=c+q, the tree T′=T+uv−u′v′ admits this strongly c-elegant labelling f and keeps fET′=c+1,c+q. We say T′ as an increasing transformation of T under f and write T′=IT. Moreover, we have T=I−1T′. However, a star denies left and right transformations since the star Sn on n vertices has a uniquely strongly c-elegant labelling f with 1,n−1. Thereby, we have a caterpillar T=Sn+uv−u′v′ that admits a strongly c-elegant labelling h with 2,n; namely, T is an increasing transformation of the star Sn under f.An example illustrating the above definition is shown in Figure4.Figure 4
(a) A caterpillar with a strongly c-elegant labelling with6,13. (b) A caterpillar T with a strongly c-elegant labelling with 5,12. (c) A left transformation LT of T. (d) A right transformation LTR of LT.
(a)(b)(c)(d)Theorem 16.
LetT be a tree with p>2 vertices having a strongly c-elegant labelling. If T is not a star, either there is a left transformation of T or a right transformation of T.Proof.
Letf be a strongly c-elegant labelling of a tree T on p vertices and fET=c,c+q−1. There are two vertices u and v such that fu+fv=c+q−1. We take a vertex w with fw<minfu,fv since fu+fv=c+q−1>c and T is not a star. Thereby, the graph H=T+uw contains a cycle C and there is an edge xy such that fu+fw=fx+fy since fET=c,c+q−1.
If edgexy belongs to C, we have a tree T′=H−xy having the strongly c-elegant labelling f with fET′=c,c+q−1. Obviously, T′ is a left transformation of T.
Ifxy∉C, we have c+q−1=fu+fv=fx+fy+fv−fw, and furthermore, we can find a vertex z in H such that fz=fy+fv−fw. Hence, the graph H′=H+xz+uw has two cycles. We have a right transformation of T as T′=H′−uv,xy admitted as a strongly c-elegant labelling f with fET′=c,c+q−1. This theorem has been proved.


## 4.1. Generalized Caterpillars

Theorem 9.
A caterpillar withp vertices admits a set-ordered strongly c-elegant labelling.Proof.
LetℒT be the set of all leaves of a caterpillar T with p vertices. By the definition of caterpillars, the graph T−ℒT is a path P=u1u2⋯um for m≥1. Let Si=u1i,u2i,…,unii be the set of all leaves adjacent to ui∈VP with 1≤i≤m. Clearly, ℒT=∪i=1mSi.
Ifm=1, the caterpillar T becomes a star; we have a set-ordered strongly c-elegant labelling h of T as follows: hu1=0 and huj1=j for 1≤j≤p−1 and hu1uj1=hu1+huj1=j for 1≤j≤p−1.
Ifm≥2, we define a set-ordered strongly c-elegant labelling f of the caterpillar T as follows. Let ∑l=10n2l=0 and s=⌊m+1/2⌋. We define(18)fu2t−1=t−1+∑l=1t−1n2l,fuj2t=fu2t−1+j,with respect to 1≤j≤n2t and 1≤t≤s−ε where ε=0 if m is even and ε=1 if m is odd.(1)
For even integerm, we let Q=fun2s2s=fu2s−1+n2s and label fuj1=Q+j for 1≤j≤n1, and(19)fu2t=Q+t+∑l=1tn2l−1,fuj2t+1=fu2t+j,with respect to 1≤j≤n2t+1 and 1≤t≤s−1. Thereby, we label fum=fu2s=q. We set X=u2t−1∪S2t and Y=u2t∪S2t−1.(2)
For odd integerm, we let R=fum=s+∑l=1s−1n2l−1 and set fuj1=R+j for 1≤j≤n1,(20)fu2t=R+t+∑l=1tn2l−1,fuj2t+1=fu2t+j,with respect to 1≤j≤n2t+1 and 1≤t≤s−1; therefore, fun2s−12s−1=funmm=q.
The rest part of the proof is to verify the edge labels ofT. If the path P=u1u2⋯um has the even number of vertices, fET=Q+1,Q+p−1 where(21)Q+1=fu1u11=0+fu11,Q+p−1=fumunmm=fum+fumunmm.
Whenm is odd, there is fET=R+1,R+p−1, where(22)R+1=fu1u11=0+fu11,R+p−1=fumunmm=fum+fumunmm.
In this case, we setX=u2t−1∪um∪S2t and Y=u2t∪S2t−1∪Sm, so X,Y is vertex bipartite of caterpillar T and maxfX<minfY; therefore, we show f is a set-ordered strongly c-elegant labelling of T.
Adjoin a vertexu of tree Ti and a vertex v of tree Ti+1 with an edge uv for 1≤i≤m−1; the resulting tree is denoted as PmT1,T2,…,Tm.Theorem 10.
IfTi is a caterpillar for 1≤i≤m, then PmT1,T2,…,Tm admits a set-ordered strongly c-elegant labelling.Proof.
Each treeTi with pi vertices and qi edges has a set-ordered strongly c-elegant labelling fi such that fis<fit for s∈V1i and t∈V2i where VTi=V1i∪V2i and V1i∩V2i=∅ for i∈1,m. Let m1i=V1i and m2i=V2i, and we define a labelling h on these m trees by relabelling each vertex of Ti, when i=1: hu=f1u if u∈V11; hu=f1u+∑j=1mV1j+1−V11 if u∈V21.
Generally, for1<i≤m, we have hu=fiu+∑j=1i−1V1j=fiu+∑j=1i−1m1j if u∈V1i and hu=∑j=1mm1j+∑j=1i−1m2j−m1i+fiu if u∈V2i.
Ifuv∈ET1 and u∈V11 and v∈V21, then huv=hu+hv=f1u+f1v+∑j=1mm1j+1−m11=f1uv+∑j=2mm1j+1, so hET1=m11+∑j=2mm1j+1,m11+q1+∑j=2mm1j. We compute huv for uv∈ETi, where 2≤i≤m, and we obtain huv=fiuv+∑j=1i−1m1j+m2i+∑j=1mm1j−m1i, so hETi=∑j=1i−1qj+∑j=1mm1j,∑j=1i−1qj+∑j=1mm1j+qi−1.
We usefiui=maxfiV1i to represent the maximum vertex label in V1i and fi+1vi+1=minfi+1V2i+1 is the minimum vertex label in V2i+1. We get graph PmT1,T2,…,Tm by connecting vertices ui and vi+1, and the label of edge uivi+1 is huivi+1=hui+hvi+1=fiui+fi+1vi+1+∑j=1i−1m1j∑j=1mm1j+∑j=1im2j−m1i+1; obviously, huv<huivi+1<hst for uv∈ETi and st∈ETi+1. In addition, we set X=V11∪V12V1m∪⋯V1m and Y=V21∪V22∪⋯V2m, so X,Y is a vertex bipartite of tree PmT1,T2,…,Tm; it can be calculated that the largest label of the edge in Tm is ∑j=1m−1qj+∑j=1mm1j+qm−1=∑j=1mm1j+∑j=1mqj−1. Based on the above content, we obtain h is a set-ordered strongly c-elegant labelling of PmT1,T2,…,Tm (see an example in Figure 3).Figure 3
A caterpillarP4T1,T2,T3,T4 with 67 vertices.


## 4.2. Generalized Lobsters

InPmT1,T2,…,Tm, when each tree Ti is a star K1,ni, then we have known that each lobster PmK1,n1,K1,n2,…,K1,nm admits a set-ordered strongly c-elegant labelling and the symbol PmK1,n denotes PmK1,n,K1,n,…,K1,n. A spider is a tree whose vertices have at most degree 2, except only one vertex u0 whose degree is not less than 3, and u0 is called the center of the spider. Thereby, we can depict this spider by linking u0 to an initial vertex of a path (called a leg of the spider) with li vertices, i=1,2,…,n, and write this spider by Sl1,l2,…,ln; each li indicates the length of i th leg. If l1=l2=⋯=ln=k, abbreviate it as Snk and name it in term of nk-regular spider. We will use some particular spiders to construct some large scale of lobsters.Corollary 11.
LobsterPmK1,n admit a set-ordered strongly c-elegant labelling.For1≤j≤m, let Skj denote a spider Sln1,ln2,…,lnkj with the center vertices uj and kj≠0 and legs Pij=ui,1jui,2j⋯ui,nij, where ui,1j is the initial vertex of the leg Pij for 1≤i≤kj. A spider-lobster LSk1,Sk2,…,Skm is obtained by adjoining each pair of center vertices uj and uj+1 between spiders Skj and Skj+1 with an edge ujuj+1 for 1≤j≤m−1. We say u1 and um the initial vertex and terminal vertex of the spider-lobster LSk1,Sk2,…,Skm. If any ni is equal to k for 1≤i≤kj and 1≤j≤m, we denote this spider-lobster by LkSk1,Sk2,…,Skm. Moreover, if kj=n for 1≤j≤m in LkSk1,Sk2,…,Skm, thus we use a simple notation Tm×nk to replace LkSk1,Sk2,…,Skm.Lemma 12.
Each lobsterT2×n2 has a strongly c-elegant labelling.Proof.
The number of vertices of lobsterT2×n2 is 4n+2, and we have the i th leg Pij=ui,1jui,2j of each spider Sn2j for j=1,2. We define a labelling f of the lobster T2×n2 as follows: fui,11=i−1 and fui,12=3n+1+i for 1≤i≤n; further, fui,22=3n−2i+1 and fui,21=fui,22+1 for 1≤i≤n. Again, we set fu02=n and fu01=3n+1. Thereby, fVT2×n2=0,4n+1 since fu1,11=0 and fun,12=4n+1. Furthermore, we have fui,11ui,21=fui,11+fui,21=i−1+3n−2i+1+1=3n−i+1,1≤i≤n; fui,11u01=fui,11+fu01=i+3n,1≤i≤n; fu01u02=fu01+fu02=4n+1; fui,12u02=fui,12+fu02=3n+1+i+n=4n+1+i,1≤i≤n; and fui,12ui,22=fui,12+fui,22=3n+1+i+3n−2i+1=6n+2−i,1≤i≤n, so fET2×n2=2n+1,6n+1, and it is easy to see that f is a strongly c-elegant labelling of the lobster T2×n2.
In spider-lobstersLSk1,Sk2,…,Skm, we allow some spider Skj to be an isolated vertex. We will find some strongly c-elegant labellings for two particular classes of spider-lobsters Lk(Sk1,Sk2,… , Skm). Let m be even and n be a positive integer. The first class of lobsters Hm,nk0 can be defined by setting kj=n if j is odd; otherwise, kj=0 in LkSk1,Sk2,…,Skm. Similarly, the second class of lobsters Hm,nk1 is constructed by letting kj=n if j is odd; otherwise, kj=1 in LkSk1,Sk2,…,Skm.Lemma 13.
Both lobstersH4,n20 and H4,n21 have a set-ordered strongly c-elegant labelling.Proof.
Notice thatH4,n20=L2Sk1,Sk2,Sk3,Sk4 is a lobster on n+1 vertices, where k1=k3=n and k2=k4=0. Hence, for j=1,3, we have VSkj=uj∪∪i=1nVPij where VPij=ui,1j,ui,2j for 1≤i≤n, and when j=2,4, we have VSkj=uj. A labelling f of the lobster H4,n20 can be defined in following forms:(1)
fu1=0, fu2=3n+2, fu3=2n+1, and fu4=4n+3(2)
fui,11=fu3+i and fui,13=fu2+i for 1≤i≤n(3)
fun−i+1,23=2i−1 and fun−i+1,21=2i for 1≤i≤n
It is not hard to obtainfVH4,n20=0,4n+3 and fEH4,n20=2n+2,6n+4; we set X=u1,u3∪un−i+1,21∪un−i+1,23 and Y=u2,u4∪ui,11∪ui,13, and maxfX<minfY, and it shows that f is truly a set-ordered strongly c-elegant labelling of H4,n20.
We have known the lobsterH4,n21=L2Sk1,Sk2,Sk3,Sk4 where k1=k3=n and k2=k4=1. When j=1,3, VSkj is the same as that of H4,n20. For j=2,4, VSkj=uj∪ui,1j. We construct a set-ordered strongly c-elegant labelling h for the lobster H4,n21 as follows:(1)
hu1=0, hu2=3n+4, hu3=2n+2, hu4=4n+5;(2)
hui,12=1, hui,14=2n+3, hui,11=hui,14+i, and hui,13=hu2+i for 1≤i≤n(3)
hun−i+1,23=2i and hun−i+1,21=2i+1 for 1≤i≤n
Notice thatH4,n21 has 4n+6 vertices, and we can easily compute hVH4,n21=0,4n+5 and hEH4,n21=2n+4,6n+8; we set X′=u1,u3∪un−i+1,21∪un−i+1,23∪ui,12,ui,14, Y′=u2,u4∪ui,11∪ui,13, and maxhX′<minhY′, so h is a set-ordered strongly c-elegant labelling of H4,n21.Theorem 14.
Supposet lobsters H4,ns2js, where js=0 or 1 and 1≤s≤t. A lobster Gt is determined by adjoining successively the initial vertex of H4,ni+12j to the terminal vertex of H4,ni2j for 1≤i≤t−1; this admits a set-ordered strongly c-elegant labelling.Proof.
SinceH4,ns2js admits a set-ordered strongly c-elegant labelling fss=1,2 shown as in the proof of Lemma 13, we have VH4,ns2js=V1s∪V2s and fsu<fsv for all u∈V1s and v∈V2s for s=1,2.
LetVH4,ns2js=ps for s=1,2. Adjoining the terminal vertex u with f1u=p1−1 to the initial vertex v with f2v=0, we have a lobster G2. We define a set-ordered strongly c-elegant labelling h of G2 as hx=f1x whenever x∈V11; hy=f2y+V11−1 if y∈V12; hx=f1x+V11+V12−1 whenever x∈V21; and hy=f2y+p1+V12−1 if y∈V22. By the induction, the rest part of the proof of this theorem is obvious and we omit it.Corollary 15.
Suppose two lobsters having set-ordered strongly c-elegant labellings. A lobster constructed by adjoining the terminal vertex of a lobster to the initial vertex of the rest lobster has a set-ordered strongly c-elegant labelling.


## 4.3. Transformation on Strongly c-Elegant Labellings

Letf be a strongly c-elegant labelling of a tree T with p vertices such that fET=c,c+q−1. Obviously, for an edge uv∉ET, the graph T+uv obtained by adding the edge uv to T contains the uniquely cycle C. We have three concepts in the following:(1)
If there is an edgeu′v′ in C such that fu+fv=fu′+fv′, another tree T′=T+uv−u′v′ admits this strongly c-elegant labelling f and keeps fET′=c,c+q−1. It is convenient to say T′ as a left transformation of T under f and write T′=LT. We are easy to define the inverse transformation L−1 of a left transformation L, that is, T=L−1T′ by T=T′+u′v′−uv under f.(2)
Analogously, foruv,xy∉ET, the graph H=T+uv,xy has two cycles C1 and C2 such that fu+fv=fx′+fy′ and fx+fy=fu′+fv′ where uv,u′v′∈EC1 and xy,x′y′∈EC2 and uv,u′v′,xy,x′y′∉EC1∩EC2. Thereby, we have a tree H′=H−u′v′,x′y′ which admits this strongly c-elegant labelling f and fEH′=c,c+q−1. We say H′ to be a right transformation of T under f, denoted by H′=TR. Clearly, T=H′R−1 where R−1 is the inverse transformation of a right transformation R.(3)
If there is an edgeu′v′ in C such that fu+fv=c and fu′+fv′=c+q, the tree T′=T+uv−u′v′ admits this strongly c-elegant labelling f and keeps fET′=c+1,c+q. We say T′ as an increasing transformation of T under f and write T′=IT. Moreover, we have T=I−1T′. However, a star denies left and right transformations since the star Sn on n vertices has a uniquely strongly c-elegant labelling f with 1,n−1. Thereby, we have a caterpillar T=Sn+uv−u′v′ that admits a strongly c-elegant labelling h with 2,n; namely, T is an increasing transformation of the star Sn under f.An example illustrating the above definition is shown in Figure4.Figure 4
(a) A caterpillar with a strongly c-elegant labelling with6,13. (b) A caterpillar T with a strongly c-elegant labelling with 5,12. (c) A left transformation LT of T. (d) A right transformation LTR of LT.
(a)(b)(c)(d)Theorem 16.
LetT be a tree with p>2 vertices having a strongly c-elegant labelling. If T is not a star, either there is a left transformation of T or a right transformation of T.Proof.
Letf be a strongly c-elegant labelling of a tree T on p vertices and fET=c,c+q−1. There are two vertices u and v such that fu+fv=c+q−1. We take a vertex w with fw<minfu,fv since fu+fv=c+q−1>c and T is not a star. Thereby, the graph H=T+uw contains a cycle C and there is an edge xy such that fu+fw=fx+fy since fET=c,c+q−1.
If edgexy belongs to C, we have a tree T′=H−xy having the strongly c-elegant labelling f with fET′=c,c+q−1. Obviously, T′ is a left transformation of T.
Ifxy∉C, we have c+q−1=fu+fv=fx+fy+fv−fw, and furthermore, we can find a vertex z in H such that fz=fy+fv−fw. Hence, the graph H′=H+xz+uw has two cycles. We have a right transformation of T as T′=H′−uv,xy admitted as a strongly c-elegant labelling f with fET′=c,c+q−1. This theorem has been proved.


## 5. Conclusion and Problems

In this paper, we mainly have studied the equivalence between strong c-elegant labelling, super-edge magic total labelling, edge antimagic total labelling, and supert,1-magical labelling. Starting from small-scale graphs with strong c-elegant labelling, several large-scale graphs with strong c-elegant labellings are constructed. We have defined a transformation about strong c-elegant labelling. The object used in the encryption process is no longer just a labelling of a graph, but these methods can provide more text passwords for topological encryption and provide new ideas for expanding the topological password space. At the end of this paper, we propose several problems:Problem 1. Can a tree H that admits a strongly c-elegant labelling f be transformed to a caterpillar T? That is to say, there is T=LjLj−1⋯L1HR1R2⋯Ri under f. In other words, for a given tree H, can we find a caterpillar T such that H=Lj−1Lj−1−1⋯L1−1TR1−1R2−1⋯Ri−1, where Lj−1 and Ri−1 stand for the inverse transformations of Lj and Ri under f, respectively?Problem 2. Let ℱ be a set of all connected p,q-graphs with the vertex set v1,v2,…,vp in common. If there is a labelling f defined as fvi=i for 1≤i≤p such that each graph of F admits f being as a strongly c-elegant itself, we say f is a strongly c-elegant labelling of ℱ. For any G∈ℱ, whether is there another graph H∈ℱ such that G=H+uv−xy where uv∉EH, xy∈EH, and fu+fv=fx+fy?



---

*Source: 6301674-2022-03-28.xml*