Topological Graphic Passwords And Their Matchings Towards Cryptography
Bing Yao Hui Sun Xiaohui Zhang Yarong Mu Yirong Sun Hongyu Wang Jing Su Mingjun Zhang Sihua Yang Chao Yang





















































Topological Graphic Passwords And Their Matchings Towards Cryptography
    Bing  Yao^1,5, Hui Sun^1, Xiaohui Zhang^1, Yarong Mu^1, Yirong Sun^1
 Hongyu Wang^2,, Jing Su^2, Mingjun Zhang^3, Sihua Yang^3, Chao Yang^4
1 College of Mathematics and Statistics,
 Northwest Normal University, Lanzhou, 730070, CHINA
 2 School of Electronics Engineering and Computer Science, Peking University, Beijing, 100871, CHINA
3 School of Information Engineering, Lanzhou University of Finance and Economics, Lanzhou, 730030, CHINA
4 School of Mathematics, Physics & Statistics, Shanghai University of Engineering Science, Shanghai, 201620, CHINA
5 School of Electronics and Information Engineering, Lanzhou Jiaotong University, Lanzhou, 730070, CHINA

^ Hongyu Wang is the corresponding author with email: why1988jy@163.com




Manuscript received June 1, 2017; revised August 26, 2017.
Corresponding author: Bing Yao, email: yybb918@163.com.
    December 30, 2023
=======================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================






Graphical passwords (GPWs) are convenient for mobile equipments with touch screen. Topological graphic passwords (Topsnut-gpws) can be saved in computer by classical matrices and run quickly than the existing GPWs. We research Topsnut-gpws by the matching of view, since they have many advantages. We discuss: configuration matching partition, coloring/labelling matching partition, set matching partition, matching chain, etc. And, we introduce new graph labellings for enriching Topsnut-matchings and show that these labellings can be realized for trees or spanning trees of networks. In theoretical works we explore Graph Labelling Analysis, and show that every graph admits our extremal labellings and set-type labellings in graph theory. Many of the graph labellings mentioned are related with problems of set  matching partitions to number theory, and yield new objects and new problems to graph theory.


Keywords—Cryptography; graphical password; matching; partition; labelling.

















fancy
plain



§ INTRODUCTION


As known, public key and private key play important roles in cryptography nowadays. How to realize the authentication of public keys and private keys by ciphers with easy to use and high level security? Graphical passwords (GPWs) emerged for alternative to  text-based passwords. GPWs have been researched and applied in the real life for a long time, for example, QR code is popular in electronic commerce, open screen graphic cipher for smart mobiles, and so on (<cit.>). The existing GPWs are lack of pictures frequently changed and occupy huge spaces of computer, and need users to learn more and have good memory, and do not support more individual ideas and personal making GPWs.

For overcoming weak limits of the existing GPWs, Wang et al. (<cit.>) have designed Topological graphic passwords (Topsnut-gpws) by an idea of “topological structure pulsing number theory”. Clearly, Topsnut-gpw is a mathematical expression of  nature, and can be storage into computer by canonical matrices, and be operated quickly in computer. Topsnut-gpws have such advantages: (i) no general polynomial algorithms for finding topological structures and colorings/labellings in graph theory, which are two basic components for producing Topsnut-gpws; (ii) easily yield text-based passwords, and such procedure is irreversible; (iii) easily operating like gesture passwords used in mobiles with touch screen; (iv) allow personal knowledge into making Topsnut-gpws for long time remembering in mind; (v) huge spaces <cit.>, for instant, there are t_23≈ 2^179 and t_24≈ 2^197, where t_p is the number of graphs of p vertices, and over 200 existing labellings <cit.>, and so on. Thereby, Topsnut-gpws have provable security, computational security and unbreakable in nowadays' computer. We will study Topsnut-gpws by the matching of view in this article.





 §.§ Examples


Matching phenomena are popular and exist almost every where of the world, such as black and white, more and less, men and women, rich and poor, public and private, and even mathematics, also, is the matching of space structure and quantity. Matching is not a connection between two different things, but also connections of one-more things and more-more things. Matching is not a simple combination of two or more things, but a combination with restrictive conditions. Here, our matchings belong to  mathematics and cryptograph.

In cryptography we can consider that a public key and a private key form an authentication matching. Sometimes, people want one public key vs two or more private keys. In <cit.> and <cit.>, the authors have listed many advantages of Topsnut-gpws. One advantage of Topsnut-gpws is that Topsnut-gpws can produce easily text-based passwords with longer bytes as longer as desired. However, we cannot reconstruct the origin Topsnut-gpws from the text-based passwords made by them. This irreversibility also appears in Hash algorithm that is a one-way encryption system, that is, only encryption procedure, no decryption procedure.

We start our discussion with the following examples for showing Topsnut-gpws worked best in generating text-based passwords. In Fig.<ref>, we can see a Topsnut-gpw K_4 having: Any two small circles (called vertices hereafter) are connected by an edge. Furthermore, we identify the vertices of the Topsnut-gpws T_1,T_2,T_3 pictured in Fig.<ref> that have the same label into one vertex, the resulting graph is just K_4, so we write this fact as K_4=⊙⟨ T_i⟩^3_1 for briefness. A phenomenon is that any two caterpillars T_i and T_j have no the edge with the same label, we denote this phenomenon by E(T_i)∩ E(T_j)=∅. However, the Topsnut-gpws H_1,H_2,H_3 shown in Fig.<ref> have common edges with the same labels, we denote this fact as E(H_i)∩ E(H_j)≠∅; and identifying the vertices of these Topsnut-gpws H_1,H_2,H_3 results in K_4 by deleting multiple edges, we write this case as K_4=⊖(H_i)^3_1. We denote the number of vertices of T_i as |V(T_i)| for i=1,2,3, where V(G) is the set of vertices of a graph G. It is not hard to observe that |V(T_i)|≠ |V(T_j)| as i≠ j. But, |V(H_i)|=|V(H_j)| for i≠ j in Fig.<ref>, these H_1,H_2,H_3 are the spanning trees of K_4. Spanning trees, such as spanning algorithms, Spanning Tree Protocol (STP), minimum spanning trees and spanning tree searches, are useful in today's scientific areas, especially, network security.





We use three Topsnut-gpws T_1,T_2,T_3 shown in Fig.<ref> to generate three text-based passwords D(T_1)=112, D(T_2)=110022, D(T_3)=033312321 for the purpose of encrypting electronic files. Moreover, we produce a little bit of complex text-based passwords below:


D_123=D(T_1)+D(T_2)+D(T_3)=112110022033312321

D_321=D(T_3)+D(T_2)+D(T_1)=033312321110022112

D_132=D(T_1)+D(T_3)+D(T_2)=112033312321110022.


Clearly, D_123, D_321 and D_132 differ from to each other (notice that we have other three text-based passwords D_213, D_231 and D_312). In fact, we can construct more complex text-based passwords by

    D_T=∑ ^m_i=1D(T_j_i)

with 1≤ j_i≤ 3 and m≥ 2, such that D_T has longer bytes as we desired. Also, we can get text-based passwords D(H_i) from three Topsnut-gpws H_1,H_2,H_3 shown in Fig.<ref>, and moreover

    D_H=∑ ^m_i=1D(H_j_i)

with 1≤ j_i≤ 3 an m≥ 2.

The second example for showing an important property of Topsnut-gpws. In Fig.<ref>, we can walk along a path 1→ 10→ 21→ 6→ 13→ 2→ 9→ 14 to make two text-based passwords

    T'_vv=   1'1012141'10'1152110'21'681021'6'13
       17216'13'2613'2'913192'9'14'135914'

and

    T'_vev=   1'1110131215141'10'11131592110'21'567
       891021'6'19131175216'13'15219613'2'119
       151321192'9'2414189'14'1511731951914'

or eliminating “'” from T'_vv and T'_vev for complex reason yields

    T_vv=   1101214110115211021681021613
       172161326132913192914135914

and

    T_vev=   11110131215141101113159211021567
       89102161913117521613152196132119
       15132119292414189141511731951914




It is not easy to reconstruct ⊙_2 ⟨ T_1, T_2⟩ shown in Fig.<ref> by T_vv in (<ref>) or T_vev in (<ref>), thus large scale Topsnut-gpws are provable security, since reconstructing graph problems are related with some mathematical conjectures, such as Kelly-Ulam's Reconstruction Conjecture proposed in 1942. So we can claim that the procedure of getting text-based passwords from Topsnut-gpws is irreversible. On the other hand, large scale Topsnut-gpws made by various graph labellings are computational security, or computationally unbreakable, since no polynomial algorithm for finding all possible graph labellings for a given graph, also no polynomial algorithm for constructing all non-isomorphic graphs. We have no polynomial algorithm for listing all possible text-based passwords in a Topsnut-gpw, although it may be interesting and important.

We have to face the following problems:

[Prob-1.  ]

  * In general, for n≥ 4, how many ways are there to form a Topsnut-gpw K_n=⊙⟨ T_i⟩^m_1 with E(T_i)∩ E(T_j)=∅ as i≠ j, or K_n=⊖(H_i)^m_1 with V(K_n)=V(H_i) for i∈ [1,m] and |E(H_i)|=|E(H_j)|?

  * Are the text-based passwords D_T in (<ref>) and D_H in (<ref>), T_vv in (<ref>) and T_vev in (<ref>) computationally unbreakable?



0.4cm

Fig.<ref> tells us: Each Topsnut-gpw T_i (H_i) consists of one configuration T_i,1 (H_i,1) and one labelling T_i,2 (H_i,2). We need to know:
[- ]

  * How many configurations T_i or H_i are there for producing K_n with n≥ 4?

  * How many type of label-functions (also, called labellings hereafter) do T_i and H_i admit?

  * How to label the vertices or edges of T_i and H_i with the labellings admitted by T_i and H_i, such that identifying the vertices of T_i or H_i that have the same labels into one just results K_n=⊙⟨ T_i⟩^m_1 or K_n=⊖(H_i)^m_1?




A public key and a private key make an authentication true in network communication. Sometimes, an authentication needs one public key and two or more private keys, and vice versa. In other words, we can consider that “public key vs private key” forms some matching partition (authentication can be seen as a matching entirety that can be partitioned into several parts). Here, we will design matching type of Topsnut-gpws (Topsnut-matchings) for the requirement of protecting people's information and property in networks.

The topic of matching partition contains: configuration matching partition, coloring/labelling matching partition, set matching partition, matching chain, etc. In the number of matching partitions, we have one-vs-one, one-vs-more and more-vs-more styles of matching partitions. Each matching mentioned here will be obtained by one of configuration-vs-configuration, configuration-vs-labelling, labelling-vs-labelling, and (configuration, labelling)-vs-(configuration, labelling).




A Topsnut-gpw was made by a topological structure (also, configuration, called graph in graph theory, which is a branch of mathematics) with a label-function (also, called graph labelling, or labelling for short) on vertices, or edges, or vertices and edges (see Fig.<ref>). So, we are reasonable to consider any labeled graph of graph theory as a Topsnut-gpw here.  Notice that Topsnut-gpws can be defined by many labellings shown in <cit.>.



 §.§ Preliminary


Before exploring solutions of Prob-1 and Prob-2, we need terminology, notations and particular graphs (=configurations) in our discussion, standard notations and definitions of graph theory can be found in <cit.>. A (p,q)-graph G has p vertices and q edges. We will use a notation [a, b]={a, a+1,…, b}, where m, n are integers with 0≤ m<n, and employ another notation [α, β]^o={α, α+2, …, β} with odd integers α, β holding 1≤α<β true.

A tree is a graph in which any pair of two vertices x,y is connected by a unique path P(x,y)=xu_1u_2⋯ u_my; a leaf is a vertex of degree one; a caterpillar is a tree such that the deletion of all leaves of the tree results in a path; a lobster is a tree such that the deletion of all leaves of the tree produces just a caterpillar.



A labelling h of a graph G is a mapping h:S⊆ V(G)∪ E(G)→ [a,b] such that h(x)≠ h(y) for any pair of elements x,y of S, and write the label set h(S)={h(x): x∈ S}. A dual labelling h' of a labelling h is defined as: h'(z)=max h(S)+min h(S)-h(z) for z∈ S. Moreover, h(S) is called  vertex label set if S=V(G), h(S) edge label set if S=E(G), and h(S) a universal  label set if S=V(G)∪ E(G).





We, in the following discussion, need four pairs of graph operations on four basic elements of vertex, edge, path and cycle as follows: In Fig.<ref>, a vertex-split operation from (a) to (b); a vertex-identifying operation from (b) to (a); an edge-split operation from (c) to (d); and an edge-identifying operation from (d) to (c). Let N(x) be the set of all neighbors of a vertex x, very often, N(x)  is called a neighbor set. In Fig.<ref> (b) and (d), after a series of vertex/edge-split operations, we have to emphasize that the neighbor sets hold N(y')∩ N(y”)=∅, N(u')∩ N(u”)=∅, N(u')∩ N(v”)=∅, N(v')∩ N(u”)=∅ and N(v')∩ N(v”)=∅ true. The path/cycle-split operation and the path/cycle-identifying operation are shown in Fig.<ref>, also, it stresses that the neighbor sets N(u'_i)∩ N(u”_j)=∅ with i,j∈ [1,n].







§ MATCHING DIVERSITY




 §.§ Configuration matching partition


Let W be a universal graph admitting a labelling f. If W contains edge disjoint subgraph G_i admitting a labelling f_i induced by f with i∈ [1,m] such that V(W)=⋃^m_i=1 V(G_i) and E(W)=⋃^m_i=1 E(G_i) after identifying the vertices of G_1, G_2,… ,G_m having the same labels respectively (see an example K_4=⊙⟨ T_i⟩ ^3_1 shown in Fig.<ref>), we write this case as W=⊙⟨ G_i⟩ ^m_1, called an edge-disjoint matching partition. On the other hand, each G_i matches with the set Z_i={G_1, G_2,… ,G_m}∖{G_i} on the edge-disjoint matching partition W, then we denote simply W as ⊙⟨ G_i, Z_i⟩. Also, we allow the case V(G_i)=V(W) with i∈ [1,m] in an edge-disjoint matching partition W=⊙⟨ G_i⟩ ^m_1.

In encryption of networks, each G_i with i∈ [1,m] can be considered as a key, so W=⊙⟨ G_i⟩ ^m_1 is just an edge-disjoint authentication. Furthermore, if G_i is a public key, and the set Z_i is a group of private keys, and W=⊙⟨ G_i, Z_i⟩ is just a one-vs-more authentication.

Similarly, we have a multiple-edge matching partition W=⊖(H_i) ^m_1 as each subgraph H_i admitting a labelling f_i induced by f with i∈ [1,m] holds V(H_i)=V(W) and E(H_i)∩ E(G_j)≠∅ true for some i≠ j by identifying the vertices of ⋃ ^m_i=1V(H_i) having the same labels together and eliminating multiple edges. A mixed matching partition W=⋃^m_i=1G_i has some G_j holding V(G_j)≠ V(W) and E(G_s)∩ E(G_t)≠∅ true for some s≠ t.


Naturally, a labelling h and its dual labelling h' of a graph G are matching with each other, call (h,h') a labelling matching of G. Let G_1,G_2 be two copies of G, and let G_1 admit the labelling h, G_2 admit the dual labelling h' of h, so we have a graph ⊙⟨ G_1,G_2⟩ obtained by identifying those vertices of V(G_1)∪ V(G_2) having the same labels together.



As W=K_n, V(K_n)=V(G_i) with i=1,2 and E(G_1)∩ E(G_2)=∅ holding E(K_n)=E(G_1)∪ E(G_2) true, we say G_1 and G_2 matching to each other and G_1 and G_2 are complementary to each other, moreover K_n=⊙⟨ G_1,G_2⟩. Conversely, by doing a vertex-split operation to each vertex of K_n, so we split K_n into two subgraphs G_1 and G_2.




As W is an Euler graph, the edge-disjoint matching partition W=⊙⟨ G_i⟩ ^m_1 has its vertex degree deg_W(u)=∑ ^m_i=1deg_G_i(u) to be even for each vertex u∈ V(W). Here, W admits some v-set e-proper labelling (F,g) defined in Definition <ref>. For m=2,  G_1,G_2 are not Euler graphs, but ⊙⟨ G_1,G_2⟩ is an Euler graph, then we say both G_1,G_2 are Euler matching to each other.



As W is a complete graph K_n, we have the following longstanding conjectures in graph theory, which show that the edge-disjoint matching partition K_n=⊙⟨ G_i⟩ ^m_1 may be computationally unbreakable:

(i) Anton Kotzig (1964) proposed the Perfect 1-Factorization Conjecture: For any n ≥ 2,
K_2n can be decomposed into 2n-1 perfect matchings such that the union of any two matchings
forms a hamiltonian cycle of K_2n.

(ii) If each tree admits a graceful labelling, then this
will settle down a well-known Ringel-Kotzig Decomposition Conjecture (Gerhard Ringel and Anton Kotzig, 1963; Alexander Rosa, 1967): A complete graph K_2n+1 can be decomposed into 2n + 1 edge-disjoint subgraphs that are all isomorphic to any given tree having n edges.

(iii) K-T conjecture (Gyárás and Lehel, 1978; Béla Bollobás, 1995): For integer
n ≥ 3, given n disjoint trees T_k having k vertices with respect to k∈ [1,n]. Then the complete graph
K_n can be decomposed into the union of n edge-disjoint trees H_k, such that T_k≅ H_k with k∈ [1,n]. Very often, we write this case as ⟨ T_1, T_2, …, T_m | K_n⟩.

Thereby, the above three conjectures can help us to design more complex Topsnut-gpws to be computationally unbreakable.






 §.§ Coloring/labelling matchings


Graph coloring/labellings are powerful and essential for designing Topsnut-gpws, let us see an example as follows:




As W is a maximal planar graph, each G_i with i∈ [1,m] is a semi-maximal planar graph (<cit.>) having a common even-cycle C, such that E(G_i)∩ E(G_j)=E(C) for i≠ j. If each G_i is 4-colorable such that the even-cycle C is colored with 1,2 only, then we do a series of cycle-identifying operations on m common even-cycles in G_1,G_2,… ,G_m in to one. The resulting Topsnut-gpw, like a “book”, is denoted as W=⊖_C(G_i) ^m_1, and G_i∪ G_j for i≠ j is a maximal planar graph, we say W=⊖_C(G_i) ^m_1 to be a maximal planar C-matching partition. Each Topsnut-gpw G_i is as a “page” of the “book” W, and the common even-cycle C is as the “bone” of the “book” W. This “book” can be considered as an authentication too.  It is not hard to see that there are two or more (infinite) “books” W=⊖_C(G_i) ^m_1.

Conversely, select a cycle L of a maximal planar graph G, and do an edge-split operation to each edge of the cycle L, so we split G into two semi-maximal planar graphs G^L and G^L, and call G^L and G^L to be matching to each other (see Fig.<ref>). So, G=⊖_L⟨ G^L, G^L⟩. Determining particular semi-maximal planar matchings (G^L,G^L) can provide more complex models for authentication of public keys and private keys, such as both graphs G^L-V(L) and G^L-V(L) are trees.








(<cit.>) Suppose that a bipartite (p,q)-graph G with partition (X,Y)  admits a vertex labelling f:V(G) → [0,2q-1], such that every edge uv is labeled as f(uv)=|f(u)-f(v)| holding f(E(G))=[1, 2q-1]^o true, we call f an odd-graceful labelling of G (called an odd-graceful graph). Furthermore, if G holds max{f(x): x∈ X}< min{f(y): y∈ Y} (f_max(X)<f_min(Y) for short) true, then f is called a set-ordered odd-graceful labelling.



In <cit.>, we have expanded the odd-graceful labelling as: Let G be a (p,q)-graph, we have:

(i) If G admits a vertex labelling f:V(G) → [0,2q] (it is allowed f(E(G))⊂ [1,2q]), such that every edge uv is labeled as f(uv)=|f(u)-f(v)| or f(uv)=2q-1-|f(u)-f(v)| and f(E(G))=[1, 2q-1]^o, then we call f a pan-odd-graceful labelling.

(ii) A k-matching odd-graceful labelling g of an odd-graceful labelling f of a (p,q)-Topsnut-gpw G is a vertex labelling defined on another graph H admitting g:V(H) → [0,2q-1], every edge uv∈ E(H) has its label g(uv)=|g(u)-g(v)| holding g(E(H))=[1, 2q-1]^o true, such that f(V(G))∪ g(V(H))=[0,2q], or [0,2q-1] and |f(V(G))∩ g(V(H))|=k. We call H with a k-matching odd-graceful labelling as an odd-graceful Topsnut-matching of G, denoted as ⊙⟨ G,H ⟩. (see  Fig. <ref> and Fig.<ref>)

(iii) A k-sequential odd-graceful labelling h: V(G)→ [k,2q-1+k] such that the induced edge labelling h(uv)=|h(u)-h(v)| for uv ∈ E(G) holding g(E(G))=[1,2q-1]^o true.




<cit.> A (p,q)-graph G admits a labelling f:V(G)
→ [0,2q-1] such that each edge uv∈ E(G) is labeled as f(uv)=f(u)+f(v) ( 2q). If the set f(E(G)) of all edge labels is equal to [1, 2q-1]^o, we call f an odd-elegant labelling of G (called an odd-elegant graph).

Finding all odd-graceful (odd-elegant) labellings of a Topsnut-gpw G admitting an odd-graceful (odd-elegant) labelling seems to be very difficult, and no way is for determining conditions for graphs admitting set-ordered odd-graceful (odd-elegant) labellings up to now. In Fig.<ref>, we have six odd-graceful Topsnut-matchings G_i=⊙_0⟨ G,H_i ⟩ with i∈ [1,6], since G admits an odd-graceful labelling. Here, V(G_i)=V(G)∪ V(H_i) and E(G_i)=E(G)∪ E(H_i) with i∈ [1,6]. Here, we present an algorithm for finding  odd-graceful Topsnut-matchings.

0.4cm

ODD-GRACEFUL-GRAPH Algorithm:

Input: A connected (p,q)-graph G admitting an odd-graceful labelling f.

Output: A connected odd-graceful Topsnut-matching H admitting an odd-graceful labelling.

Step 1. Build up an integer set R(f,G)=[0,2q-1]∖ f(V(G)) (or R'(f,G)=[0,2q]∖ f(V(G))), and make a candidate edge set C_0={x^ox^e:x^o,x^e∈ R(f,G), x^o is odd, x^e is even}, and a graph H_0 is constructed by identifying the ends of edges of C_0 into one vertex, these ends  have the same labels.

Step 2. If the graph H_k contains no two edges x^o_ix^e_i and x^o_jx^e_j holding |x^o_i-x^e_i|=|x^o_j-x^e_j| true, go to Step 4; otherwise,  go to Step 3.

Step 3. Do H_k+1:=x^o_ix^e_i+H_k-E(k+1) with E(k+1)={x^o_jx^e_j: |x^o_j-x^e_j|=k+1}⊂ C_0 and x^o_ix^e_i with |x^o_i-x^e_i|=k+1, such that H_k+1 is connected,  go to Step 2.

Step 4. Return a connected Topsnut-matching H admitting an odd-graceful labelling.


0.4cm








Let H be an (a pan-)odd-graceful graph with vertices v_1,v_2,…, v_p. If each vertex v_i matches with an (a pan-)odd-graceful graph T_i with i∈ [1,p] such that there exists an odd-graceful Topsnut-matching ⊙_1⟨ H,T_i⟩ ^p_1 obtained by identifying the vertex v_i with some vertex of T_i into one, these two vertices have been labeled with the same labels. We say ⊙_1⟨ H,T_i⟩ ^p_1 a  (pan-)odd-graceful Topsnut-matching team (see an example shown in  Fig.<ref>). Moreover, ⊙_1⟨ H,T_i⟩ ^p_1 is called a uniformly (pan-)odd-gracefully Topsnut-matching team if T_i≅ T_j for i≠ j.




 
Each caterpillar H of p vertices has an (a pan-)odd-graceful Topsnut-matching team ⊙_1⟨ H,T_i⟩ ^p_1.

 There is  a path P=u_1u_2⋯ u_n in a caterpillar H, such that each u_i has its own leaf set L(u_i)={v_i,j:j∈ [1,m_i]} with m_i≥ 0 and i∈ [1,n]. And

    V(H)=V(P)∪ L(u_1)∪ L(u_2)∪⋯∪ L(u_n),
 see a caterpillar shown in Fig.<ref>.

We define an odd-graceful labelling h of H by setting

h(u_1)=0, h(v_2,j)=h(u_1)+2j with j∈ [1,m_2];

h(u_3)=h(v_2,m_2)+2=2(m_2+1),

h(v_4,j)=h(u_3)+2j=2(m_2+1+j) with j∈ [1,m_4];

h(u_5)=h(v_4,m_4)+2=2(m_2+m_4+1)+2=2(m_2+m_4+2),

h(v_6,j)=h(u_5)+2j=2(m_2+m_4+2+j) with j∈ [1,m_6].

For i≥ 2, we let

    h(u_2i-1)=h(v_2i-2,m_2i-2)+2=2 (i-1+∑^i-1_k=1m_2k )

and for j∈ [1,m_2i],

    h(v_2i,j)=h(u_2i-1)+2j=2 (i-1+j+∑^i-1_k=1m_2k ).


Clearly, h(v_2i-2,m_2i-2)<h(u_2i-1) and h(v_2i,j)<h(v_2i,j+1) with j∈ [1,m_2i-1] and i≥ 2.

Case 1.  n is even.

We set h(u_n)=h(v_n,m_n)+1, an odd integer, and h(v_n-1,j)=h(u_n)+2j  with j∈ [1,m_n-1]. Notice that h(u_n)-h(v_n,m_n)=1. Furthermore, we have h(u_n-2)=h(v_n-1,m_n-1)+2, and h(v_n-3,j)=h(u_n-2)+2j  with j∈ [1,m_n-3].

For i≥ 1, h(u_n-2i)=h(v_n-2i+1,m_n-2i+1)+2, and h(v_n-2i-1,j)=h(u_n-2i)+2j  with j∈ [1,m_n-2i-1]. As  2i=n-2, h(u_2)=h(v_3,m_3)+2, and h(v_1,j)=h(u_2)+2j  with j∈ [1,m_1].

Case 2.  n is odd.

We set h(u_n)=h(v_n-1,m_n-1)+2 to be an even integer, so we label h(v_n,j)=h(u_n)+j  with j∈ [1,m_n], such that each h(v_n,j) is  an odd integer. Then,  h(v_n,1)-h(u_n)=1. Next, let h(u_n-1)=h(v_n,m_n)+2, and h(v_n-2,j)=h(u_n-1)+2j  with j∈ [1,m_n-2]. In general, we have h(u_n-2i+1)=h(v_n-2i+2,m_n-2i+2)+2, and h(v_n-2i,j)=h(u_n-2i+1)+2j  with j∈ [1,m_n-2i] for i≥ 1. As 2i=n-1, h(u_2)=h(v_1,m_n-2i-2)+2, and h(v_1,j)=h(u_2)+2j  with j∈ [1,m_1].

Notice that h(v_1,m_1)=2p-3 and h(v_1,m_1-1)=2p-5. So, we can use the induction to show h is a set-ordered   odd-graceful labelling of the  caterpillar T.


Now, we write a copy of the caterpillar T with an odd-graceful labelling h by H and define a set-ordered pan-odd-graceful labelling h^* of  H as:  h^*(x)=h(x)+1 for each x∈ V(T)=V(H). Clearly,

    h^*(V(H))∪ h(V(T))=[0,2(P-1)]

and h^*(V(H))∪ h(V(T))=∅. Now, we make another caterpillar T-v_n,1 with a labelling f defined by f(y)=h(y) for y∈ V(T)∖{v_n,1}. So, f(E(T-v_n,1))=[3,2p-3]^o. We add a new vertex w_i to T-v_n,1, and join w_i with some vertex w'_i of T-v_n,1 by an edge w_iw'_i, the resulting tree is denoted as T_i=T-v_n,1+w_iw'_i, and define a labelling f_i of T_i as f_i(x)=f(x) for x∈ V(T_i)∖{w_i}, and f_i(w_i)∈ h^*(V(H)) such that |f_i(w_i)-f_i(w'_i)|=1, which means f_i(V(T_i))=[1,2p-3]^o. Thereby, 
    |f_i(V(T_i))∩ h^*(V(H))|=1
 and the graph ⊙_1⟨ H,T_i⟩ is a pan-odd-graceful Topsnut-matching, and so we can claim that ⊙_1⟨ H,T_i⟩^p_1 is an (a pan-)odd-graceful Topsnut-matching team. The proof of this theorem is complete.




In the proof of Theorem  <ref>, we can see

    H-v_n,1≅ T-v_n,1≅ T_i-w_i
 with i∈ [1,p], so ⊙_1⟨ H,T_i⟩^p_1 is approximately a uniformly (pan-)odd-gracefully Topsnut-matching team. Thereby, we can get a result: “If a tree T of p vertices admits an odd-graceful labelling f such that f(uv)=1 for an edge uv ∈ E(T), where v is a leaf of T, that is, deg_T(v)=1. Then we have an (a pan-)odd-graceful Topsnut-matching team ⊙_1⟨ H,T_i⟩^p_1, where T_i is obtained by deleting the leaf v of T and add a new vertex w to the remainder T-v, and join w with some vertex of T-v; H is a copy of T and admits a pan-odd-graceful labelling g defined by g(x)=f(x)+1 for x∈ V(T)=V(H).”



For designing complex Topsnut-gpws, Wang et al. (<cit.>) have defined firstly the twin-type of labellings by means of the matching of view (also, key-vs-lock).


<cit.> For two connected (p_i,q)-graphs G_i with i=1,2, and p=p_1+p_2-2, if a (p,q)-graph G=⊙⟨ G_1, G_2⟩ admits a vertex labelling f: V(G)→ [0, q] such that

(i) f is just an odd-graceful labelling of of G_1;

(ii) f(E(G_2))={f(uv)=|f(u)-f(v)|: uv∈ E(G_2)}=[1, q-1]^o;

(iii) |f(V(G_1))∩ f(V(G_2))|=k and f(V(G_1))∪ f(V(G_2))⊆ [0, q-1].

Then f is called a twin odd-graceful labelling (Tog-labelling) of G, and G a Tog-matching partition.






<cit.> For two connected (p_i,q)-graphs G_i with i=1,2, and p=p_1+p_2-2, if a (p,q)-graph G=⊙⟨ G_1, G_2⟩ admits a vertex labelling f: V(G)→ [0, q-1] such that

(i) f is just an odd-elegant labelling of G_i with i=1,2;

(ii) |f(V(G_1))∩ f(V(G_2))|=k and f(V(G_1))∪ f(V(G_2))⊆ [0, q-1].

Then f is called a twin odd-elegant labelling (Toe-labelling) of G (called a Toe-graph), and ⊙⟨ G_1, G_2⟩ is called a Toe-matching partition, where G_1 is the Toe-source and G_2 is a Toe-association.

Fig.<ref> shows an example for understanding Definition <ref>. If each G_i with i=1,2 is a connected graph in Definition <ref>, and G_1 is a bipartite connected graph with bipartition (X_1,Y_1) holding f_max(X_1)<f_min(Y_1) true, then f is called a set-ordered twin odd-elegant labelling (Sotoe-labelling) of G (called a Sotoe-graph). Wang et al. have shown the algorithms for producing Toe-graphs G=⊙⟨ G_1, G_2⟩, such as

 
<cit.> Every non-star tree T admitting a set-ordered odd-elegant labelling matches with at least two trees T_1,T_2 such that each ⊙_2 ⟨ T, T_i⟩ with i=1,2 admits a set-ordered twin odd-elegant labelling.


Wang et al. have constructed large scale of Toe-graphs ⊙_2 ⟨ H_1, H_2⟩ by smaller Toe-graphs ⊙_2 ⟨ T_i, T'_i⟩ with i∈ [1,m] for exploring Topsnut-chains. Moreover, they have mixed odd-graceful labelling with odd-elegant labelling together in Definition <ref> below.


<cit.> For two connected (p_i,q)-graphs G_i with i=1,2, and p=p_1+p_2-2, if a (p,q)-graph G=⊙⟨ G_1, G_2⟩ admits a vertex labelling f: V(G)→ [0, q] such that

(i) f is an odd-graceful labelling of G_1;

(ii) f:V(G_2)→ [0,2|E(G_2)|] holding

    f(E(G_2))   ={f(uv)=f(u)+f(v) ( 2|E(G_2)|):
            uv∈ E(G_2)}
       =[1, 2|E(G_2)|-1]^o
 true.

Then f is called a 2-odd graceful-elegant labelling (a 2odd2-labelling) of G (called a 2odd2-graph), and ⊙⟨ G_1, G_2⟩ is called a 2odd2-matching partition.

In Definition <ref>, if f is a set-ordered odd-graceful labelling of G_1, and G_2 has its bipartition (X, Y) holding f_max(X)<f_min(Y) true, then we call f a set-ordered 2odd2-labelling of G. The results on the 2odd2-matching partition can be found in <cit.>. The authors of two articles <cit.> and <cit.>  propose several conjectures on the twin type of odd-graceful/odd-elegant labellings which mean that Topsnut-gpws made by such labellings are computational security (<cit.>).











 §.§ Matching partitions based on set-type of labellings



We use a notation S^2 to denote the set of all subsets of a set S. For instance, S={a,b,c}, so S^2 has its own elements: {a}, {b}, {c}, {a,b}, {a,c}, {b,c} and {a,b,c}. It is clear that ∅∉S^2 in the paper.


^* Let G be a (p,q)-graph G, and [0,M]^2 be a set of all subsets of [0,M] with M≥ p+q, and [a,b] be an integer set. We have:

(i) A set mapping F: V(G)∪ E(G)→ [0, M]^2 is called a total set-labelling of G if F(x)≠ F(y) for distinct elements x,y∈ V(G)∪ E(G).

(ii) A vertex set mapping F: V(G) → [0, M]^2 is called a vertex set-labelling of G if F(x)≠ F(y) for distinct vertices x,y∈ V(G).

(iii) An edge set mapping F: E(G) → [0, M]^2 is called an edge set-labelling of G if F(uv)≠ F(xy) for distinct edges uv, xy∈ E(G).

(iv) A vertex set mapping F: V(G) → [0, M]^2 and a proper edge mapping g: E(G) → [a, b] are called a v-set e-proper labelling (F,g) of G if F(x)≠ F(y) for distinct vertices x,y∈ V(G) and two edge labels g(uv)≠ g(wz) for distinct edges uv, wz∈ E(G).

(v) An edge set mapping F: E(G) → [0, M]^2 and a proper vertex mapping f: V(G) → [a,b] are called an e-set v-proper labelling (F,f) of G if F(uv)≠ F(wz) for distinct edges uv, wz∈ E(G) and two vertex labels f(x)≠ f(y) for distinct vertices x,y∈ V(G).





Fig.<ref>(a) shows a (6,8)-graph G admitting a v-set e-proper graceful labelling (F,g) defined by F:V(G)→ [0,8]^2 and g(E(G))=[1,8]. And Fig.<ref>(b) shows a (6,8)-graph H admitting a v-set e-proper odd-graceful labelling (F,f) defined by F:V(H)→ [0,15]^2 and f(E(H)) =[1,15]^o.








A tree T shown in Fig.<ref> admits an e-set v-proper labelling (F,f) defined by f:V(T)→ [0,11], and let “∙”=“null”, each edge of T has its own label set as follows:

F(ay)={∙,1,5,11,21,22}, F(cy)={∙,2,6,10,19,21},

F(dy)={∙,3,7,9,17,20}, F(de)={∙,6,10,11,17},

F(dr)={∙,4,8,15,19}, F(ds)={∙,5,7,9,13,18},

F(dt)={∙,2,3,5,9,14}, F(ew)={∙,0,5,7,9,16},

F(xw)={∙,1,4,7,8,15}, F(ut)={∙,1,4,11,12},

F(uv)={∙,2,3,10,13}.

Thereby, this Topsnut-gpw T can produce more complex text-based passwords.



If a connected graph T admits mutually distinct graceful labellings f_1,f_2, …, f_m and odd-graceful labellings g_1,g_2, …, g_n with m,n≥ 1, then T admits a total set-labelling.


There are many trees support Theorem <ref>, such as caterpillars, and so do trees admitting set-ordered graceful labellings.


If a tree T admits a set-ordered graceful labelling, then T admits an e-set v-proper labelling (F,f) such that max{|F(uv)|:uv∈ E(T)}≥ 5.

 Let a tree T of p vertices has its own vertex bipartition (X,Y) with X={x_i:i∈ [1,s]} and Y={y_j:j∈ [1,t]} holding s+t=|V(T)|=p true. By the hypothesis of this theorem, T admits a set-ordered graceful labelling f defined by f(x_i)=i-1 for i∈ [1,s], f(y_j)=s+j-1 for j∈ [1,t] and f(x_iy_j)=f(y_j)-f(x_i)=s+j-i for each edge x_iy_j∈ E(T). We define another labelling f^* as: f^*(x_i)=f(x_i) for i∈ [1,s], f^*(y_j)=f(y_t-j+1) for j∈ [1,t] and f^*(x_iy_j)=f(x_iy_j) for each edge x_iy_j∈ E(T).

We define the following labellings:

[(L-1) ]

  *  h_1(w)=f^*(w) for w∈ V(T), h_1(x_iy_j)=null for each edge x_iy_j∈ E(T).

  *  We construct a labelling h_2 by setting h_2(w)=f^*(w) for w∈ V(T), and h_2(x_iy_j)=f^*(x_iy_j) for each edge x_iy_j∈ E(T). We verify

    h_2(x_i)+h_2(x_iy_j)+h_2(y_j)
       =f^*(x_i)+f^*(x_iy_j)+f^*(y_j)
       =f(x_i)+f(x_iy_j)+f(y_t-j+1)
       =i-1+(s+j-i+1)+s+(t-j+1)-1
       =2s+t
       =p+s.

Thereby, h_2 is really a pan-edge-magic total labelling of T.



  *  Suppose that h_3(w)=f^*(w) for w∈ V(T), h_3(x_iy_j)=p-1+f^*(x_iy_j) for each edge x_iy_j∈ E(T). Hence, h_3 is another pan-edge-magic total labelling of T.


  *  Define a labelling h_4 by setting h_4(w)=f^*(w) for w∈ V(T) and h_4(x_iy_j)=h_4(x_i)+h_4(y_j) ( p-1) for each edge x_iy_j∈ E(T). We compute

    h_4(x_iy_j)   =h_4(x_i)+h_4(y_j)
       =f^*(x_i)+f^*(y_j)
       =f(x_i)+f(y_t-j+1)
       =f(y_t-j+1)+f(y_j)-[f(y_j)-f(x_i)]
       =s+(t-j+1)+s+j-f(x_iy_j)
       =p+s-f(x_iy_j),

which distributes a set
 {p+s-1,p+s-2,… ,p,p-1,p-2,… ,s+1} ( p-1)={s,s-1,… ,1,0,p-2,… ,s+1}=[0,p-2]. So we claim that h_4 is a felicitous labelling of T.


  *  We define a labelling h_5 as: h_5(w)=f^*(w) for w∈ V(T) and h_5(x_iy_j)=p-f^*(x_iy_j)=p-f(x_iy_j) for each edge x_iy_j∈ E(T). Because


    |h_5(x_i)+h_5(y_j)-h_5(x_iy_j)|
       =|f^*(x_i)+f^*(y_j)+f^*(x_iy_j)-p|
       =|f(x_i)+f(y_t-j+1)+f(x_iy_j)-p|
       =|i-1+s+(t-j+1)-1+s+j-i+1-p|
       =s-1,


then we claim that h_5 is an edge-magic graceful labelling of T according to  Definition <ref>.

  *  Let h_6 be defined by h_6(w)=f^*(w) for w∈ V(T) and h_6(x_iy_j)=2f^*(x_iy_j)-1=2f(x_iy_j)-1 for each edge x_iy_j∈ E(T). We get


    h_6(x_i)+h_6(x_iy_j)+h_6(y_j)
       =f(x_i)+f(y_t-j+1)+2f(x_iy_j)-1
       =f(x_i)+f(y_t-j+1)+2[f(y_j)-f(x_i)]-1
       =i-1+s+(t-j+1)-1+s+j-i+f(x_iy_j)-1
       =p+s-2+f(x_iy_j),

which induces a set {p+s-1,p+s+1,…, 2p+s-3}=[p+s,2p+s-3].


We can see relationships between the above labellings: h_2(x_iy_j)+p-1=h_3(x_iy_j), 
    h_2(x_iy_j)+h_4(x_iy_j)   =f(x_iy_j)+p+s-f(x_iy_j)
       ≡ s-1  ( p-1)

and

    h_2(x_iy_j)+h_5(x_iy_j)=f(x_iy_j)+p-f(x_iy_j)=p.


Now, we define the desired e-set v-proper labelling F in the way: F(x_iy_j)={h_k(x_iy_j): k∈ [1,6]} for each edge x_iy_j∈ E(T), so T admits an e-set v-proper labelling (F,f^*) with max{|F(uv)|:uv∈ E(T)}≥ 6. This theorem is covered.





^* If a (p,q)-graph G admits an e-set v-proper labelling (F,f) by f: V(G)→ [0, a(p,q)] and F: E(G)→ [0, b(p,q)]^2, where a(p,q) and b(p,q) are linear functions of p and q, such that G can be decomposed into spanning trees T_1,T_2,… ,T_m with m≥ 2 and E(G)=⋃^m_i=1E(T_i) (allow E(T_i)∩ E(T_j)≠∅ for some i≠ j), and each spanning tree T_i admits a proper labelling f_i induced by (F,f). We call G a multiple-tree matching partition, denoted as G=⊕_F⟨ T_i⟩ ^m_1.






A multiple-tree matching partition G shown in Fig.<ref> has two spanning trees T_1,T_2 and an e-set v-proper labelling F, such that T_1 admits a set-ordered graceful labelling f_1 induced by F, and T_2 admits a super pan-edge-magic total labelling f_2 induced by F. In detail, f_1(u)∈ f(V(G)) for x∈ V(T_1)=V(G), each edge uv∈ E(T_1) is labeled as f_1(uv)=|f_1(u)-f_1(v)|∈ F(uv); and f_2(u)∈ f(V(G)) for y∈ V(T_2)=V(G), f_2(uv)∈ F(uv) for each edge uv∈ E(T_2), such that f_2(u)+f_2(uv)+f_2(v)=28 for uv∈ E(T_2). We can see T_0=T_1∩ T_2, called the common body of G, each edge of T_0 is labeled with a set.


Similarly with Definition <ref>, we propose:

^* If a (p,q)-graph G admits a vertex labelling f: V(G)→ [0, p-1], such that G can be decomposed into (spanning) graphs G_1,G_2,… ,G_m with m≥ 2 and E(G)=⋃^m_i=1E(G_i) and E(G_i)∩ E(G_j)=∅ for  i≠ j, and each graph G_i admits a proper labelling f_i induced by f. We call G a multiple-graph matching partition, denoted as G=⊙_f⟨ G_i⟩ ^m_1.

In Fig.<ref>, we can see that E(G_i)∩ E(G_j)=∅ for  i≠ j, and G_1 admits a graceful labelling f_1 induced by f, each G_j admits a felicitous labelling f_j induced by f with j∈ [2,4]. H_j=⊙ _k_j⟨ G_1,G_j⟩, with j∈ [2,4], admits the labelling f such that f(E(G_1))={|f(u)-f(v)|: uv∈ E(G_1)}=[1,11], f(E(G_j))={f(x)+f(y) ( 11): xy∈ E(G_j)}=[1,11] (where we set 0≡ 11 ( 11)), so each H_j=⊙ _k_j⟨ G_1,G_j⟩ with j∈ [2,4] is called a graceful-felicitous matching partition.





If a tree T admits a set-ordered graceful labelling, then T matches with a multiple-tree matching partition ⊕_F⟨ T_i⟩ ^m_1 with m≥ 10.

 Let (X,Y) be the bipartition of vertex set of the tree T admitting a set-ordered graceful labelling f, where X={x_i:i∈ [1,s]} and Y={y_j:j∈ [1,t]} with s+t=|V(T)|=p. By the definition of a set-ordered graceful labelling, we have f(x_i)=i-1 for i∈ [1,s], f(y_j)=s+j-1 for j∈ [1,t] and f(x_iy_j)=f(y_j)-f(x_i)=s+j-i for each edge x_iy_j∈ E(T). Now, let T=T_1 and f=f_1 for the purpose of statement. Clearly, max f_1(X)<min f_1(Y).



We construct the following trees.

[(Equ-1) ]

  *  The tree T_2 is isomorphic to T, and admits an edge-magic total labelling f_2 defined as: f_2(x_i)=f(x_i)+1 for i∈ [1,s], f_2(y_j)=f(y_t-j+1)+1 for j∈ [1,t], and f_2(x_iy_j)=f(x_iy_j)+p for each edge x_iy_j∈ E(T). Notice that f_2(V(T_2))=[1,p]. Furthermore,

    f_2(x_i)+f_2(x_iy_j)+f_2(y_j)
       =f(x_i)+f(x_iy_j)+p+f(y_t-j+1)
       =s+2p+1.

So, f_2 is a super edge-magic total labelling with
the magic constant s+2p+1 and max f_2(X)<min f_2(Y).


  *  We take a copy of T, denoted as T_3, and define an edge-magic total labelling f_3 of T_3 in the way: f_3(x_i)=f(x_s-i+1)+1 for i∈ [1,s], f_3(y_j)=f(y_j)+1 for j∈ [1,t], and f_2(x_iy_j)=f(x_iy_j)+p for each edge x_iy_j∈ E(T). So f_3(V(T_3))=[1,p]. By the same way used in Equ-<ref>, f_3 is a super edge-magic total labelling with
the magic constant t+2p+1 and max f_3(X)<min f_3(Y).


  *  Let T_4 be a tree being isomorphic to T. And T_4 admits a super felicitous
labelling f_4 made by: f_4(x_i)=f(x_i) for i∈ [1,s], f_4(y_j)=f(y_t-j+1) for
j∈ [1,t]. Moreover, we have

    f_4(x_i)+f_4(y_j)   =f(x_i)+f(y_t-j+1)
       =f(x_i)+s+p-1-f(y_j)
       =s+p-1- [f(y_j)-f(x_i) ]
       =s+p-1-f(x_iy_j),

The above form (<ref>) induces two sets 

    S_1=   {s+p-1-1,s+p-1-2,…
    ,
       s+p-1-(s-1),s+p-1-s}
 and S_2={p-2,p-3,… ,s}. Under modulo
(p-1), S_1≡ [0,s-1]. Thereby,
f_4(E(T_4))=[0,p-2]. We claim that f_4 is a super felicitous
labelling of T_4 with max f_4(X)<min f_4(Y).


  *  T_5 is isomorphic to T, and admits a super felicitous
labelling f_5 with max f_5(X)<min f_5(Y). made by: f_5(x_i)=f(x_s-i+1) for i∈ [1,s], f_5(y_j)=f(y_j) for
j∈ [1,t]. The remainder proof is as the same as that in Equ-<ref>.


  *  Let T_6≅ T. We define a labelling f_6 of T_6 in the way:
f_6(x_i)=f(x_i)+1 for i∈ [1,s], f_6(y_j)=f(y_t-j+1)+1=s+p-f(y_j) for j∈ [1,t], and
f_6(x_iy_j)=2p-f(x_iy_j) for each edge x_iy_j∈ E(T_6). It is not hard to see f_6(V(T_6))=[1,p]. We have

    f_6(x_i)+f_6(x_iy_j)+f_6(y_j)=s+3p+1-2f(x_iy_j)
 which produces a
set {p+s+3,p+s+3+2,p+s+3+4, … ,p+s+3+2(p-2)}. We can confirm that f_6
is a super edge antimagic total labelling with max f_6(X)<min f_6(Y).


  *  Take a tree T_7≅ T, and define a super edge antimagic total labelling f_7 of T_7 with max f_7(X)<min f_7(Y) as follows: f_7(x_i)=f(x_s-i+1)+1 for i∈ [1,s], f_7(y_j)=f(y_j)+1=s+p-f(y_j) for j∈ [1,t], and f_7(x_iy_j)=2p-f(x_iy_j) for each edge x_iy_j∈ E(T_7). The remainder proof is very similar to that in Equ-<ref>.


  *  Suppose that T_8 is a copy of T, we define a labelling f_8 of T_8 in the way that
f_8(x_i)=f(x_i) for i∈ [1,s], f_8(y_j)=f(y_t-j+1) for
j∈ [1,t-1], and f_8(y_t)=0. For each edge x_ky_t∈ E(T_8), we have

    f_8(x_k)+f_8(y_t)=f_8(x_k)+0
       =f_8(x_k)+(p-1) ( p-1)
       =f(x_k)+f(y_t) ( p-1)
       =f(x_k)+s+p-1-f(y_1) ( p-1)
       =s+p-1- [f(y_1)-f(x_k) ] ( p-1)
       =s-f(x_ky_1).
 Under modulo (p-1),

    f_8(E(T_8))={f_8(x_iy_j)
       =f_8(x_i)+f_8(y_j)  ( p-1): x_iy_j∈
    E(T_8)}
       =[0,p-2].
 Therefore, f_8 is a harmonious labelling of T_8 with max f_8(X)<min f_8(Y).


  *  Let T_9≅ T. We define a harmonious labelling f_9 of T_9 with max f_9(X)<min f_9(Y) as follows: f_9(x_i)=f(x_s-i+1) for i∈ [1,s], f_9(y_j)=f(y_j) for j∈ [1,t-1], and f_9(y_t)=0. By the same way used in Equ-<ref>, we can show f_9 is a harmonious labelling of T_9 and max f_9(X)<min f_9(Y).


  *  By Definition <ref> we define a Dgemm-labelling f_10 of T_10 that holds T_10≅ T true as following: f_10(x_i)=f(x_i) for i∈ [1,s], f_10(y_j)=f(y_j) for j∈ [1,t], and f_10(x_iy_j)=p-f(x_iy_j) for each edge x_iy_j∈ E(T_10). We verify:

  (i) Each edge x_iy_j corresponds an edge x'_iy'_j such that

    f_10(x_iy_j)   =p-f(x_iy_j)=p-|f(x_i)-f(y_j)|
       =|f(x'_i)-f(y'_j)|.


  (ii) For each edge x_iy_j∈ E(T_10),  T_10 has p-1 edges, and

    s(x_iy_j)   =|f_10(x_i)-f_10(y_j)|-f_10(x_iy_j)
       =|f(x_i)-f(y_j)|-p+f(x_iy_j)
       =2f(x_iy_j)-p
 distributes a set {2-p,4-p,…, 0, 2,4, …, p-2} when p is even. Clearly, each edge x_iy_j matches with another edge x'_iy'_j∈ E(T_10) holding s(x_iy_j)+s(x'_iy'_j)=0 true. If p is odd, s(x_iy_j) induces another set {2-p,4-p,…, -1, 1,3, …, p-2}, so s(x_iy_j)+s(x'_iy'_j)=0 is true.

  (iii) For each edge x_iy_j∈ E(T_10), we have

    f_10(x_iy_j)+|f_10(x_i)-f_10(y_j)|
       =p-f(x_iy_j)+|f_10(x_i)-f_10(y_j)|
       =p.


  (iv) Since f(V(T))=[0,p-1] and f(E(T))=[1,p-1], thus, f(E(T))=[1,p-1]=f(V(T))∖{0}, we have f(x_iy_j)=f(w) for each edge x_iy_j matching with a vertex w, which implies

    f_10(x_iy_j)+f_10(w)=p-f(x_iy_j)+f(w)=p;
 conversely, each vertex w corresponds an edge x_iy_j holding 
    f_10(w)+f_10(x_iy_j)=p-f(x_iy_j)+f(w)=p
  true, except the singularity f(x_0)=⌊ p⌋.






We identify the vertices of T_1,T_2,… ,T_10 with the same labels into one, and delete the multiple edges, the resulting graph is just the desired multiple-tree matching partition G=⊕_F⟨ T_i⟩ ^10_1 with the v-proper labelling f holding f(V(G))=[0,p-1] true and the e-set labelling F satisfying F(x_iy_j)={f_k(x_iy_j): k∈ [1,10]} for each edge x_iy_j∈ E(G).

The labellings f_2,f_3,… ,f_10 shown in the above proof can deduce the set-ordered graceful labelling f, we omit the proof since the proof methods are similar to that in <cit.>.



If a bipartite (p,q)-graph G admits a set-ordered graceful labelling, then G admits a set-ordered graceful/odd-graceful total set-labelling.

 Suppose that G has its own vertex bipartition (X,Y) with X={x_i:i∈ [1,s]} and Y={y_j:j∈ [1,t]} holding s+t=|V(G)|=p true. By the hypothesis of this theorem, G admits a set-ordered graceful labelling f defined by f(x_i)=i-1 for i∈ [1,s], f(y_j)=s+j-1 for j∈ [1,t] and

    f(x_iy_j)=f(y_j)-f(x_i)=s+j-i
 for each edge x_iy_j∈ E(G), such that f(E(G))=[1,q].

We define a total  set-labelling F: V(G)∪ E(G)→ [0, p+q]^2  as follows: F(x_i)=[0,i-1] with i∈ [1,s], F(y_j)=[0,s+j-1] with j∈ [1,t] and F(x_iy_j)=F(y_j)∖ F(x_i)=[i,s+j-1] for each edge x_iy_j∈ E(G). Clearly,  F(u)≠ F(w) for distinct elements u,w∈ V(G)∪ E(G). Moreover, we have

    {|F(x_iy_j)|:i∈ [1,s],j∈ [1,t]}
       ={s+j-i:i∈ [1,s],j∈ [1,t]}
       ={f(x_iy_j):x_iy_j∈ E(G)}
       =f(E(G))=[1,q],

and F(x_i)⊂ F(y_j) with i=|F(x_i)|<|F(y_j)|=s+j. Thereby, F is really  a set-ordered graceful total set-labelling of G.

For proving that G admits a set-ordered odd-graceful total set-labelling, we set a total  set-labelling F': V(G)∪ E(G)→ [0, p+q]^2  in the following way: F'(x_i)=[0,2(i-1)] with i∈ [1,s], F'(y_j)=[0,2(s+j)-3] with j∈ [1,t] and

    F'(x_iy_j)=F'(y_j)∖ F'(x_i)=[2(i-1)+1,2(s+j)-3]
 for each edge x_iy_j∈ E(G). Furthermore, F'(x_i)⊂ F'(y_j) with

    2i-1=|F'(x_i)|<|F'(y_j)|=2(s+j)-2

and

    {|F'(x_iy_j)|:i∈ [1,s],j∈ [1,t]}   =f(E(G))
       =[1,2q-1]^o.


We are done for the proof of the theorem.


By the results appeared in <cit.>, we can show other type of  total set-labelling on bipartite graphs admitting set-ordered graceful labellings.


The graceful graph G shown in Fig.<ref>(b) is a graceful matching of K_5 admitting a v-set e-proper graceful labelling, and an odd-graceful graph H shown in Fig.<ref>(d) is an odd-graceful matching of K_5 having a v-set e-proper odd-graceful labelling. The graceful graph G and the odd-graceful graph H can be obtained from K_5 by the vertex-split operation introduced in Section I. Two graphs shown in Fig.<ref>(b) and (d) can be shrunk back to K_5. Identifying two non-adjacent vertices u,v of a graph H into one w=u∘ v if N(u)∩ N(v)=∅ until, any pair of vertices x,y of the last graph H^* hold |N(u)∩ N(v)|≥ 1 true. Clearly, |E(H)|=|E(H^*)|. We call H^* a non-contracted graph, H has a non-contracted H^*-kernel. Two graphs shown in Fig.<ref>(b) and (d) both have a non-contracted K_5-kernel.



Each complete graph K_n admits a v-set e-proper (odd-)graceful labelling.

 We have known that K_5 admits a v-set e-proper graceful labelling. Assume that K_n admits a v-set e-proper graceful labelling (F,f) such that F:V(K_n)→ [0,M_n] with F(x_i)∩ F(x_j)=∅ for distinct x_i,x_j∈ V(K_n) and f(E(K_n))=[1,M_n], where M_n=1/2n(n-1). We add a new vertex x_n+1 to K_n by joining x_n+1 with each vertex of K_n, and label it with the number M_n+n. If x_i∈ V(K_n) such that M_n+n-a_i,k_i=M_n+k_i for a_i,k_i∈ F(x_i)={a_i,1,a_i,2,… ,a_i,m_i} with 1≤ m_i≤ M_n, we put x_i into a set S such that each F(x_j) with x_j∈S=V(K_n)∖ S has no element of F(x_j)={a_j,1,a_j,2,… ,a_j,m_j} with 1≤ m_j≤ M_n holds M_n+n-a_j,l=M_n+l true. We add an number b_j∈ [M_n+1,M_n+n]∖{n-k_i:x_i∈ S} to F(x_j) for x_j∈S, one-vs-one, thus, we get a v-set e-proper graceful labelling (F',f') of K_n+1 holding F':V(K_n+1)→ [0,1/2n(n+1)] true with F'(x)∩ F'(y)=∅ for distinct x,y∈ V(K_n+1) and f'(E(K_n+1))=[1,1/2n(n+1)].

By the induction of hypothesis, we claim that each complete graph admits a v-set e-proper graceful labelling, and furthermore this proof way can be used to show each complete graph admits a v-set e-proper odd-graceful labelling.


Lemma <ref> enables us to obtain the following result:


A (p,q)-graph G with a non-contracted H-kernel admits a proper ε-labelling if and only if H admits a v-set e-proper ε-labelling.







Any connected (p,q)-graph can be split into a tree of q+1 vertices.

 Our proof is based on induction of vertex number. As p=2 and q=1, the lemma is obvious. Assume that a connected (p,q)-graph can be split into a tree of q+1 vertices. We consider any connected (p+1,q')-graph G. There exists a spanning tree T in G, since G is connected. We take a leaf x of T, so the graph G-x is a connected (p,q'-m)-graph, where m=|N(x)|, and the neighbor set N(x) collects all neighbors x_1,x_2,… x_m of the vertex x. By the hypothesis of induction, the connected (p,q'-m)-graph G-x can be split into a tree H of q'-m vertices. Suppose that each vertex x_i∈ N(x) was split into x_i,1,x_i,2, … ,x_i,m_i in H. We add new vertices x'_i to x_i,1 by an edge x'_ix_i,1 with i∈ [1,m], the result graph is just a tree H' of q'-m+m vertices. Thereby, H' is the desired tree split from G, and the leaves x'_1,x'_2,… ,x'_m of H' are the result of splitting the vertex x of G.


By Lemma <ref> we can see: “If every tree is (odd-)graceful, then any connected (p,q)-graph admits a v-set e-proper (odd-)graceful labelling. Conversely, if a connected (p,q)-graph G admits a v-set e-proper (odd-)graceful labelling (F,f) holds f(E(G))=[1,q] (resp. f(E(G))=[1,2q-1]) true and ⋃_u∈ V(G)F(u)=[0,q] (resp. ⋃_u∈ V(G)F(u)⊂ [0,2q-1]), then it can be split into a (an odd-)graceful tree”. For a connected (p,q)-graph G holding q≡ 0,3 ( 4) true, we can say G admits a v-set e-proper (odd-)graceful labelling. Thereby, we conjecture:

Each connected graph with no multiple edges and self-loops admits a v-set e-proper (odd-)graceful labelling.




In <cit.>, the authors show some Euler graphs admit v-set e-proper X-labellings with X ∈{graceful, odd-graceful, harmonious, k-graceful, odd sequential, elegant, odd-elegant, felicitous, odd-harmonious, edge-magic total}. Thereby, we can generalize Conjecture <ref> to other labellings. Zhou et al. in<cit.> have proven: Lobsters admit odd-graceful labellings, then we have


If  a connected graph can be split into a tree admitting a v-set e-proper X-labelling, where X is a graph labelling, then it admits a v-set e-proper X-labelling.


Notice that a  connected (p,q)-graph G admitting a graceful labelling f can be split into a tree T of q edges, then T admits a splitting  graceful labelling g induced by f, here, there are at least two vertices u,v holding g(u)=g(v) true under g(V(T))⊆ [0,q], but g(E(T))=[1,q].


Each tree with diameter less than three admits a splitting graceful labelling.





 §.§ Magic type of matching labellings



^* Let f:V(G)∪ E(G)→ [1,p+q] be a total labelling of a (p,q)-graph G. If there is a constant k such that 
    f(u)+f(uv)+f(v)=k,
 and each edge uv corresponds another edge xy holding f(uv)=|f(x)-f(y)| true, then we call f a relaxed edge-magic total labelling (relaxed Emt-labelling) of G (called a relaxed Emt-graph) (see Fig.<ref>(a)).


^* Suppose that a (p,q)-graph G admits a vertex labelling f:V(G) → [0,2q-1] and an edge labelling g:E(G)→ [1,2p-1]^o. If there is a constant k such that 
    f(u)+g(uv)+f(v)=k
 for each edge uv∈ E(G), and g(E(G))=[1,2p-1]^o, then we call (f,g) an odd-edge-magic matching labelling (Oemm-labelling) of G (called an Oemm-graph). See Fig.<ref>(c),Fig.<ref>(a) and Fig.<ref> (b).


^* Suppose that a (p,q)-graph G admits a vertex labelling f:V(G)→ [0,2q-1] and an edge labelling g:E(G)→ [1,2q-1]^o, and let s(uv)=|f(u)-f(v)|-g(uv) for uv∈ E(G). If

(i) each edge uv corresponds an edge u'v' such that g(uv)=|f(u')-f(v')|;

(ii) and there exists a constant k' such that each edge xy has a matching edge x'y' holding s(xy)+s(x'y')=k' true;

(iii) there exists a constant k such that f(uv)+|f(u)-f(v)|=k for each edge uv∈ E(G).

Then we call (f,g) an ee-difference odd-edge-magic matching labelling (Eedoemm-labelling) of G (called a Eedoemm-graph). (see Fig.<ref>(a) and (b))





We, again, define a new labelling with more restrictive conditions as follows:


^* A total labelling f:V(G)∪ E(G)→ [1,p+q] for a bipartite (p,q)-graph G is a bijection and holds:

(i) (e-magic) f(uv)+|f(u)-f(v)|=k for a constant k and each edge uv∈ E(G);

(ii) (ee-difference) each edge uv∈ E(G) matches with another edge xy∈ E(G) holding f(uv)=|f(x)-f(y)| (or f(uv)=2(p+q)-|f(x)-f(y)|);

(iii) (ee-balanced) let s(uv)=|f(u)-f(v)|-f(uv) for uv∈ E(G), then there exists a constant k' such that each edge uv matches with another edge u'v' holding s(uv)+s(u'v')=k' (or 2(p+q)+s(uv)+s(u'v')=k') true;

(iv) (EV-ordered) f_min(V(G))>f_max(E(G)) (or f_max(V(G))<f_min(E(G)), or f(V(G))⊆ f(E(G)), or f(E(G))⊆ f(V(G)), or f(V(G)) is an odd-set and f(E(G)) is an even-set);

(v) (ve-matching) there exists a constant k” such that each edge uv matches with one vertex w such that f(uv)+f(w)=k”, and each vertex z matches with one edge xy such that f(z)+f(xy)=k”, except the singularity f(x_0)=⌊p+q+1/2⌋;

(vi) (set-ordered) f_max(X)<f_min(Y) (or f_min(X)>f_max(Y)) for the bipartition (X,Y) of V(G).

We then call f a 6C-labelling.

For a given (p,q)-tree G admitting a 6C-labelling f, if another (p,q)-tree H admits a 6C-labelling g such that

    f(V(G))∖ X^*=g(E(H)), f(E(G))=g(V(H))∖ X^*
 and f(V(G))∩ g(V(H))=X^*, where X^*={⌊p+q+1/2⌋}, we identify the vertex x_0 of G having f(x_0)=⌊p+q+1/2⌋ with the vertex w_0 of H having g(w_0)=⌊p+q+1/2⌋ into one to form a graph ⊙_1⟨ G,H ⟩, called a 6C-complementary matching. See examples shown in Fig.<ref> and Fig.<ref>.




If a tree T admits a 6C-labelling, then there exists another tree H admitting a 6C-labelling such that ⊙_1⟨ T,H ⟩ is a 6C-complementary matching.


Suppose that a (p,q)-tree T admits a 6C-labelling f, we define another labelling h of T by h(x)=2(p+q+1)-f(x) for x∈ V(T), so h(uv)=(p+q+1)-f(uv) for uv∈ E(T). Next, we set E(T)={u_iv_i:i∈ [1,q]} holding h(u_jv_j)<u_j+1v_j+1 true with j∈ [1,q-1]. Now, we can defined a labelling g of a copy T' of T in the way: g(x)=h(x) for x∈ V(T')=V(T), and g(u_iv_i)=2p+q+1-h(u_iv_i) for u_iv_i∈ E(T')=E(T). Notice that

    g(u_iv_i)   =2p+q+1-h(u_iv_i)
       =2p+q+1-[(p+q+1)-f(u_iv_i)]
       =f(u_iv_i)+p
 for u_iv_i∈ E(T')=E(T). We claim that g is a 6C-labelling of  T' too, which means that ⊙_1⟨ T,T' ⟩ is a 6C-complementary matching.



A tree admits a set-ordered graceful labelling if and only if it admits a 6C-labelling.

 Suppose that (X,Y) is the bipartition of vertex set of a tree T, where X={x_i:i∈ [1,s]} and Y={y_j:j∈ [1,t]} with vertex number |V(T)|=p=s+t and edge number |E(T)|=p-1.


The proof of “if”. Notice that T admitting a set-ordered graceful labelling g, so each vertex is labeled as g(x_i)=i-1 for i∈ [1,s] and g(y_j)=s+j-1 for j∈ [1,t], and furthermore each edge x_iy_j∈ E(T) has its label g(x_iy_j)=g(y_j)-g(x_i)=s+j-i.

We define another labelling f for the tree T in the way: f(w)=p+g(w) for w∈ V(T), and 
    f(x_iy_j)=p-g(x_iy_j)=p-|g(x_i)-g(y_j)|
 for x_iy_j∈ E(T). Clearly,

    f(V(T))=[p,2p-1],   f(E(T))=[1,p-1].


(i) (e-magic) Each edge x_iy_j∈ E(T) holds f(x_iy_j)+|f(x_i)-f(y_j)|=p-g(x_iy_j)+g(x_iy_j)=p true.

(ii) (ee-difference) Each edge x_iy_j∈ E(T) matches with another edge x'_iy'_j∈ E(T) holding p-g(x_iy_j)=g(x'_iy'_j) such that


    f(x_iy_j)   =p-g(x_iy_j)=g(x'_iy'_j)
       =|g(x'_i)-g(y'_j)|
       =|p+g(x'_i)-[p+g(y'_j)]|
       =|f(x'_i)-f(y'_j)|.


(iii) (ee-balanced) Let s(x_iy_j)=|f(x_i)-f(y_j)|-f(x_iy_j) for x_iy_j∈ E(T), so

    s(x_iy_j)   =|f(x_i)-f(y_j)|-f(x_iy_j)
       =|g(x'_i)-g(y'_j)|-p+g(x_iy_j)
       =2g(x_iy_j)-p,
 which distributes {2-p,4-p, … ,-2,0,2,4,… ,p-2} if p is even, or {2-p,4-p, … ,-3,-1,1,3,… ,p-2} if p is odd. Thereby, each edge x_iy_j∈ E(T) matches with another edge x”_iy”_j∈ E(T) such that s(x_iy_j)+s(x”_iy”_j)=0, except that edge e golding s(e)=0 as p is even.

(iv) (EV-ordered) f_max(E(T))<f_min(V(T)) from (<ref>).

(v) (ve-matching) The form (<ref>) tells us: Each edge uv matches with one vertex w such that f(uv)+f(w)=2p, and each vertex z matches with one edge xy such that f(z)+f(xy)=2p, except the singularity f(w')=p.

(vi) (set-ordered) f_max(X)<f_min(Y) for the bipartition (X,Y) of V(G) according to (<ref>).

Hence, we claim that the labelling f admits really a 6C-labelling defined in Definition <ref>.


The proof of “only if”. Suppose that T admits a 6C-labelling h. By the property (iv) and h(V(T)∪ E(T))=[1,2p-1], we get h(E(T))=[1,p-1] and h(V(T))=[p,2p-1]. We define a labelling h^* as: h^*(w)=h(w)-p for w∈ V(T), which gives h^*(V(T))=[0,p-1]; and h^*(x_iy_j)=p-h(x_iy_j) for each edge x_iy_j∈ E(T), so h^*(E(T))=[1,p-1]. The property (i) enables us to compute


    h^*(x_iy_j)   =p-h(x_iy_j)
       =p-[p-|h(x_i)-h(y_j)|]
       =|[h(x_i)-p]-[h(y_j)-p]|
       =|h^*(x_i)-h^*(y_j)|,

that is, h^* is graceful. The property (vi) means that h^* is set-ordered.








In Fig.<ref>(a), G=⊙_1⟨ T,G_3⟩ is obtained by identifying two singularities 13 of T and G_3 shown in Fig.<ref> into one, where the 6C-labelling f_G_3 of G_3 is the reciprocal-inverse labelling of the 6C-labelling f_T of T, so we say f_G_3 and f_T are matching to each other, and (f_G_3,f_T)  is a 6C-complementary matching. Observe the 6C-labelling θ of G=⊙_1⟨ T,G_3⟩, we can see such properties: θ(E(G))⊂θ(V(G)); 13 (=p) is the common singularity of two trees T and G_3; and θ(uv)+|θ(u)-θ(v)|=13 (=p) for each edge uv∈ E(T), θ(xy)-|θ(x)-θ(y)|=13 (=p) for each edge xy∈ E(G_3). The particular properties of the 6C-labelling θ of G=⊙_1⟨ T,G_3⟩ enables us to define a new labelling. Fig.<ref>(b) and Fig.<ref>(c) show two odd-even separable 6C-labellings. Thereby, we can have the following results (the proofs of these two results are similar to that in the proof of Theorem <ref>):


A tree admits a set-ordered graceful labelling if and only if it admits an odd-even separable 6C-labelling defined in Definition <ref>.



Suppose that two trees T and H of p vertices admit set-ordered graceful labellings. Then G=⊙_1⟨ T,H⟩ admits a 6C-labelling θ with

    θ(uv)+|θ(u)-θ(v)|=p

for each edge uv∈ E(T),

    θ(xy)-|θ(x)-θ(y)|=p
 for each edge xy∈ E(H).



Similarly with Definitions <ref> and <ref>, we can define a graceful-magic matching labelling (e.g. the edge-magic total labelling) and an ee-difference graceful-magic matching labelling (f,g) (see Fig.<ref>(c) and (d)).


^* Suppose that a (p,q)-graph G admits a vertex labelling f:V(G)→ [0,p-1] and an edge labelling g:E(G)→ [1,q], and let s(uv)=|f(u)-f(v)|-g(uv) for uv∈ E(G). If

(i) each edge uv corresponds an edge u'v' such that g(uv)=|f(u')-f(v')| (or g(uv)=p-|f(u')-f(v')|);

(ii) and there exists a constant k” such that each edge xy has a matching edge x'y' holding s(xy)+s(x'y')=k” true;

(iii) there exists a constant k such that |f(u)-f(v)|+f(uv)=k for each edge uv∈ E(G);

(iv) there exists a constant k' such that each edge uv matches with one vertex w such that f(uv)+f(w)=k', and each vertex z matches with one edge xy such that f(z)+f(xy)=k', except the singularity f(x_0)=0.

Then we call (f,g) an ee-difference graceful-magic matching labelling (Dgemm-labelling) of G (called a Dgemm-graph). (see examples shown in Fig.<ref>(c) and (d))







 §.§ Inverse matchings



<cit.> If there exists a constant k≥ 0, such that a (p, q)-graph G admits a total labelling f:V(G)∪ E(G)→ [1, p+q], each edge uv∈ E(G) holds

    |f(u)+f(v)-f(uv)|=k
 and f(V(G)∪ E(G))=[1, p+q] true, we call f an edge-magic graceful labelling of G, and k a magic constant. Moreover, f is called a super edge-magic graceful labelling if f(V(G))=[1, p].



<cit.> A ve-exchanged matching labelling h of an edge-magic graceful labelling f of a (p, q)-graph G is defined as: h:V(G)∪ E(G)→ [1, p+q], each edge uv∈ E(G) holds h(uv)=|h(u)-h(v)| true (or h(uv)+|h(u)-h(v)|=k, or h(uv)=h(u)+h(v) ( q), or |h(u)+h(v)-h(uv)|=k, or h(u)+h(uv)+h(v)=k), such that h(V(G)∪ E(G))=[1, p+q], h(V(G))∖{a_0}=f(E(G)) and h(E(G))=f(V(G))∖{a_0}, where a_0=⌊p+q+1/2⌋ is the singularity of two labellings f and h. (see Fig.<ref>(b) and (c)).



By Definition <ref>, we propose the concept of “reciprocal-inverse matching labelling”: Suppose that a (p,q)-graph G admits an edge-magic graceful labelling f, and a (q,p)-graph H admits an edge-magic graceful labelling g. If

    f(E(G))=g(V(H))∖ X^*, f(V(G))∖ X^*=g(E(H))
 for X^*=f(V(G))∩ g(V(H)), we say that f and g are reciprocal-inverse (or reciprocal complementary), moreover H (or G) is an inverse matching of G (or H).

Observe Fig.<ref>(b) and (c), we have the total-magic matching labelling (f,f') of a (p,q)-graph G defined as: Two total labellings f:V(G)∪ E(G)→ [1,p+q] and  f':V(G)∪ E(G)→ [1,p+q] such that 
    f(x)+f'(x)=f(uv)+f'(uv)
 for any vertex x∈ V(G) and edge uv∈ E(G). We can ask for f (or f') being an edge-magic total labelling, or an edge-magic graceful labelling, or other labellings defined on V(G)∪ E(G) and [1,p+q].



 §.§ Self-matchings


For a partition K_n=G∪G with the same vertex set V(K_n)=V(G)=V(G) and edge-disjoint sets E(G)∩ E(G)=∅, we say that G and G are complementary to each other, and we say G is self-complementary if G is isomorphic to G. So, we can consider this case as a self-matching. Motivated from complete graph K_n=G∪G, we propose

^* Let W be a universal graph, and two graphs G,H of W hold E(G)∩ E(H)=∅ and V(W)=V(G)∪ V(H) true. If E(W)=E(G)∪ E(H), we say G and H to be W-complementary to each other, and moreover we call G to be self-matching (also, self-complementary) if G is isomorphic to H, that is, G≅ H.

For example, if T is isomorphic to T' in a universal graph ⊙⟨ T,T'⟩, then we say T a self-matching.


If a connected (p,q)-graph G admits an edge-magic total labelling f, then there exists a connected graph H admitting a ve-matching labelling g such that f(E(G))=g(V(H)) and f(V(G))=g(E(H)) for G and H being not trees. We prove this proposition as: We take H as a copy of G, and define the dual labelling of f for H as: g(x)=max f(V(G)∪ E(G))+min f(V(G)∪ E(G))-f(x) for x∈ V(G)∪ E(G). So, G is self-matching with H under the ve-matching labelling.

If a connected (p,q)-graph G admits an odd-graceful labelling f:V(G)→ [0,2q-1], then there exists another connected graph H admitting a pan-odd-graceful labelling g:V(H)→ [1,2q] such that ⊙⟨ G,H⟩ admits a twin odd-graceful labelling. For showing this claim, we let H≅ G, and define g(x)=f(x)+1 for x∈ V(H)=V(G), and then identify the vertices of G and H with the same labels into one for obtaining ⊙⟨ G,H⟩. Here, G is a self-matching.

If a connected (p,q)-graph G admits a 6C-labelling f, G has its own reciprocal complementary H admitting a 6C-labelling g, and f and g are pairwise reciprocal-inverse labellings, so ⊙⟨ G,H⟩ is a self-matching when G≅ H (see for examples T and G_1 shown in Fig.<ref>).


If a tree T admits a set-ordered graceful labelling, then we have a self-matching ⊙_1⟨ T,T⟩ admitting a 6C-labelling.



If a tree T admits a set-ordered odd-graceful/odd-elegant labelling, then there exists a self-matching ⊙_1⟨ T,T⟩ admitting a twin odd-graceful/odd-elegant labelling.

 By the hypothesis of the corollary, a tree T has its own vertex bipartition (X,Y) with X={x_i:i∈ [1,s]} and Y={y_j:j∈ [1,t]} with vertex number |V(T)|=p=s+t and edge number |E(T)|=p-1. Since T admits a set-ordered graceful labelling f, so we get f(x_i)=i-1 for i∈ [1,s] and f(y_j)=s+j-1 for j∈ [1,t], and f(x_iy_j)=f(y_j)-f(x_i)=s+j-i for each edge x_iy_j∈ E(T). Clearly, f(X)<f(Y).

(1) We define a labelling g of a copy T' of T with (X',Y')=(X,Y) as: g(x'_i)=2f(x_i)=2(i-1) for i∈ [1,s] and g(y'_j)=2f(y_j)-1=2(s+j)-3 for j∈ [1,t], immediately,


    g(x'_iy'_j)   =|g(y'_j)-g(x'_i)|
       =|2(s+j)-3-2(i-1)|
       =2s+2(j-i)-1
       =2(s+j-i)-1
       =2f(x_iy_j)-1.


So, g is an odd-graceful labelling of T', since g(X')={0,2,…, 2(s-1)} is an even-set, g(Y')={2s-1,2s+1,…, 2p-3} is an odd-set, and g(E(T))=[1,2p-3]^o is an odd-set too. Now, we take another copy T” of T with (X”,Y”)=(X,Y), and make a complementary labelling g” of the odd-graceful labelling g' by setting g”(w)=g'(w)+1 for w∈ V(T), clearly, g”(E(T))=g'(E(T)). Moreover, g”(X)=[1, 2s-1]^o, g”(Y)={2s,2s+2,…, 2p-2}, we can see

    g”(V(T))∩ g'(V(T))={2s-1}

and

    g”(V(T))∪ g'(V(T))=[0,2p-2].
 T” is the complementary matching of T'. Thereby, ⊙_1⟨ T',T”⟩ admits a twin odd-graceful labelling and it is a self-matching.

(2) The proof of ⊙_1⟨ T',T”⟩ admitting a twin odd-elegant labelling is very similar to that of the above (1), here, it takes “2p-2”.

The proof of this corollary is finished.




 §.§ Set-ordered matchings


Suppose that a (p,q)-graph G admits an ε-labelling f: V(G)→ [0,p-1] (or [1,p+q], or [0,2q-1], or [1,2q]), G is bipartite with its own bipartition (X,Y). The symbol f_max(X)<f_min(Y) is defined by 
    max{f(x): x∈ X}< min{f(y): y∈ Y}
 and we call f a set-ordered ε-labelling of G. As known, many set-ordered ε-labellings have good properties, and have been connected with other labellins equivalently (<cit.>). However, determining a graph whether admits a set-ordered ε-labelling seems to be not easy.


Suppose that a bipartite (p,q)-graph G admits an ε-labelling, then there exists another bipartite (p,q)-graph H such that a bipartite graph G⊖ H obtained by using an edge to join a vertex of G with a vertex of H admits a set-ordered ε-labelling.

 Let (X,Y) be the bipartition of vertices of G such that each edge uv∈ E(G) satisfies u∈ X and v∈ Y. We take a copy of G, denoted as H with its bipartition (X',Y')=(X,Y). Suppose that G admits an ε-labelling f, so H admits an ε-labelling f' which is a copy of f. Now, we use an edge to join any vertex u of G with its isomorphic vertex u' of H for producing the desired graph G⊖ H. Clearly, G⊖ H is a bipartite (2p,2q+1)-graph with bipartition (X∪ Y',X'∪ Y). We define a labelling g as: g(x)=f(x) for x∈ X, g(y')=f(y') for y'∈ Y', g(w)=f(w)+p for w∈ X', and g(z)=f(z)+p for z∈ Y. Obviously,

    g_max(X∪ Y')<g_min(X'∪ Y),
 so g is a set-ordered ε-labelling of G⊖ H.


If the graph G⊖ H based on two disjoint graphs G and H admits a set-ordered ε-labelling, we say G to be a set-ordered matching of H, and vice versa. It may be interesting to look for G≇H in the set-ordered matching G⊖ H.





 §.§ Labellings with extremal conditions



^* Let f:V(G)→ [0,q] be a vertex labelling of a (p,q)-graph G, and let

    S_um(G,f)=∑_uv∈ E(G)|f(u)-f(v)|,
 we call f a difference-sum labelling. Find two extremum max_f S_um(G,f) (profit) and min_f S_um(G,f) (cost) over all difference-sum labellings of G.

A tree T shown in Fig.<ref> has max_f S_um(T,f)=S_um(T,h_1)=84 and min_f S_um(T,f)=S_um(T,h_4)=20. We will show some properties of difference-sum labellings of graphs with necessary proofs.

[(Extr-1) ]

  * Each complete graph K_n holds

    min_g S_um(K_n,g)=max_f S_um(K_n,f)
       =∑^n-1_i=1∑^n-i_k=1k=1/2∑^n-1_i=1(n-i+1)(n-i).



  * Let G be a caterpillar, then

  (a) Adding a leaf to G produces another caterpillar G+e, we have

    min_f S_um(G,f)   ≤min_gS_um(G+e,g)
       ≤min_f S_um(G,f)+3.


  (b) Suppose H is another caterpillar with |V(G)|=|V(H)|. If two diameters D(H)>D(G), then

    min_g S_um(H,g)≤min_f S_um(G,f).






  * If a disconnected graph G has its components G_1,… ,G_m, then 
    max_fS_um(G,f)=∑^m_i=1max_gS_um(G_i,g),

 
    min_fS_um(G,f)=∑^m_i=1min_gS_um(G_i,g).


  * Adding an edge uv to join two non-adjacent vertices u,v of G produces a new graph G+uv, then max_f S_um(G,f)≤max_h S_um(G+uv,h).

  * If f and f^* are dual difference-sum labellings to each other, then S_um(G,f)=S_um(G,f^*).


  * For a tree T of p vertices, a path P_p of p vertices and a star K_1,p-1, we have

    p-1=   min_f S_um(P_p,f)≤min_f S_um(T,f)
       ≤min_f S_um(K_1,p-1,f)=p^2/4,p^2-1/4.



  * A difference-sum labelling h of a tree T holds max_f S_um(T,f)=S_um(T,h) true if and only if h_max(X)< h_min(Y) with the partition (X,Y) of T.

 Let V(T)=X∪ Y with X∩ Y=∅, where X={x_1,x_2,… ,x_a}, Y={y_1,y_2,… ,y_b}. Suppose G admits a vertex labelling f:V(T)→ [0,p-1] such that

    0=   f(x_1)<f(x_2)<⋯ f(x_i)<f(x_i+1)<⋯
       <f(x_a)<f(y_1)<f(y_2)<⋯ f(y_j)<
       f(y_j+1)<⋯ <f(y_b)=p-1

We exchange two labels f(x_i) and f(y_j) for some i≠ j. In other word, we define another vertex labelling g:V(T)→ [0,p-1] such that g(x_i)=f(y_j), g(y_j)=f(x_i) and g(w)=f(w) for w∈ V(T)∖{x_i,y_j}. Clearly, there is no g_max(X)< g_min(Y). We claim


    S_um(T,f)>S_um(T,g).


Let the set of neighbors of the vertex x_i is denoted as N(x_i)={y_i_1,y_i_2,… y_i_m}, the set of neighbors of the vertex y_j is written as N(y_j)={x_j_1,x_j_2,… x_j_n}. We compute

    |g(x_i)-g(y_i_s)|=|f(y_j)-f(y_i_s)|≤ f(y_i_s)-
       f(y_1)<f(y_i_s)-f(x_a)≤ f(y_i_s)-f(x_i),

and

    |g(y_j)-g(x_j_t)|=|f(x_i)-f(x_j_t)|≤ f(x_a)-
       f(x_j_t)<f(y_1)-f(x_j_t)≤ f(y_1)-f(x_j_t).

Thereby, our assertion (<ref>) holds true.





  * Max-min-sum Algorithm for computing max_f S_um(T,f).

  Initiation. Take a labelling f_0:V(T)→ [0,p-1].

  Iteration. For an optimal labelling f_k:V(T)→ [0,p-1], find a pair of vertices x,y, and check whether

    ∑_x_i∈ N(x)|f_k(y)-f(x_i)|≥ (≤)∑_x_i∈ N(x)|f_k(x)-f(x_i)|

and

    ∑_y_j∈ N(y)|f_k(x)-f(y_j)|≥ (≤)∑_y_j∈ N(y)|f_k(y)-f(y_j)|.

If it is so, we define a new labelling f_k+1 as: f_k+1(x):=f_k(y), f_k+1(y):=f_k(x), and f_k+1(w):=f_k(w) for w∈ V(T)∖{x,y}.

  Termination. If no two vertices x,y hold the forms (<ref>) and (<ref>) true, output the labelling f_k with S_um(T,f_k)=max_fS_um(T,f).

  Similarly, we can use (≤ ) in (<ref>) and (<ref>) to deal with the case min_fS_um(T,f).


  * If T is a caterpillar, then we can compute the exact value of min_f S_um(T,f).
 We show an algorithmic proof here. A caterpillar T shown in Fig.<ref> contains a path P=u_1u_2⋯ u_n, and each set of leaves v_i,j adjacent to a vertex u_i is denoted as L(u_i)={v_i,j:j∈ [1,m_i]} with m_i≥ 0 and i∈ [1,n]. So, each vertex u_i has its own degree deg(u_1)=|L(u_1)|+1=m_1+1, deg(u_j)=|L(u_j)|+2=m_j+2 with j∈ [2,n-1], deg(u_n)=|L(u_n)|+1=m_n+1. We define a labelling f of T as follows. Let N(x) be the set of neighbors of a vertex x.

  Step 1. For the vertices of N(u_1)=L(u_1)∪{u_2}, we set f(v_1,j)=j-1 with j∈ [1,m_1], f(u_1)=m_1, f(u_2)=m_1+1. Compute the sum

    ∑ ^m_1_j=1|f(v_1,j)-f(u_1)|=∑ ^m_1_j=1[m_1-f(v_1,j)]
       =1+2+⋯ +m_1=1/2(m_1+1)m_1,

and |f(u_1)-f(u_2)|=m_1+1-m_1=1.

  Step 2. Notices that u_i∈ N(u_i-1) with i∈ [2,n], so f(u_i) has been defined well. For the vertices of N(u_i)=L(u_i)∪{u_i-1,u_i+1} with i∈ [2,n-1], we set f(v_i,j)=f(u_i)+j with j∈ [1,m_i], f(u_i+1)=f(u_i)+m_i+1. Thereby, we have

    ∑ ^m_i_j=1|f(v_i,j)-f(u_i)|=∑ ^m_i_j=1[f(u_i)+j-f(u_i)]
       =1+2+⋯ +m_i=1/2(m_i+1)m_i,

and

    |f(u_i)-f(u_i+1)|=f(u_i)+m_i+1-f(u_i)=m_i+1.


  Step 3. For the vertices of N(u_n)=L(u_n)∪{u_n-1}, we set f(v_n,j)=f(u_n)+j with j∈ [1,m_n]. We get

    ∑ ^m_n_j=1|f(v_n,j)-f(u_n)|=∑ ^m_n_j=1[f(u_n)+j-f(u_n)]
       =1+2+⋯ +m_n=1/2(m_n+1)m_n.

Therefore, we summarize the above sub-sums as

    S_um(T,f)   =1/2(m_1+1)m_1+1+1/2(m_n+1)m_n
         ∑^n-1_k=21/2(m_k+1)m_k+∑^n_k=2(m_k+1)
       =n-m_1+1/2∑^n_k=1m_k(m_k+3)


We, now, optimize the sum S_um(T,f). According to the definition of the labelling f, |f(u_i)-f(u_i+1)|=f(u_i+1)-f(u_i)=m_i+1, so |f(u_i)-f(u_i-1)|=f(u_i)-f(u_i-1)=m_i-1+1. We select a vertex v_i,j for some j∈ [1,m_i], and define a new labelling g as: g(u_i)=f(v_i,j)=f(u_i)+j, g(v_i,j)=f(u_i), and g(w)=f(w) for w∈ V(T)∖{v_i,j,u_i}. Now, we inspect the sum S_um(T,g). From


    |g(u_i)-g(u_i-1)|=f(v_i,j)-f(u_i-1)
       =f(u_i)+j-f(u_i-1)
       =m_i-1+1+j

and

    |g(u_i)-g(u_i+1)|=f(u_i+1)-f(u_i)
       =f(u_i+1)-f(v_i,j)
       =f(u_i)+1+m_i-[f(u_i)+j]
       =m_i+1-j.


we have

    |f(u_i)-f(u_i-1)|+|f(u_i)-f(u_i+1)|
       =|g(u_i)-g(u_i-1)|+|g(u_i)-g(u_i+1)|.

and

    ∑ ^m_i_k=1|g(u_i)-g(v_i,k)|
       =|f(v_i,j)-f(u_i)|+∑ ^m_i_k=1, k≠ j|f(v_i,j)-f(v_i,k)|
       <∑ ^m_i_k=1|f(u_i)-f(v_i,k)|

We select a_i,0=⌊m_i+1/2⌋ with i∈ [1,n], thus, each sum

    ∑ ^m_i_k=1|g(u_i)-g(v_i,k)|   =∑ ^m_i_k=1, k≠ a_i,0|f(v_i,a_i,0)-f(v_i,k)|
       =2(1+2+⋯ +a_i,0)
       =a_i,0(1+a_i,0)

Clearly, 
    a_i,0(1+a_i,0)<∑ ^m_i_j=1|f(v_i,j)-f(u_i)|
 from in (<ref>). Furthermore, using (<ref>) and (<ref>) check the sum S_um(T,g), we can see S_um(T,g)=min_fS_um(T,f) holds true. This algorithm is correct and has the complex of polynomial time.









When considering network passwords, we have theoretical guarantee for using Topsnut-gpws made by caterpillars. A spider with three legs of length 2, also, is called an aster, denoted as A_2,2,2. Or, the deletion of all leaves of A_2,2,2 results in K_1,3. If each spanning tree of a graph G is a caterpillar, we call G to be caterpillar-pure. Jamison et al. <cit.> have shown: A connected graph is caterpillar-pure if and only if it does not contain any aster A_2,2,2 as a (not necessarily induced) subgraph.

We present a new extremal labelling, called felicitous-sum labelling (see an example in Fig.<ref>), as follow:


^* Let f:V(G)→ [0,q] be a labelling of a (p,q)-graph G, and let 
    F_um(G,f)=∑_uv∈ E(G)[f(u)+f(v)] ( q+1),
 we call f a felicitous-sum labelling. Find two extremum max_f F_um(G,f) and min_f F_um(G,f) over all felicitous-sum labellings of G. (See examples shown in Fig.<ref>)



Observe Fig.<ref> and Fig.<ref>, we can get two particular matching graphs A=⊙_12⟨ G_a,G_d⟩ with G_a,G_d shown in Fig.<ref> and B=⊙_9⟨ F_b,F_c⟩ with F_b,F_c shown in Fig.<ref>. These two particular matching graphs enable us to define two new concepts in the following  Definition <ref> and Definition <ref>, respectively.


^* Suppose that G_M and G_m are two copies of a (p,q)-graph G, and G_M admits a difference-sum labelling f_M holding S_um(G_M,f_M)=max_f S_um(G,f) true, G_m admits another difference-sum labelling f_m holding S_um(G_m,f_m)=min_f S_um(G,f) true. The identifying graph H=⊙⟨ G_M,G_m⟩ is called a Max-min difference-sum matching partition, moreover if H=⊙_p⟨ G_M,G_m⟩ holds E(G_M)∩ E(G_m)=∅ true, we call H a perfect Max-min difference-sum matching partition. (See a perfect Max-min difference-sum matching partition shown in <ref>(a))




^* Suppose that H_M and H_m are two copies of a (p,q)-graph H, and H_M admits a felicitous-sum labelling h_M holding F_um(H_M,h_M)=max_f F_um(G,f) true, H_m admits another felicitous-sum labelling h_m holding F_um(H_m,h_m)=min_f F_um(G,f) true. The identifying graph G=⊙⟨ H_M,H_m⟩ is called a Max-min felicitous-sum matching partition, and furthermore we call G a perfect Max-min felicitous-sum matching partition if G=⊙_p⟨ H_M,H_m⟩ holds E(H_M)∩ E(H_m)=∅ true. (see a perfect Max-min felicitous-sum matching partition shown in <ref>(b))

We guess: Each tree  induces a perfect Max-min difference-sum matching partition and a perfect Max-min felicitous-sum matching partition.







§ MATCHINGS FROM PROPER TOTAL COLORINGS


Graph coloring is an important branch of graph theory, since there are many unsolved problems and conjectures in various graph colorings. For example, the famous four color conjecture on planar graphs was proved in 1976 by Kenneth Appel and Wolfgang Haken, but only after many false proofs and counterexamples. It was the first major theorem to be proved using a computer. A  simpler proof using the same ideas and still relying on computers was published in 1997 by Robertson, Sanders, Seymour, and Thomas. Additionally, in 2005, the theorem was proved by Georges Gonthier with general-purpose theorem-proving software (Ref. Wikipedia). Unfortunately, there is no mathematical proof of the four color theorem up to now. Another example is the total coloring conjecture proposed by Behzad in 1965 and Vizing in 1964.





 §.§ Edge-magic and equitable proper total colorings


Coloring each of vertices and edges of a graph G with a number in [1,k] makes no two adjacent vertices/edges or incident edge/vertex having the same label, we call this coloring a proper total coloring, the minimum number of k for which G admits a proper total k-colorings is denoted as χ”(G). Let f:V(G)∪ E(G)→ [1,χ”(G)] be a proper total coloring of G with χ”(G)=|{f(x):x∈ V(G)∪ E(G)}|, and we call such coloring f to be total chromatic number pure (tcn-pure). Let d_f(uv)=f(u)+f(uv)+f(v) for each edge uv∈ E(G), and set

    B_tol(G,f)=max_uv ∈ E(G){d_f(uv)}-min_uv ∈ E(G){d_f(uv)}.

Determine a new parameter min_fB_tol(G,f) over all tcn-pure colorings of G, and call min_fB_tol(G,f) by the pan-bandwidth total chromatic number. Especially, a coloring h is called an edge-magic proper total coloring if B_tol(G,h)=0, or an equitably proper total coloring if B_tol(G,h)=1.


0.4cm

In Fig.<ref>, three complete bipartite graphs K_2,3, K_2,4 and K_3,3 admit six tcn-pure colorings: each h_i is the dually total coloring (also, matching total coloring) of f_i with i∈ [1,3]. Moreover, B_tol(K_2,3,f_1)=2, B_tol(K_2,4,f_2)=3 and  B_tol(K_3,3,f_3)=4; B_tol(K_2,3,h_1)=2,  B_tol(K_2,4,h_2)=3, B_tol(K_3,3,h_3)=3.





There are some obvious facts:
[Tot-1. ]

  * Any path P_n of n vertices admits an edge-magic proper total coloring, that is, min_fB_tol(P_n,f)=0.


  * A cycle C_n of n vertices admits an edge-magic proper total coloring if n≡ 0 ( 3), and admits an equitably total coloring, otherwise.




  * If h is the matching proper total coloring of a tcn-pure coloring f defined as: h(w)=[max f(V(G)∪ E(G))+min f(V(G)∪ E(G))]-f(w) for w∈ V(G)∪ E(G), then,

    d_h(uv)   =h(u)+h(uv)+h(v)
       =3(max f+min f)-[f(u)+f(uv)+f(v)]
       =3(max f+min f)-d_f(uv),
 thus,

    B_tol(G,h)   =max_uv ∈ E(G){d_h(uv)}-min_uv ∈ E(G){d_h(uv)}
       =max_uv ∈ E(G){d_f(uv)}-min_uv ∈ E(G){d_f(uv)}
       =B_tol(G,f).



0.4cm


It seems to be not easy to determine the exact value of the pan-bandwidth total chromatic number min_fB_tol(G,f) for a given simple graph G, since min_fB_tol(G,f) is related with the total chromatic number χ”(G), which lets us recall the long standing total coloring conjecture: “For any simple graph G, the elements of V (G)∪ E(G) can be colored with at most Δ (G)+2 colors so that no two adjacent or incident elements receive the same color, also χ”(G)≤Δ (G)+2.” Unfortunately, there are less significant results on the total labelling conjecture so far. The exact values of some special families of graphs have been obtained, such as K_n, complete bipartite graph K_m,n, complete k-partite graph K_m_1,m_2,… ,m_k, and join graph G+H and so on. We, as exercise, verify a simple result.

 
Let T be a tree, then the total chromatic number χ ”(T)=Δ(T)+1.

 The assertion is true if T is a star K_1,n-1 or a double star S_s,t, so assume T≠ K_1,n-1 and T≠ S_s,t. The following part of the proof is by induction on orders of trees and constrained by diameter D(T)≥ 4.

Case 1. If there is a vertex u of T such that deg_T(u)=2, which is adjacent to a leaf v with  deg_T(v)=1 in T. Let T_1=T-v, then Δ(T_1)=Δ(T). We take a proper χ ”(T_1)-total coloring f of T_1, hence, set f '(v)=f(uw), f '(uv)=f(w) and f '(x)=f(x) for x∈ [E(T)∪ V(T)]∖ N(u). It is clear that the coloring f ' is a proper χ ”(T_1)-total coloring of T such that

    χ ”(T)=χ ”(T_1)=Δ(T_1)+1=Δ(T)+1.


Case 2. For the case deg_T(u)≥ 3, we take a vertex u of T with its neighbor set N(u)={u_1,u_2,… ,u_k,u_0}, where k=deg_T(u)-1, u_i is a leaf of T with i∈ [1, k] and deg (u_0)≥ 2, and let T_2=T-u_1.

Now, we take a proper χ ”(T_2)-total coloring g of T_2 having χ ”(T_2)=Δ(T_2)+1, and then build a proper χ ”(T)-total coloring g' of T as: Let C=[1,χ ”(T_2)] be the color set of T_2 under g and C(g,w)={g(xw): xw∈ E(T_2)}∪{g(w)} for w∈ (T_2).

Case 2.1. If Δ(T_2)=Δ(T), then |C(g,u)|≤Δ(T_2), so there is a color α∈ C but α∉ C(g,u). We have that g'(v)=g(u_0), g'(uv)=α and g'(x)=g(x) for x∈ [E(T)∪ V(T)]∖{v,uv}. Hence,

    χ ”(T)=χ ”(T_2)=Δ(T_2)+1=Δ(T)+1.


Case 2.2. If Δ(T_2)=Δ(T)-1, so χ ”(T_2)=Δ(T_2)+1=Δ(T), and then we set g'(v)=g(u_0), g'(uv)=χ ”(T_2)+1 and g'(x)=g(x) for x∈ (E(T)∪ V(T))∖{v,uv}. Therefore,

    χ ”(T)=χ ”(T_2)+1=Δ(T)+1.


The proof of this lemma is finished.



 
A star also is a complete bipartite graph K_1,n. Then this star K_1,n admits an edge-magic proper total coloring for even n, that is, min_fB_tol(K_1,n,f)=0, or an equitably proper total coloring for odd n.

 Clearly, Δ(K_1,n)=n. Let this star K_1,n have its vertex set V(K_1,n)={x_0,x_1, x_2,… ,x_n} and edge set E(K_1,n)={x_ix_0:i∈ [1,n]}. We define a proper total coloring f of K_1,n as: If n is even, we set f(x_0)=1, f(x_0x_i)=1+i and f(x_i)=n+2-i with i∈ [1,n]. We can compute χ”(K_1,n)=Δ(K_1,n)+1=n+1, and

    d_f(u_0u_i)   =f(x_0)+f(x_0x_i)+f(x_i)
       =1+1+i+n+2-i
       =n+3,
 which shows B_tol(K_1,n,f)=0.

  If n is odd, we label f(x_0)=1, f(x_0x_i)=1+i with i∈ [1,n], f(x_i)=n+2-i with i∈ [1,n] and i≠ (n+1)/2, and f(x_(n+1)/2)=n+1-(n+1)/2. Clearly, χ”(K_1,n)=Δ(K_1,n)+1=n+1, d_f(u_0u_i)=f(x_0)+f(x_0x_i)+f(x_i)=1+1+i+n-i=n+2 with i∈ [1,n-1] and i≠ (n+1)/2, and

    d_f(u_0u_(n+1)/2)=f(x_0)+f(x_0x_(n+1)/2)+f(x_(n+1)/2)
       =1+[n+2-(n+1)/2]+[n+1-(n+1)/2]
       =n+3.


Thereby, we claim B_tol(K_1,n,f)=1, in other words, K_1,n admits an equitably proper total coloring.


 
Each bi-star S_m,n admits an equitably proper total coloring.

 By the definition of a bi-star S_m,n, it has its own vertex set V(S_m,n)={x_0,x_1, x_2,… ,x_m}∪{y_0,y_1, y_2,… ,y_n} and edge set E(S_m,n)={x_ix_0:i∈ [1,m]}∪{y_jy_0:j∈ [1,n]}∪{x_0y_0}. Without loss of generality, assume that m≥ n. We consider the case m=2a and n=2b and set a proper total coloring g of S_m,n as follows: g(x_0)=1, g(x_0x_i)=1+i with i∈ [1,2a], g(x_0y_0)=2a+2, g(y_0)=2, g(x_i)=2a+3-i with i∈ [1,2a] and i≠ a+1, g(x_a+1)=g(x_a+2); if a≠ b, g(y_0y_j)=2+j with j∈ [1,2b], g(y_j)=2a+1-j with i∈ [1,2b]; if a=b, g(y_0y_j)=2+i with j∈ [1,2b-1], g(y_0y_2b)=1, g(y_2b)=2a+2, g(y_j)=2a+1-j with j∈ [1,2b-2], g(y_2b-1)=3. It is not hard to verify B_tol(S_2a,2b,g)=1. Notice that

    g:V(S_2a,2b)→ [1,2a+2]=[1,Δ(S_2a,2b)+1].


  For other three cases m=2a and n=2b-1, m=2a-1 and n=2b-1, m=2a-1 and n=2b, the proof ways are similar to that of the case m=2a and n=2b. We claim that S_m,n admits an equitably proper total coloring.




 
There exist infinite trees admitting edge-magic proper total colorings.

 A spider S_m_1,m_2,…, m_n has n paths (called legs) P_i=u_i,1u_i,2⋯ u_i,m_i with m_i≥ 1 for i∈ [1,n], and a body u_0 is joined with u_i,1 by an edge u_0u_i,1 with i∈ [1,n]. As n is even, the star K_1,n having its vertex set {u_0,u_1,1,u_2,1,… ,u_n,1} and edge set {u_0u_i,1:i∈ [1,n]} admits an edge-magic proper total coloring f by Lemma <ref>. So, f(u_0)=1, f(u_0u_i,1)=1+i and f(u_i,1)=n+2-i with i∈ [1,n]. Notice that

    d_f(u_0u_i,1)   =f(u_0)+f(u_0u_i,1)+f(u_i,1)
       =1+n+2-i+1+i
       =n+3
 with i∈ [1,n]. Clearly, χ”(K_1,n)=n+1=Δ(K_1,n)+1.

We expend the coloring f to the spider S_m_1,m_2,…, m_n by coloring a leg P_i=u_i,1u_i,2⋯ u_i,m_i as: f(u_i,1u_i,2)=1 and f(u_i,2)=f(u_0u_i,1)=1+i, which shows d_f(u_i,1u_i,2) obeys (<ref>); next, f(u_i,2u_i,3)=f(u_i,1)=n+2-i and f(u_i,3)=f(u_0)=1, so d_f(u_i,2u_i,3) obeys (<ref>) too. Go on in this way, we have shown that the spider S_m_1,m_2,…, m_n admits f as its a proper total coloring such that

    χ”(S_m_1,m_2,…, m_n)=n+1=Δ(S_m_1,m_2,…, m_n)+1

and

    B_tol(S_m_1,m_2,…, m_n,f)=0.

The proof of the theorem is complete.


An example is shown in Fig.<ref> for understanding the proof of Theorem <ref>. Motivated from the technique in the proof of Theorem <ref>, we have:

 
For any tree T, we can add a leaf u to T with u∉V(T) such that the tree T+uv with v ∈ V(T) holds min_fB_tol(T,f)=min_gB_tol(T+uv,g) true.


See a generalized spider admitting an edge-magic proper total coloring shown in Fig.<ref> for understanding Lemma <ref>, which can help us to design random Topsnut-gpws or rooted Topsnut-gpw.





 
Each tree admits an equitable proper total coloring.

 We consider a tree T having diameter D_ia(T)≥ 4 since T with D_ia(T)≤ 3 follows Lemma <ref> and Lemma <ref>. Select a vertex u of T such that the neighbor set N(u)={u_1,u_2,… ,u_k,u_0}, where k=deg_T(u)-1, deg_T(u_i)=1 with i∈ [1, k] and deg (u_0)≥ 2. Without loss of generality, assume that k+2≤Δ(T), since we use the induction proof on numbers of vertices of trees.

Then, T admits a proper total coloring f holding B_tol(T,f)=min_gB_tol(T,g)=1 true. Notice that χ”(T)=Δ(T)+1, there exists a vertex w of T such that deg_T(w)=Δ(T). By the principle of induction, we add a new vertex x to T and join it with u by an edge ux. There are the following cases.

Case 1. If f(u_0)≠ f(u_iu) with i∈ [1,k], then we set f(ux)=f(u_0), f(x)=f(u_0u). Obviously, |d_f(u_0u)-d_f(ux)|=0.

Case 2. If f(u_j)≠ f(u_iu) for some i≠ j, then we set f(ux)=f(u_j), f(x)=f(u_ju), thus, |d_f(u_ju)-d_f(ux)|=0.

Case 3. Without loss of generality, we assume f(u_0)= f(u_ju) for some j, and f(u_i)=f(u_i'u) for each i∈ [1,k]. We have a color set 
    S={f(u_0u), f(u_1u), f(u_2u), …, f(u_ku),f(u)}
 such that |S|=Δ(T). We can arrange 
    f(u_0u)< f(u_1u)< f(u_2u)< … <f(u_ku).


By χ”(T)=Δ(T)+1, the cardinality of the color set holds |f(V(T)∪ E(T))|=Δ(T)+1 true, so there exists one color c∈ f(V(T)∪ E(T))∖ S. So, f(u_ju)< c <f(u_j+1u).

Case 3.1. If f(u)<f(u_ju) or f(u_j+1u)<f(u), immediately, we have c-f(u_ju)=1 and f(u_j+1u)-c=1, f(u_j+1u)-f(u_ju)=2. We set f(ux)=c, f(x)=f(u_ju), and furthermore


    |d_f(u_j+1u)-d_f(ux)|
       =|[f(u_j+1)+f(u_j+1u)+f(u)]
          -[f(x)+f(ux)+f(u)]|
       =|f(u_j+1)-f(u_ju)+f(u_j+1u)-c|
       =|c+1-2-c|=1.


Case 3.2. If f(u_ju)<f(u)<c<f(u_j+1u), according to χ”(T)=Δ(T)+1, we get f(u)-f(u_ju)=1, c-f(u)=1 and f(u_j+1u)-c=1. We let f(ux)=c, f(x)=f(u_j+1u), and moreover we can compute


    |d_f(u_j+1u)-d_f(ux)|
       =|[f(u_j+1)+f(u_j+1u)+f(u)]
          -[f(x)+f(ux)+f(u)]|
       =|f(u_j+1)+f(u_j+1u)-f(u_j+1u)-c|
       =|c+1-c|=1.

Summarizing the above cases, we have shown

    B_tol(T+ux,f)=B_tol(T,f)=1,
 that is, f is an equitable proper total coloring of the tree T+ux. The proof of this theorem is complete.



According to Lemma <ref> and Lemma <ref>, we claim that a tree T admits an edge-magic proper total coloring if its maximum degree Δ(T) is even, and T admits an equitable proper total coloring otherwise. Furthermore, we can make random rooted Topsnut-gpws by adding vertices and edges based on edge-magic/equitable proper total colorings. About rooted Topsnut-gpws G with edge-magic proper total colorings, we have the following problems: (1) The distance between two maximum degree vertices of G is at least 3. (2) For a fixed |V(G)|, how large is |E(G)|? and what is the number of maximum degree vertices of G? (3) The girth (length of the smallest cycle) of G is at least 6, and so on.

In  Fig.<ref>, we can get a text-based password

    D_vev=   5231631721721635272635235145163
       5217217235235217213613.

Clearly, no way by D_vev to reconstruct the original non-planar rooted Topsnut-gpw G shown in Fig.<ref>.






 §.§ Consecutive integer sets of complete graphs with proper total colorings


A complete graph K_m admits a proper total coloring f with χ”(K_m)=m+1 for even m, and χ”(K_m)=m for odd m. Let 
    f^*(E(K_m))={f(u)+f(uv)+f(v):uv ∈ E(K_m)}.
 Hence, we guess: f^*(E(K_m)) is a consecutive integer set [a,b] (see Fig.<ref>). Four proper total colorings h shown in Fig.<ref> match with four proper total colorings f shown in Fig.<ref>, we can see f^*(E(K_3))=h^*(E(K_3)) and f^*(E(K_5))=h^*(E(K_5)), so we say the proper total colorings f of K_3 and K_5 are self-matching about consecutive integer sets. Does any complete graph K_2n+1 admit a  proper total coloring f being self-matching about consecutive integer set?


Since any tree T admits an edge-magic proper total labelling f or an equitable  proper total labelling f, so 
    f^*(E(T))={f(u)+f(uv)+f(v):uv ∈ E(T)}
 is a consecutive integer set.






In Fig.<ref>, we have f^*_1(E(K_2,3))={f_1(u)+f_1(uv)+f_1(v):uv ∈ E(K_2,3)}=[6,8], f^*_2(E(K_2,4))={f_2(u)+f_2(uv)+f_2(v):uv ∈ E(K_2,4)}=[6,9] and f^*_3(E(K_3,3))={f_3(u)+f_3(uv)+f_3(v):uv ∈ E(K_3,3)}=[6,10], and furthermore the matching colorings h_1,h_2,h_3 distribute us

h^*_1(E(K_2,3))={h_1(u)+h_1(uv)+h_1(v):uv ∈ E(K_2,3)} =[7,9],

h^*_2(E(K_2,4))={h_2(u)+h_2(uv)+h_2(v):uv ∈ E(K_2,4)} =[9,12] and

h^*_3(E(K_3,3))={h_3(u)+h_3(uv)+h_3(v):uv ∈ E(K_3,3)} =[8,12].

It shows that each complete bipartite graph K_m,n admits a proper total coloring

    g:V(K_m,n)∪ E(K_m,n)→ [1,χ”(K_m,n)]
 such that

    g^*(E(K_m,n))={g(u)+g(uv)+g(v):uv ∈ E(K_m,n)}
 is a  consecutive integer set [a,b].







 §.§ New parameters on proper vertex colorings


We define two parameters on proper vertex colorings of graph theory in this subsection. Let f:V(G)→ [1,k] be a proper vertex coloring of a graph G with k=χ (G). We define a parameter

    B_sub(G,f)=∑ _xy∈ E(G)|f(x)-f(y)|,

and try to determine min_fB_sub(G,f) and max_fB_sub(G,f). Clearly, if G is a bipartite graph, then 
    min_fB_sub(G,f)=max_fB_sub(G,f)=|E(G)|.


If a connected graph G holds

    min_fB_sub(G,f)<M<max_fB_sub(G,f)

true for each M, there exists a proper vertex coloring f_M of G such that B_sub(G,f_M)=M, we say that G has a group of consecutive difference proper vertex colorings (see an example shown in Fig.<ref>).



Let g:V(G)→ [1,k] be a proper vertex coloring of a graph G with k=χ(G). We define another parameter 
    B_sum(G,g)=∑ _xy∈ E(G)[f(x)+f(y)]

and try to compute two extremal values min_gB_sum(G,g) and max_hB_sum(G,h). If G has a proper vertex coloring g_Q for each Q satisfying

    min_gB_sum(G,g)<Q<max_hB_sum(G,h)

such that B_sum(G,g_Q)=Q, we say that G has a group of consecutive sum proper vertex colorings. We give an example shown in Fig.<ref>.

Observed that the labeled graph (a) in Fig.<ref> is equal to the labeled graph (a) in Fig.<ref>, so we ask for a problem: If a proper vertex coloring h^* holds 
    B_sub(G,h^*)=min_fB_sub(G,f)
 true, then h^* holds 
    B_sum(G,h^*)=min_fB_sum(G,f)
 true too?




For making Topsnut-gpws and Topsnut-matchings more complex, we can use distinguishing edge-colorings and distinguishing total colorings, since they match with the following open problems:

(i) Zhang et al. <cit.> show a famous conjecture: For every graph G with no K_2 or C_5 component, then the adjacent strong edge chromatic number 
    χ'_as(G) ≤Δ(G)+2.


(ii) Zhang et al. <cit.> introduced a concept of adjacent vertex distinguishing total coloring (AVDTC), and show a conjecture: Let G be a simple graph with order n ≥  2; then G has its AVDTC chromatic number 
    χ”_as(G) ≤Δ(G)+2.


(iii) Yang et al. propose the following conjectures (<cit.>):  Every simple graph G having at least a 4-avdtc holds 
    χ”_4as(G) ≤Δ(G)+4.




 §.§ New proper total colorings


We use the successful experience of graph labelling definitions to propose new proper total colorings. Let f:V(G)∪ E(G)→ [1,k] be a proper total coloring of a graph G. If each edge uv holds f(uv)=|f(u)-f(v)| true, we call f a ve-matching difference total k-coloring of G, we denote the smallest number of k over all ve-matching difference total k-colorings by χ”_ved(G), called the ve-matching difference total chromatic number of G. See two ve-matching difference total colorings shown in Fig.<ref>(a) and (b). We can see χ”(G)≤χ”_ved(G), in general.


For a proper total coloring h:V(G)∪ E(G)→ [1,m], if each edge uv holds h(uv)=h(u)+h(v) true, we call h a ve-matching sum total m-coloring. The minimal number of m over all ve-matching sum total m-colorings is denoted as χ”_ves(G), called the ve-matching sum total chromatic number of G. Two ve-matching sum total colorings are shown in Fig.<ref>(c) and (d). Clearly, χ”(G)≤χ”_ves(G).



 
Suppose that H is a connected subgraph of a connected graph G, then

    χ”_ved(H)≤χ”_ved(G), χ”_ves(H)≤χ”_ves(G).











§ GRAPH LABELLING ANALYSIS


Analyzing a graph labelling in detail and depth is necessary and important, since graph labellings are applied to design graphical ciphers serving to information security. We hope that analysis of graph labellings will be helpful for applying graph labellings towards information networks, and become a new subbranch of graph theory.





 §.§ Pan-labellings


A pan-labelling is constituted of a topological structure and some operations based on numbers, letters, Topsnut-gpws, sets, groups etc. In general, a pan-labelling may be a traditional graph labelling/coloring of graph theory, or others introduced here. A coloring can be admitted by each simple graph, but a traditional labelling is admitted only by part of simple graphs.


For a (p,q)-graph G, a pan-labelling f is defined on a domain S⊆ V(G)∪ E(G), and yields the main-range f(S)={f(x):x∈ S}. Furthermore, f gives a mapping f' based on the edge-domain E(G) and produces the derivative range

    f'(E(G))={f'(uv)=F(f(u),f(v)):uv∈ E(G)}
 where F(f(u),f(v)) is a function of two variables. The main range or the derivative range is one of number sets, graph sets, group sets, Topsnut-sets, and so on.

Definition <ref> is one of generalized labelling definitions for connecting more well-defined graph labellings.


<cit.> Let G be a (p,q)-graph, and let A_M={a_i}_1^M and B_q={b_j}_1^q be two monotonic increasing sequences of numbers with M≥ p. There are the following restrict conditions:
[Seq-1. ]

  *  A vertex mapping f:V(G)→ A_M such that f(u)≠ f(v) for distinct vertices u,v∈ V(G).

  *  A total mapping g:V(G)∪ E(G) → A_M∪ B_q such that g(x)≠ g(y) for distinct elements x,y∈ V(G)∪ E(G).

  *  An induced edge label f(uv)=O(f(u),f(v)).

  *  An F-equation F(g(u),g(uv),g(v))=0 holds true.

  *  An E-equation E(f(u),f(uv),f(v))=0 holds true.

  *  f(E(G))⊆ B_q.

  *  g(V(G)∪ E(G))⊆ A_M∪ B_q.

  *  f(V(G))⊆ A_M and f(E(G))=B_q.

  *  f(V(G))=A_M and f(E(G))=B_q.

  We call f:
[(1) ]

  * a sequence-(A_M,B_q) labelling if Seq-<ref> and Seq-<ref> hold true;


  * a sequence-(A_M,B_q) total labelling if Seq-<ref>, Seq-<ref> and Seq-<ref> hold true;


  * a full sequence-(A_M,B_q) labelling if Seq-<ref>, Seq-<ref> and Seq-<ref> hold true;


  * a graceful sequence-(A_M,B_q) labelling if Seq-<ref>, Seq-<ref> and Seq-<ref> hold true;


  * a total sequence-(A_M,B_q) labelling if Seq-<ref> and Seq-<ref> hold true;


  * a sequence-(A_M,B_q) F-total graceful labelling if Seq-<ref>, Seq-<ref> and Seq-<ref> hold true;


  * a sequence-(A_M,B_q)  mixed labelling if Seq-<ref>, Seq-<ref> and Seq-<ref> hold true.



If two sets A_M={a_i}_1^M and B_q={b_j}_1^q defined in Definition <ref> correspond a graph labelling admitted by graphs, we say (A_M, B_q) a graph-realized sequence matching.



 §.§ Topsnut-matchings labeled by graphs


Let {G_i}^m_1 be a set of disjoint graphs G_1,G_2,… ,G_m, where G_k admits a labelling g_k with k∈ [1,m], and let  a (p,q)-graph H be a base.

∗ Addition and subtraction. Define a mapping f:V(H)→{G_i}^m_1, and an induced edge label f'(uv)=F(G_i,G_j) for each edge uv∈ E(H), where f(u)=G_i and f(v)=G_j. Hereafter, “joining G_i with G_j” is defined as an operation of “joining a vertex of a graph G_i with some vertex of another graph G_j by an edge”.
[Gr-1. ]

  * If f'(E(H))={|i-j|:uv∈ E(H)}=[1,q], we call H(f,f') a graceful graph-set labelling (graceful gs-labelling). And, we have a graceful gs-compound G=⟨{G_i}^m_1;H(f,f')⟩ obtained by joining G_i=f(u) with G_j=f(v) for each edge uv∈ E(H). In general, the number of such graphs G=⟨{G_i}^m_1;H(f,f')⟩ is not one.

  * If f'(E(H))={|i-j|:uv∈ E(H)}=[1,2q-1]^o, then H(f,f') is called an odd-graceful graph-set labelling (odd-graceful gs-labelling), and we have an odd-graceful gs-compound G=⟨{G_i}^m_1;H(f,f')⟩.

  * If f'(E(H))={i+j ( q):uv∈ E(H)}=[0,q-1], we have a felicitous graph-set labelling (felicitous gs-labelling) H(f,f'), and a felicitous gs-compound G=⟨{G_i}^m_1;H(f,f')⟩.

  * If f'(E(H))={i+j ( 2q-1):uv∈ E(H)}=[0,2q-3]^o, we have an odd-elegant graph-set labelling (felicitous gs-labelling) H(f,f'), and an odd-elegant gs-compound G=⟨{G_i}^m_1;H(f,f')⟩.


∗ Magic type. Define a mapping f:V(H)∪ E(H)→{G_i}^m_1, such that f(u)=G_i, f(v)=G_j and f(uv)=G_k for each edge uv∈ E(H).
[Mg-1. ]

  * If there exists a constant k^*, such that 
    i+k+j=k^*
 for each edge uv∈ E(H), we call f an edge-magic total graph-set labelling (edge-magic total gs-labelling), the graph G=⟨{G_i}^m_1;H(f)⟩ is obtained by joining G_i with G_k and joining G_k with G_j for each edge uv∈ E(H) is called an edge-magic total gs-compound.

  * If there exists a constant k^* such that |i-k+j|=k^* for each edge uv∈ E(H), we call f an edge-magic total graceful graph-set labelling (edge-magic total graceful gs-labelling), the graph G=⟨{G_i}^m_1;H(f)⟩ is obtained by joining G_i with G_k and joining G_k with G_j for each edge uv∈ E(H) is called an edge-magic total graceful gs-compound.

  * If there exists a constant k^* such that k+|i-j|=k^* for each edge uv∈ E(H), we call f an edge-magic graceful total graph-set labelling (edge-magic graceful total gs-labelling), the graph G=⟨{G_i}^m_1;H(f)⟩ is obtained by joining G_i with G_k and joining G_k with G_j for each edge uv∈ E(H) is called an edge-magic graceful total gs-compound.


∗ (k,d) type. It is not difficult to imitate those well-defined graph labellings having parameters, so it is interesting to mention them as exercise.



 §.§ Topsnut-matchings produced by graph operations

[Op-1. ]

  * Odd-graceful/odd-elegant graph matching. Let S_og(p) be a set of odd-graceful/odd-elegant graphs of m vertices. A (p,q)-graph G admits a graph labelling f:V(G)→ S_og(p) such that each edge uv∈ E(G) labeled as f(uv)=⊙⟨ f(u),f(v)⟩ is just a twin odd-graceful/odd-elegant graph of k_uv vertices, where (f(u),f(v)) is just an odd-graceful/odd-elegant Topsnut-matching. If {k_uv:uv ∈ E(G)}=[a,b], we say the graph ⟨ G⊙ S_og(p)⟩ obtained by joining f(u) with f(uv) and joining f(uv) with f(v) for each edge uv∈ E(G) an [a,b]-twin odd-graceful/odd-elegant graph.


  * Euler graph matching. Let E_g be a set of non-eulerian graphs. A (p,q)-graph G admits a graph labelling f:V(G)→ E_g, and induced edge label f(uv)=⊙⟨ f(u),f(v)⟩ is just an Euler graph of k_uv vertices, we call (f(u),f(v)) an Euler Topsnut-matching. The graph ⟨ G⊙ E_g⟩ obtained by joining f(u) with f(uv) and joining f(uv) with f(v) for each edge uv∈ E(G) an [a,b]-Euler graph, where {k_uv:uv ∈ E(G)}=[a,b].


  * Hamilton graph matching. Let H_ag be a set of graphs. A (p,q)-graph G admits a graph labelling f:V(G)→ H_ag, and induced edge label f(uv)=⊙⟨ f(u),f(v)⟩ is just a Hamilton graph of k_uv vertices, we call (f(u),f(v)) a Hamilton Topsnut-matching. The graph ⟨ G⊙ E_ag⟩ obtained by joining f(u) with f(uv) and joining f(uv) with f(v) for each edge uv∈ E(G) is an [a,b]-Hamilton graph, where {k_uv:uv ∈ E(G)}=[a,b].

  * Pan-matching with operation (∙). Let P_ag be a set of graphs. A (p,q)-graph G admits a graph labelling F:V(G)→ H_ag, and induced edge label F(uv)=F(u)(∙)F(v) is just a graph having a P-matching, where (∙) is an operation. Here, a P-matching may be: a perfect matching of k_uv vertices, k_uv-cycle, k_uv-connected, k_uv-edge-connected, k_uv-colorable, edge k_uv-colorable, total k_uv-colorable, k_uv-regular, k_uv-girth, k_uv-maximum degree, k_uv-clique, {a;b}_uv-factor, a maximal planar graph of k_uv vertices, and so on. We call the graph ⟨ G(∙) P_ag⟩ obtained by joining F(u) with F(uv) and joining F(uv) with F(v) for each edge uv∈ E(G) a P-matching {k_uv}-graph.


An {a;b}-factor is a spanning subgraph H of a graph G such that each vertex x of H has one of degree a and degree b. Let F:V(G)→ H_ag, where P_ag is a set of graphs, and let F(uv)=⊙⟨ F(u),F(v)⟩ be a graph having an {a;b}-factor for each edge uv∈ E(G) (see Fig.<ref>).








In Fig.<ref> and Fig.<ref>, a tree T admits a graph labelling F:V(T)→ F(G), where F(x_i)=G_i with i∈ [1,7], and F(x_ix_j)=F(x_i)∩ F(x_j)=G_i∩ G_j=H_ij. The graph H shown in Fig.<ref> is one of the collection T^* of graph-labelling graphs, since there are many ways to join two graphs by an edge. Here, H_13=K_1+K_2 is a {2;1}-factor, H_23=K_2+K_2 is a {2;2}-factor, H_34=K_2+K_2 is a {2;3}-factor, H_45=K_2+K_3 is a {2;4}-factor, H_46=K_2+K_4 is a {2;5}-factor, and H_47=K_2+K_5 is a {2;6}-factor. So, The edges of the graph H form a  graceful sequence of {2;k}-factors with k∈ [1,6].

 
Each caterpillar with q edges admits an {a;b}-factor graph labelling, where {a;b} is a non-decreasing sequence-pair {a^*_i; b^*_i}^q_1.

 A caterpillar T shown in Fig.<ref> contains a path P=u_1u_2⋯ u_n, and each set of leaves v_i,j adjacent to a vertex u_i is denoted as L(u_i)={v_i,j:j∈ [1,m_i]} with m_i≥ 0 and i∈ [1,n]. We take a non-decreasing sequence-pair {a_i,j} and {b_i,j} for j∈ [1,m_i] and i∈ [1,n]. Each complete bipartite graph K_a_i,j,b_i,j is written as K(a_i,j,b_i,j) for convenient statement. We define a graph labelling F on T as follows:

For i:=1, we set

    F(u_1)=K(c_1,2+A(m_1),d_1,2+B(m_1))
 with A(m_1)=∑^m_1_j=1a_1,j and B(m_1)=∑^m_1_j=1b_1,j, and set F(v_1,j)=K(a_1,j,b_1,j) and F(u_1v_1,j)=F(u_1)∩ F(v_1,j) with j∈ [1,m_1].

For i:=i+1, we set

    F(u_i+1)=   K (∑^i+1_k=1A(m_k)+∑ ^i_k=1c_k,k+1,
       ∑^i+1_k=1B(m_k)+∑ ^i_k=1d_k,k+1  )

with A(m_k)=∑^m_k_j=1a_k,j and B(m_k)=∑^m_k_j=1b_k,j, and set F(v_i+1,j)=K(a_i+1,j,b_i+1,j) and F(u_1v_i+1,j)=F(u_i+1)∩ F(v_i+1,j) with j∈ [1,m_i+1].

At the last, we let

    F(u_n)=   K (1+∑^n_k=1A(m_k)+∑ ^n-1_k=1c_k,k+1,
       ∑^n_k=1B(m_k)+∑ ^n-1_k=1d_k,k+1 )
 and set F(v_n,j)=K(a_n,j,b_n,j) and F(u_nv_n,j)=F(u_n)∩ F(v_n,j) with j∈ [1,m_n].

Let α(r)=∑^r_k=1m_k. We write a^*_j=a_1,j and b^*_1,j=b_1,j with j∈ [1,m_1]; c_12=a^*_1+α(1) and d_12=b^*_1+α(1); a^*_1+α(1)+j=a_2,j and b^*_1+α(1)+j=b_2,j with j∈ [1,m_2]; c_2,3=a^*_2+α(2) and d_2,3=b^*_2+α(2); ⋯; c_n-1,n=a^*_n-1+α(n-1) and d_n-1,n=b^*_n-1+α(n-1); a^*_n-1+α(n-1)+j=a_n,j and b^*_n-1+α(n-1)+j=b_n,j with j∈ [1,m_n]. Furthermore, we let a^*_k≤ a^*_k+1 and b^*_k≤ b^*_k+1 with k∈ [1, n-1+α(n)].

Thereby, we have shown the result of the theorem.


We give the values of {a^*_i}^q_1 and {b^*_i}^q_1 in Theorem <ref> in the following:

(i) {a^*_i}^q_1={a} and {b^*_i}^q_1=[1,q], so each caterpillar with q edges admits a graceful {a;b}-factor graph labelling;

(ii) {a^*_i}^q_1={a} and {b^*_i}^q_1=[1,2q-1]^o, then every caterpillar with q edges admits an odd-graceful {a;b}-factor graph labelling;

(iii) {a^*_i}^q_1=[1,q] and {b^*_i}^q_1=[1,q], then each caterpillar with q edges admits an bi-graceful {a;b}-factor graph labelling;

(iv) {a^*_i}^q_1=[1,2q-1]^o and {b^*_i}^q_1=[1,2q-1]^o, then each caterpillar with q edges admits an bi-odd-graceful {a;b}-factor graph labelling.

Notice that there are many graphs containing {a;b}-factors, in general. We can take well-known sequences (such as Fibonacci sequence, arithmetic progression, geometric progression, etc.) to replace {a^*_i}^q_1 and {b^*_i}^q_1 for getting more  interesting Topsnut-gpws. Moreover, it is not difficult to prove: Each lobster with q edges admits an {a;b}-factor graph labelling, where {a,b} is some non-decreasing sequence-pair {a^*_i; b^*_i}^q_1.





 §.§ Properties of Labellings


The previous subsections show the labellings with the following properties. Other properties of labellings can be found in <cit.>. Let k be a constant, and let G be a (p,q)-graph admitting a labelling f. We have:
[C-1. ]

  * (e-magic-graceful) Each edge uv matches with another edge xy such that f(uv)+|f(x)-f(y)|=k.

  * (e-magic) Each edge uv matches with another edge xy such that f(x)+f(uv)+f(y)=k.

  * (ee-graceful) Each edge uv matches with another edge xy holding |f(x)+f(y)-f(uv)|=k true.

  * (ee-difference) Each edge uv matches with another edge xy holding f(uv)=|f(x)-f(y)| true, or f(uv)=M-|f(x)-f(y)|.

  * (ee-sum) Each edge uv matches with another edge xy holding f(uv)=f(x)+f(y) ( B) true,  such that the resulting edge labels are distinct and nonzero.

  * (ep-matching) Each matching edge uv∈ M holds f(u)+f(v)=k true, where M is a perfect matching of G, and k is some constant.

  * (ee-bandwiden) Each edge uv matches with another edge u'v' holding s(uv)+s(u'v')=0 true, where s(xy)=|f(x)-f(y)|-f(xy).

  * (ve-matching) Each edge uv matches with one vertex w such that f(uv)+f(w)=k', and vice versa, except the singularity.

  * (EV-ordered) There two orders:

  (i) f_max(V(G))<f_min(E(G)), or f_min(V(G))>f_max(E(G));

  (ii) f(V(G))⊆ f(E(G)), f(E(G))⊆ f(V(G)).


  * (set-ordered) f_max(X)<f_min(Y), or f_min(X)>f_max(Y) if G is bipartite with its partition (X,Y) of V(G).

  * (reciprocal-inverse) h(V(G)∪ E(G))=[1, p+q],

    h(V(G))∖{a_0}=f(E(G)), h(E(G))=f(V(G))∖{a_0}
 where a_0=⌊ (p+q+1)/2⌋ is the singularity of two labellings f and h.

  * (odd-even separable) f(V(G)∪ E(G))=[1, p+q], and f(V(G)) is an odd-set containing only odd numbers, as well as f(E(G)) is an even-set containing only even numbers.






 §.§ Some indices for analyzing graph labellings


We design parameters for theoretically metricizing Topsnut-gpws, such as:
[Deg-1. ]

  * Difficulty. A labelling f holds m conditions, we say f to be m-rank difficulty.

  * Complexity. A labelling f holds m conditions, each condition has a complex rank, summarizing them together forms the whole complex rank.

  * Constructibility and non-constructibility. It includes configuration construction (with no polynomial algorithm in general) and structural construction  (with polynomial algorithm), constructive labelling. Conversely, it includes non-structural construction, non-constructive labelling.

  * Computationally unbreakable. Consider giant spaces, no-constructive algorithms, non-mathematical interventions (physics, chemistry, biology, music, national language).

  * Matching. Twin odd-graceful labelling, reciprocal-inverse labellings, other matchings mentioned here, and so on.

  * Combinatorics. Twin type of labellings, such as twin odd-graceful and twin  odd-elegant labellings. Various combinatorics induce many labellings, such as 6C-labellings.

  * Closure to property and configuration. Labellings are closed to particular graphs, or graph properties, or labelling properties, and so on.

  * Connections with others. There are: (i) canonical mathematical operations, such as addition, subtraction, multiplication and division; (ii) graph operations, such as union, intersection, split, subdivision, and so on; (iii) advanced algebraic operations, such as group, ring and field; (iv) text-based passwords; (v) between labellings, such as equivalence, transformation etc.

  * Compound. Graphs are labeled by Topsnut-gpws and graphic groups etc.

  * Transformation. For example, f is set-ordered on (X,Y), so we have an affine transformation g defined by g(x)=af(x)+b for x∈ X, g(y)=cf(y)+d for y∈ Y.

  * Generalization and diversity. What is a hyperlabelling? What is a network labelling? What is an random labelling? What is a functional (chemistry, physical, biological) labelling?





§ ALGEBRAIC GROUP/SET MATCHING PARTITIONS


Many problems of Topsnut-gpws can be transformed into algebraic problems, such as set problems and algebraic group problems, etc. However, the research of algebraic group/set problems differs greatly from that of Topsnut-gpws. On the other hands, investigating the problems proposed in this subsection does not need knowledge of graph theory, only basic mathematical knowledge.





 §.§ Set matching partitions



Set matching partition is a natural phenomenon in mathematics, such as an integer set [1,10] contains two subsets [1,10]^o={1,3,5,7,9} and [1,10]^e={2,4,6,8,10}. Clearly, [1,10]^o∪ [1,10]^e=[1,10], we say [1,10]^o and [1,10]^e are matching to each other, they are a set matching partition of [1,10]. Many graph labellings are related with set problems. For two integers p≥ 2 and q≥ 1, the previous labelling definitions enable us to obtain the following set problems:

[Set-1. ]

  * From Definition <ref>: Partition [1, p+q] into two disjoint subsets V and E with V∪ E=[1, p+q] such that: (i) each c∈ E corresponds to distinct a,b∈ V holding c=|a-b| true; (ii) there exists a constant k, each c'∈ E matches with distinc a',b'∈ V holding a'+c'+b'=k true. We call (V,E) a relaxed edge-magic total matching partition of [1, p+q].

    ∗ Find all possible relaxed edge-magic total matching partitions (V,E) of [1, p+q].


  * From Definition <ref>: Select two subsets V,E⊂ [1,2q-1] with E=[1,2p-1]^o such that there is a constant k, each c∈ E corresponds two distinct a,b∈ V holding a+b+c=k true. We call (V,E) an odd-edge-magic matching partition of [1,2q-1].

     ∗ Find all possible odd-edge-magic matching partitions of [1,2q-1].



  * From Definition <ref>: Selecting two subsets V,E⊂ [1,2q-1] with E=[1,2p-1]^o holds true: (i) each c∈ E corresponds a,b∈ V to form an ev-matching (acb); (ii) each c∈ E corresponds to z∈ E with the ev-matching (xzy) such that c=|x-y|; (iii) each c∈ E with the ev-matching (acb) corresponds to c'∈ E with the ev-matching (a'c'b') such that 
    (|a-b|-c)+(|a'-b'|-c')=0.
 We call (V,E) an ee-difference odd-edge-magic matching partition of [1,2q-1].

     ∗ Find all possible ee-difference odd-edge-magic matching partitions (V,E) of [1,2q-1]. Here, each ev-matching (acb) corresponds an edge c of a graph, where the edge c has two ends a,b.



  * From Definition <ref>: Partition [1,p+q] into two subsets V,E satisfies: (i) each c∈ E corresponds a,b∈ V to form an ev-matching (acb); (ii) (e-magic) each c∈ E with the ev-matching (acb) hold c+|a-b|=k true; (iii) (ee-difference) each c∈ E corresponds to z∈ E with the ev-matching (xzy) such that c=|x-y|; (iv) (ee-bandwiden) each c∈ E with the ev-matching (acb) corresponds to c'∈ E with the ev-matching (a'c'b') such that (|a-b|-c)+(|a'-b'|-c')=0; (iv) (EV-ordered) max V<min E (or max V>min E); (v) (ve-matching) each ev-matching (acb) matches with another ev-matching (uwv) such that a+w=k' or b+w=k', k' is a constant, except the singularity ⌊p+q+1/2⌋. We call (V,E) a 6C-partition of [1,p+q].

     For a given 6C-partition (V,E) of [1,p+q], if there exists another 6C-partition (V',E') of [1,p+q] such that 
    V∖ (V∩ V')=E', E=V'∖ (V∩ V')
 for V∩ V'={⌊p+q+1/2⌋}, we get a partition (V∪ E', E∪ V), and call it a 6C-complementary matching partition of [1,p+q].


     ∗ Find all possible 6C-partitions (V,E) of [1,p+q], and all possible 6C-complementary matching partitions (V∪ E', E∪ V).



  * From Definition <ref>: Partition [0,p+q-1] into two subsets V,E with E=[1,q] and V⊆ [0,q-1] satisfies: (i) each c∈ E corresponds a,b∈ V to form an ev-matching (acb); (ii) (ee-difference) each c∈ E corresponds to z∈ E with the ev-matching (xzy) such that c=|x-y|; (iii) (ee-bandwiden) each c∈ E with the ev-matching (acb) corresponds to c'∈ E with the ev-matching (a'c'b') such that (|a-b|-c)+(|a'-b'|-c')=|a-b|+|a'-b'|-(c+c')=0; (iv) there exists a constant k such that each c∈ E with its ev-matching (acb) holds c+|a-b|=k true; (v) each c∈ E corresponds another c'∈ E with its ev-matching (a'c'b') such that c+a'=p or c+b'=p. We call (V,E) an ee-difference graceful-magic matching partition of [0,p+q-1].


     ∗ Find all possible ee-difference graceful-magic matching partitions of [0,p+q-1].


  * From Definition <ref>: Partition [1, p+q] into two disjoint subsets V and E with V∪ E=[1, p+q] such that each c∈ E corresponds to distinct a,b∈ V holding c=|a-b| true, and there exists a constant k satisfying a+c+b=k for each c∈ E which corresponds to distinct a,b∈ V. We call (V,E) an edge-magic graceful matching partition of [1, p+q]. If (E, V) is another edge-magic graceful matching partition of [1, p+q], we say (V,E) (resp. (E, V)) to be a ve-exchanged matching partition of [1, p+q].

     ∗ Find all possible edge-magic graceful matching partitions of [1, p+q], and all possible ve-exchanged matching partitions.

  * If there are two sets V⊆ [0,q]^2 (or [0,2q-1]^2) and E⊆ [1,q] (or [1,2q-1]) such that each c∈ E with its ev-matching (acb) holds c=|a-b| true, where a∈ A∈ V and b∈ B∈ V with A∩ B=∅, then we call (V,E) a v-set e-proper graceful (or odd-graceful) matching partition.


  * From the twin odd-graceful/odd-elegant labellings: Partition [0,2q] into two subsets S_1,S_2 such that S_1⊂ [0,2q-1], S_2⊂ [1,2q], |S_1∩ S_2|=1 and S_1∪ S_2=[0,2q]. For E_1=E_2=[1,2q-1]^o, each c_i∈ E_i corresponds two numbers a_i,b_i∈ S_i holding c_i=|a_i-b_i| true (or c_i=a_i+b_i ( 2q)) with i=1,2. We call (S_1,S_2) a twin odd-graceful (or odd-elegant) matching partition of [0,2q].

     ∗ Characterize twin odd-graceful (or odd-elegant) matching partitions, and find them.


  * From Definitions <ref> and <ref>: Select a subset E⊂ [0,p-1] such that each c∈ E corresponds two distinct a,b∈ V=[0,p-1] to hold c=|a-b| true (or c=a+b ( |E|)), we call f_E=(V,E) a graph matching partition, and call S_um(G,f_E)=∑_c∈ E|a-b| a difference-sum number (or F_um(G,f_E)=∑_c∈ E(a+b) ( |E|) is a felicitous-sum number).


     ∗ Determine max_f_E S_um(G,f_E) (profit) and min_f_E S_um(G,f_E) (cost) over all difference-sum matching partitions f_E=(V,E) of [0,p-1]. Find max_f_E F_um(G,f_E) and min_f_E F_um(G,f_E) over all felicitous-sum matching partitions f_E=(V,E) of [0,p-1].





It may be interesting to consider such algebraic groups on the above set partition problems.





 §.§ Matching partitions of algebraic matrices


We introduce an algebraic expression of a Topsnut-gpw G being a (p,q)-graph as follows:

A Topsnut-matrix A_vev(G) of  a Topsnut-gpw G being a (p,q)-graph is defined as

    A_vev(G)= (
    [ x_1 x_2   ⋯ x_q; e_1 e_2   ⋯ e_q; y_1 y_2   ⋯ y_q ])=(X W Y)^T


where

    X=(x_1   x_2  ⋯ x_q), W=(e_1   e_2  ⋯ e_q)
       Y=(y_1   y_2  ⋯  y_q),

and G has another Topsnut-matrix A_vv(G) defined as A_vv(G)=(X,Y)^T, where X,Y are called vertex-vectors, W is called edge-vector, such that e_i=x_iy_i is an edge of G for i∈ [1,q].



So, A_vev(G) is a Topsnut-matrix, and A_vv(G) is a Topsnut-matrix. Clearly, such Topsnut-matrices are easily saved in computer, and produce quickly text-based passwords. For example, we have the following four Topsnut-matrices A_1,A_2,B_1 and B_2 from Fig.<ref> to Fig.<ref>:









We point out: (i) A Topsnut-matrix A_vev(G) is not unique for expressing a Topsnut-gpw G, in other words, a Topsnut-gpw G many have two or more Topsnut-matrices; (ii) Topsnut-matrices differ from popular algebraic matrices, since Topsnut-matrices are only the expression of labelled vertices joined by labelled edges. Clearly, we need some new algebraic operations on Topsnut-matrices.

Let D(A) be the matrix of a perfect Max-min difference-sum matching partition A=⊙_12⟨ G_a,G_d⟩ shown in Fig.<ref>. So, D(A) is a Topsnut-matrix, denoted directly as D(A)=⊙_12⟨ A_1,A_2⟩ (see Fig.<ref> and Fig.<ref>), called a matrix matching partition. Similarly, the matrix D(B) of the perfect Max-min felicitous-sum matching partition B=⊙_9⟨ F_b,F_c⟩ shown in Fig.<ref> is a Topsnut-matrix, and we have another matrix matching partition D(B)=⊙_8⟨ B_1,B_2⟩ (see Fig.<ref> and Fig.<ref>).

Along the orange line in the matrix B_1, we can get a text-based password

    T_ext(B_1)=077088066033473385561572
 and another text-based password

    T_ext(B_2)=731734825701611001143323
 obtained along the orange line in the matrix B_2. Obviously, it is not easy to reconstruct the perfect Max-min felicitous-sum matching partition B shown in Fig.<ref> from T_ext(B_1) and T_ext(B_2), even it is impossible if Topsnut-gpws with large numbers of vertices and edges.

By the vertex-split and vertex-identifying operations, as well as the edge-split and edge-identifying operations, we can define algebraic operations on Topsnut-matrices of (p,q)-graphs that are topological structures of Topsnut-gpws, such as D(A)=⊙_12⟨ A_1,A_2⟩ and D(B)=⊙_8⟨ B_1,B_2⟩ obtained by the vertex-identifying operation of (3× q)-matrices.



 §.§ Topsnut-matchings made by graphic groups


Let T^odd_group be a set of odd-graceful Topsnut-groups. We define a labelling f:V(G)→ T^odd_group for a (p,q)-graph G, and set f(uv)=⊙⟨ f(u),f(v)⟩ to be a matching of two odd-graceful Topsnut-groups G^odd_i and G^odd_j, here, each T_i∈ G^odd_i matches with T_j∈ G^odd_j such that ⊙⟨ T_i,T_j⟩ is just an odd-graceful Topsnut-matching, and vice versa.

For encrypting a network by graphic groups we show a simple example in Fig.<ref>, Fig.<ref> and Fig.<ref>. We have an operation defined by

    [f_i(x)+f_j(x)-f_k(x)] ( 13)=f_λ(x)

for each element x∈ V(G)∪ E(G) shown in Fig.<ref>, where λ=i+j-k ( 13), and call (<ref>) “additive operation”. We can see that there are many ways to realize a network encrypted by a graphic group, since there are two or more ways to join G_i with G_j by an edge (allow by two or more edges). Thereby, we have obtained many encrypted networks.









 §.§ Algebraic groups from Topsnut-gpws, Topsnut-matrices and text-based passwords



We have known that a Topsnut-gpw G has its Topsnut-matrix A(G) which induces a text-based password D(G). So this  Topsnut-gpw G and its Topsnut-matrix A(G), as well as the text-based password D(G) can produce three Abelian additive groups by the additive operation shown in (<ref>), we call them Topsnut-group, Topsnut-matrix group and Text-pw group, respectively. If a Topsnut-gpw G matches with another Topsnut-gpw H, so two Topsnut-groups induced by G and H match with each other. More results on such groups can be found in <cit.> and <cit.>.









§ RESEARCHING PROBLEMS


For further researching Topsnut-matchings we propose the following problems:
[Pro-1. ]

  * (A complete graph obtained from labeled trees) Given disjoint trees T_1,T_2, …, T_m with

    ∑^m_i=1|E(T_i)|≥1/2n(n-1).
 Can we find a labelling f_i for each tree T_i such that f_i:V(T_i)→ [0,n-1] and 
    {|f_i(u)-f_i(v)|:uv∈ E(T_i)}=[1,|E(T_i)|],
 and identify the vertices of ⋃^m_i=1V(T_i) having the same labels into one, the resulting graph is just K_n=⊙⟨ T_i⟩^m_1, or K_n=⊖(T_i)^m_1, or K_n=⋃^m_i=1 T_i?


  * For any odd-graceful graph H of p vertices, does there exists a pan-odd-graceful Topsnut-matching team ⊙_1⟨ H,T_i⟩ ^p_1? Or consider this H as a lobster first. Find conditions for the perfect odd-gracefully Topsnut-matching team ⊙_1⟨ H,T_i⟩ ^p_1 with T_i≅ T_j for i≠ j. Find nontree graphs which induce pan-odd-graceful Topsnut-matching teams.


  * Plant the concept of pan-odd-graceful Topsnut-matching team ⊙_1⟨ H,T_i⟩^p_1 on other graph labellings.


  * For a given lobster T, find another lobster T' such that ⊙⟨ T,T'⟩ admits a twin odd-graceful labelling (or a twin odd-elegant labelling) (<cit.>).


  * For a given (p,q)-tree G admitting a 6C-labelling f, find all possible (p,q)-tree H admits a 6C-labelling g such that ⊙⟨ G,H ⟩ are 6C-complementary matchings.

  * Find conditions for a connected graph G to be a multiple-tree matching partition G=⊕_F⟨ T_i⟩ ^m_1 with m≥ 2.

  * Find all possible odd-graceful Topsnut-matchings ⊙⟨ G,H ⟩ for a given (p,q)-graph G admitting odd-graceful labellings.

  * Determine v-set e-proper graceful/odd-graceful labellings of Euler graphs.


  * Determine the conditions for A_M and B_q and any a∈ A_M corresponds two numbers a^*∈ A_M b^*∈ B_q such that b^*=|a-a^*|. Then determine such sequence pair (A_M,B_q) defined in Definition <ref> such that the sequence type of labellings defined in Definition <ref> hold true on graphs. Clearly, if any b∈ B_q corresponds two  numbers a',a”∈ A_M such that b=|a'-a”|, then there exists at least a forest T admitting a graceful sequence-(A_M,B_q) labelling defined in Definition <ref>.


  * Find connected graphs G such that for any integer M holding

    min_f S_um(G,f)<M<max_f S_um(G,f)
 true, then there exists a difference-sum labelling h of G with M=S_um(G,h).


  * Find connected graphs G such that for any integer M holding

    min_f F_um(G,f)<M<max_f F_um(G,f)
 true, then there exists a felicitous-sum labelling h of G with M=F_um(G,h).


  * For particular graphs G, compute the exact values of min_f S_um(G,f) and max_f S_um(G,f).


  * For a given graph G, find all graphs H for forming set-ordered matching graphs G⊖ H with H≇G.


  * For an odd-graceful graph G, find all matching graphs H such that ⊙⟨ G,H⟩ admitting twin odd-graceful labellings.


  * Consider other v-set e-proper ε-labellings of a complete graph K_n, where ε∈{edge-magic total labelling, odd-elegant labelling, harmonious labelling, the labellings defined in this paper}. For example:

   (i) A v-set e-proper felicitous labelling (F,f) of a (p,q)-graph G is defined as: F:V(G)→ [0,q-1]^2 with F(x)∩ F(y)=∅ for distinct x,y∈ V(G), and f:E(G)→ [0,q-1] holding f(E(G))=[0,q-1] and f(uv)=a_u+a_v ( q) true with a_u∈ F(u) and a_v(v)∈ F(v).

   Does K_n admits a v-set e-proper felicitous labelling?

   (ii) A v-set e-proper edge-magic total labelling (F,f) of a (p,q)-graph G is defined by F:V(G)→ [1,M]^2 with p+q≤ M and F(x)∩ F(y)=∅ for distinct x,y∈ V(G), and f:E(G)→ [1,M] with f(uv)≠ f(xy) for any two edges uv,xy∈ E(G), and there exists a constant k such that 
    a_u+f(uv)+a_v=k
 for any edge uv∈ E(G) with a_u∈ F(u) and a_v∈ F(v).

   Does K_n admits a v-set e-proper edge-magic total labelling? Find the parameter E_mt(G)=min_(F,f){M} over all v-set e-proper edge-magic total labellings of G.


  * If we can split a connected graph admitting a v-set e-proper graceful labelling into a tree, then characterize this graph and its possible v-set e-proper graceful labellings.

  * Find conditions for a connected graph G that can be split into caterpillars, or lobsters, such that G admits a v-set e-proper X-labelling, where X  is a graph labelling admitted by caterpillars, or lobsters (see Theorem <ref>).


  * For each p≥ 2, find a (p,q)-graph G=⊙_f⟨ G_i⟩ ^m_1 defined in definition <ref>, such that q is the largest edge number on such (p,q)-graphs when p is fixed. We can add other restrictions: (i) each G_i is a spanning subgraph of G; (ii) E(G_i)∩ E(G_j)=E^*⊂ E(G) for i≠ j and E^*≠∅; (iii) each G_i is a tree, or an Euler graph, or a bipartite graph, and so on.


  * A (p,q)-graph G and a (q,p)-graph H admit two edge-magic graceful labellings f and g, respectively, and f and g are reciprocal inverse because f(E(G))=g(V(H))∖ X^* and f(V(G))∖ X^*=g(E(H)) for X^*=f(V(G))∩ g(V(H)). Find such pairs of graphs G and H, and characterize them.

  * Find reciprocal complementary (reciprocal-inverse matching) G=⊙⟨ T,G⟩ for a fixed graph T, where T and G admit reciprocal-inverse labellings f and g, respectively, such that 
    f(E(T))=g(V(G))∖ X^* and f(V(T))∖ X^*=g(E(G))
 for X^*=f(V(T))∩ g(V(G)).

  * If a total coloring g of a graph G arrives at B_tol(G,g)=min_fB_tol(G,f), is there χ”(G)=|{g(x):x∈ V(G)∪ E(G)}|?

  * For any connected subgraph H of a connected graph G, does there exists max_g S_um(H,g)≤max_f S_um(G,f)?

  * Determine connected graphs having a group of consecutive difference proper vertex colorings, or a group of consecutive sum proper vertex colorings.

  * Find connected graphs admitting one of the edge-magic proper total coloring and the equitably proper total coloring.

  * It is not difficult to verify χ”_ved(K_n)≤ 2n and χ”_ves(K_n)≤ 2n-1. Does any tree T hold 
    χ”_ved(T)≤Δ(T)+4
 and 
    χ”_ves(T)≤ 2Δ(T)+1
 true?

  * Let f: V(G)∪ E(G)→ [1,χ”(G)] be a proper total coloring of a graph G, and let 
    f^*(E(G))={f(u)+f(uv)+f(v):uv ∈ E(G)}.
 Characterize G if f^*(E(G)) is a consecutive integer set [a,b].

  * In <cit.>, the authors defined: “Let η-labeling be a given graph labelling, and let a connected graph G admit an η-labeling. If every connected proper subgraph of G also admits a labelling like  η-labeling, then we call G a perfect η-labeling graph.” Caterpillars are perfect η-labeling graphs if these η-labelings are listed in this article, and each lobster is a perfect (odd-)graceful labeling graph. They ask for: If every connected proper subgraph of a connected graph G admits an η-labelling, then does G admits this η-labelling too? Clearly, a perfect η-labeling graph (like an elder generation) can be used to produce a crowd of Topsnut-GPWs (like son generations).









§ CONCLUSION


We have known that Topsnut-matching is a larger topic in researching Topsnut-gpws, nature-inspired passwords. Results and techniques of graph theory are proven to be powerful in designing and researching Topsnut-gpws, since there are no polynomial algorithms for many of these results and techniques. Many of the graph labellings introduced here match with mathematical conjectures, so they may provide computationally unbreakable for our Topsnut-gpws. It is hopeful to let more people use Topsnut-gpws and pan-Topsnut-gpws (allow label vertices and edges with non-mathematical elements) for protecting their information and profits in networks ( <cit.>, <cit.>). There are over 200 graph labellings introduced in <cit.>, and more new graph labellings emerge everyday. It is time to consider Graph Labelling Analysis as a subbranch of graph theory. So, we try doing some exploring work here, although we have two hands empty on this topic.

Matching can help us to design Topsnut-gpws for one public key vs one private key, one public key vs two or more private keys, and more public keys vs more private keys. Matching opens a window for us to understand something new in cryptography. It is very important that matching is just one of mathematical principles. Almost mathematical operations have their own matching operations. The graph labellings first defined or introduced here match with other existing graph labelllings, and can be shown to be related with mathematical conjectures, or open problems.

Researching Topsnut-matching can derive two interesting topics: one is set matching partition to number theory, and another is about labeled graphs for constructing large scale of graphs with labellings, which differs from finding labellings to unlabeled graphs. We have listed possible researching problems for further studying works on Topsnut-gpws, and hope to find more something new and to do more theoretical works on Topsnut-gpws. We try to use Topsnut-groups to build up so-called network passwords for encrypting a network with thousand and thousand nodes (vertices). So we have investigated one of Topsnut-groups, called Abelian additive graphic group (graphic group for short). This type of graphic groups based on addition operation processes a particular property: “Every element in a graphic group can be regarded as “zero” of the graphic group, so we can call it an every-zero graphic group”. Unfortunately, we do not discover graphic group based on multiplication operation. It may be a way to find more graph labellings of a graph from connection between two or more graphic groups.

Several new colorings and new parameters on proper total colorings have been introduced and investigated. We have found that the difference-sum labelling (extremal labelling) can be admitted by every graph, so then it breaks down the case of no labelling admitted by each graph. Thereby, we are motivated from the difference-sum labelling and know that there are many extremal labellings like the difference-sum labelling, which mean that we may touch a new subbranch of graph labellings.

The above research works on two different areas motivate us to think of the biological combination of human being and AI machine in current development of the world, rather than AI machines only that will take a long time to success. An application project supported by mathematics like passwords depends on mathematics going deep into and continuous improvement, how long will it support last, how far can the project go.





§ ACKNOWLEDGMENT


The author, Bing Yao, is delight for supported by the National Natural Science Foundation of China under grants 61163054, 61363060 and 61662066. Bing Yao, cordially, thanks every member of Topological Graphic Passwords Symposium in the second semester of 2017-2018 academic year for their effective discussion and constructive suggestions, and part of members of the Symposium were supported by Scientific research project of Gansu University under grants 2016A-067, 2017A-047 and 2017A-254.




























1
Bondy-2008 J. A. Bondy, U. S. R. Murty. Graph Theory. Springer London, 2008.
Biddle-Chiasson-van-Oorschot-2009R. Biddle, S. Chiasson, and P.C. van Oorschot. Graphical passwords: Learning from the First Twelve Years. ACM Computing Surveys, 44(4), Article 19:1-41. Technical Report TR-09-09, School of Computer Science, Carleton University, Ottawa, Canada. 2009.
Yang-Ren-Yao-Ars-2016Chao Yang, Han Ren, Bing Yao. Adjacent Vertex Distinguishing Total Colorings Of Graphs With Four Distinguishing Constraints. Ars combinatoria 127(2016), pp. 197-208
Yang-Yao-Ren-Information-2016Chao Yang, Bing Yao, Han Ren. A Note on Graph Proper Total Colorings with Many Distinguishing Constraints. Information processing letters V 16, 6 396-400. (2016) DOI: 10.1016/j/ipl.2015.11.04, ISSN:0020-0190

Gao-Jia-Ye-Ma-2013Haichang Gao, Wei Jia, Fei Ye and Licheng Ma. A Survey on the Use of Graphical Passwords in Security. Journal Of Software, Vol. 8, No. 7, July 2013, 1678-1698.
Gallian2016 Joseph A. Gallian. A Dynamic Survey of Graph Labeling. The electronic journal of
combinatorics, 17 (2016), # DS6. (440 pages, 2265 reference papers, over 200 graph labellings)
Jamison-McMorris-Mulder-2003Robert E. Jamison, F.R. McMorris, Henry Martyn Mulder. Graphs with only caterpillars as spanning trees. Discrete Mathematics 272 (2003) 81-95.
Suo-Zhu-Owen-2005 Xiaoyuan Suo, Ying Zhu, G. Scott. Owen. Graphical Password: A Survey. In: Proceedings of Annual
Computer Security Applications Conference (ACSAC), Tucson, Arizona. IEEE (2005) 463-472.
Marumuthu-G-2015Marumuthu. G. Super Edge Magic Graceful Labeling of Generalized Petersen Graphs, Discrete Mathematics (2015) 235-241.
Hui-Sun-Bing-Yao2018Hui Sun, Bing Yao. New Graph Labellings Of Euler Graphs For Designing Topological Graphic Passwords. submitted (2018).
SH-ZXH-YB-2017-2Hui Sun, Xiaohui Zhang, Bing Yao. New Graphical Passwords On Trees Having Perfect Matchings. submitted to Information Processing letters (2017).
SH-ZXH-YB-2017-3Hui Sun, Xiaohui Zhang, and Bing Yao. Strongly (k,d)-Graphical Labellings For Designing Graphical Passwords In Communication. ICMITE 2017, MATEC Web of Conferences 139, 00204 (2017) DOI: 10.1051/matecconf/201713900204
Sun-Zhang-Zhao-Yao-2017Hui Sun, Xiaohui Zhang, Meimei Zhao and Bing Yao. New Algebraic Groups Produced By Graphical Passwords Based On Colorings And Labellings. ICMITE 2017, MATEC Web of Conferences 139, 00152 (2017), DOI: 10. 1051/matecconf/201713900152
SH-ZXH-YB-2017-4Hui Sun, Xiaohui Zhang, Bing Yao. Construction Of New Graphical Passwords With Graceful-type Labellings On Trees. 2018 2nd IEEE Advanced Information Management, Communicates, Electronic and Automation Control Conference (IMCEC 2018), 1491-1494.
SH-ZXH-YB-2018-5Hui Sun, Jing Su, Xiaohui Zhang, Bing Yao. New Graphic Cryptography Made By Strongly Graceful-Type Labellings Towards Communication Security. submitted (2018).
Wang-Xu-Yao-2016 Hongyu Wang, Jin Xu, Bing Yao. Exploring New Cryptographical Construction Of Complex Network Data. IEEE First International Conference on Data Science in Cyberspace. IEEE Computer Society, (2016):155-160.
Wang-Xu-Yao-Key-models-Lock-models-2016Hongyu Wang, Jin Xu, Bing Yao. The Key-models And Their Lock-models For Designing New Labellings Of Networks.Proceedings of 2016 IEEE Advanced Information Management, Communicates, Electronic and Automation Control Conference (IMCEC 2016) 565-5568.
Wang-Xu-Yao-2017Hongyu Wang, Jin Xu, Bing Yao. Odd-elegant Matching Trees In Planning New-type Graphical Passwords. submitted (2017).
Hongyu-Wang-2018-Doctor-thesisHongyu Wang. The Structure And Theoretical Analysis On Topological Graphic Passwords. Doctor's thesis. School of Electronics Engineering and Computer Science, Peking University, 2018.
Wang-Xu-Yao-2017-TwinHongyu Wang, Jin Xu, Bing Yao. Twin Odd-Graceful Trees Towards Information Security. Procedia Computer Science 107 (2017)15-20, DOI: 10.1016/j.procs.2017.03.050
Jin-Xu-(1)-2016Jin Xu. Theory on Structure and Coloring of Maximal Planar Graphs: (1) Recursion Formulae of Chromatic Polynomial and Four-Color Conjecture. Journal of Electronics and Information Technology. Vol.38 No.4, Jul. 2016, 763-770.
Jin-Xu-(2)-2016Jin Xu. Theory on Structure and Coloring of Maximal Planar Graphs: (2) Domino Configurations and Extending-Contracting Operations. Journal of Electronics and Information Technology. Vol.38 No.6, Jul. 2016, 1271-1327.
Jin-Xu-(3)-2016Jin Xu. Theory on Structure and Coloring of Maximal Planar Graphs: (3) Purely Tree-colorable and Uniquely 4-colorable Maximal Planar Graph Conjectures. Journal of Electronics and Information Technology. Vol.38 No.6, Jul. 2016, 1329-1353.
Jin-Xu-(4)-2016Jin Xu. Theory on Structure and Coloring of Maximal Planar Graphs: (4) σ-Operations and Kempe Equivalent Classes. Journal of Electronics and Information Technology. Vol.38 No.7, Jul. 2016, 1558-1585.
Yao-Liu-Yao-2017Bing Yao, Xia Liu and Ming Yao. Connections between labellings of trees. Bulletin of the Iranian Mathematical Society, ISSN: 1017-060X (Print) ISSN: 1735-8515 (Online), Vol. 43 (2017), 2, pp. 275-283.
Bing-Yao-Cheng-Yao-Zhao2009Bing Yao, Hui Cheng, Ming Yao and Meimei Zhao. A Note on Strongly
Graceful Trees. Ars Combinatoria 92 (2009), 155-169.
Yao-Mu-Sun-Zhang-Wang-Su-Ma-2018Bing Yao, Yarong Mu, Hui Sun, Xiaohui Zhang, Hongyu Wang, Jing Su, Fei Ma. Algebraic Groups For Construction Of Topological Graphic Passwords In Cryptography. 2018 IEEE 3rd Advanced Information Technology, Electronic and Automation Control Conference(IAEAC 2018), 2211-2216.
Yao-Mu-Sun-Zhang-Wang-Su-2018 Bing Yao, Yarong Mu, Hui Sun, Xiaohui Zhang, Hongyu Wang, Jing Su. Connection Between Text-based Passwords and Topological Graphic Passwords. 2018 IEEE 4th Information Technology and Mechatronics Engineering Conference (2018), submitted.
YAO-SUN-WANG-SU-XU2018arXivBing Yao, Hui Sun, Hongyu Wang, Jing Su, Jin Xu. Graph Theory Towards New Graphical Passwords In Information Networks. arXiv:1806.02929v1 [cs.CR] 8 Jun 2018
Yao-Zhang-Sun-Mu-Wang-Zhang-Yang-2018 Bing Yao, Xiaohui Zhang, Hui Sun, Yarong Mu, Hongyu Wang, Mingjun Zhang, Sihua Yang. On Space and Design of Topological Graphic Passwords For Information Networks. The 2018 IEEE 3rd Advanced Information Technology, Electronic and Automation Control Conference (IAEAC2018), submitted.
Zhang-Chen-Li-Yao-Lu-Wang-China-2005Z. Zhang, X. Chen, J. Li, B. Yao, X. Lv and J. Wang, On the adjacent
vertex-distinguishing total coloring of graphs, Sci. China Ser. A 48 (2005):289-299.
Zhang-Liu-Wang-2002Zhongfu Zhang, Linzhong Liu, Jianfang Wang, Adjacent strong edge coloring of graphs. Applied Math. Letters 15 (2002) 623-626.
Zhou-Yao-Chen-Tao2012Xiangqian Zhou, Bing Yao, Xiang'en Chen and Haixia Tao. A proof to the
odd-gracefulness of all lobsters. Ars Combinatoria 103 (2012), 13-18.
Zhou-Yao-Chen-2013Xiangqian Zhou, Bing Yao, Xiang'en Chen. Every lobster is odd-elegant. Information Processing Letters, 113,1-2(2013):30-33.








