# Topological Graphic Passwords And Their Matchings Towards Cryptography

Bing Yao1,5, Hui Sun1, Xiaohui Zhang1, Yarong Mu1, Yirong Sun1
Hongyu Wang2,‡, Jing Su2, Mingjun Zhang3, Sihua Yang3, Chao Yang4 Manuscript
received June 1, 2017; revised August 26, 2017. Corresponding author: Bing
Yao, email<EMAIL_ADDRESS>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<EMAIL_ADDRESS>
###### Abstract

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 these labellings can
be realized for trees or spanning trees of networks. In theoretical works we
explore Graph Labelling Analysis, and show first 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._

##  I 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 use and high level security? Graphical passwords (GPWs)
emerged for alternative 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
([3, 4, 5]). The existing GPWs are lack of frequent changed pictures and
occupy huge spaces, and need users to learn more and have good memory, and do
not provide more individual idea and personal making GPWs.

For overcoming weak limits, Wang _et al._ ([7, 8]) have designed Topological
graphic passwords (Topsnut-gpws) by an idea of “topological structure pulsing
number theory”. Clearly, Topsnut-gpws are naturally mathematical expression,
and can be storage into computer by canonical matrices, and be operated
quickly. 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 process 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; (v) huge spaces [25], for instant, there are $t_{23}\approx
2^{179}$ and $t_{24}\approx 2^{197}$, where $t_{p}$ is the number of graphs of
$p$ vertices, and over 200 existing labellings [2]. Thereby, Topsnut-gpws have
provable security, computationally security and unbreakable in nowadays’
computer. We will study Topsnut-gpws by the matching of view in this article.

###  I-A Examples

Matching phenomenon are popular and exist almost 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 a public key and a private key form an
_authentication matching_. Sometimes, people want one public key vs two or
more private keys. In [7] and [8], 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 byte as we 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 process, no decryption process.

We start our discussion with the following examples for showing Topsnut-gpws
work best in generating text-based passwords. In Fig.1, 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.1 that have the same label into one
vertex, the resulting graph is just $K_{4}$, so we write this fact as
$K_{4}=\odot\langle T_{i}\rangle^{3}_{1}$. 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})\cap E(T_{j})=\emptyset$. However, the
Topsnut-gpws $H_{1},H_{2},H_{3}$ shown in Fig.1 have common edges with the
same labels, we denote this fact as $E(H_{i})\cap E(H_{j})\neq\emptyset$; 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}=\ominus(H_{i})^{3}_{1}$. We write 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})|\neq|V(T_{j})|$ as $i\neq j$.
But, $|V(H_{i})|=|V(H_{j})|$ for $i\neq j$ in Fig.1, these $H_{1},H_{2},H_{3}$
are the spanning trees of $K_{4}$. Spanning trees, such as spanning algorithm,
Spanning Tree Protocol (STP), minimum spanning trees and spanning tree search,
are useful in today’s scientific areas, especially, network security.

Figure 1:  Two decompositions of $K_{4}$. The vertices and edges of each
$T_{i}$ and $H_{i}$ are labelled with $0,1,2,3$.

We use three Topsnut-gpws $T_{1},T_{2},T_{3}$ shown in Fig.1 to generate three
text-based passwords $D(T_{1})=112$, $D(T_{2})=110022$, $D(T_{3})=03312321$
for the purpose of encrypting files. Moreover, we produce a little bit of
complex text-based passwords below:

$D_{123}=D(T_{1})+D(T_{2})+D(T_{3})=11211002203312321,$

$D_{321}=D(T_{3})+D(T_{2})+D(T_{1})=03312321110022112$

$D_{132}=D(T_{1})+D(T_{3})+D(T_{2})=11203312321110022$

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}=\sum^{m}_{i=1}D(T_{j_{i}})$ (1)

with $1\leq j_{i}\leq 3$ for $m\geq 2$, such that $D_{T}$ has longer byte 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.1, and moreover

$D_{H}=\sum^{m}_{i=1}D(H_{j_{i}})$ (2)

with $1\leq j_{i}\leq 3$ for $m\geq 2$.

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

${\begin{split}T^{\prime}_{vv}=&1^{\prime}1012141^{\prime}10^{\prime}1152110^{\prime}21^{\prime}681021^{\prime}6^{\prime}13\\\
&17216^{\prime}13^{\prime}2613^{\prime}2^{\prime}913192^{\prime}9^{\prime}14^{\prime}135914^{\prime}\end{split}}$
(3)

and

${\begin{split}T^{\prime}_{vev}=&1^{\prime}1110131215141^{\prime}10^{\prime}11131592110^{\prime}21^{\prime}567\\\
&891021^{\prime}6^{\prime}19131175216^{\prime}13^{\prime}15219613^{\prime}2^{\prime}119\\\
&151321192^{\prime}9^{\prime}2414189^{\prime}14^{\prime}1511731951914^{\prime}\end{split}}$
(4)

or eliminating “′” from $T^{\prime}_{vv}$ and $T^{\prime}_{vev}$ for complex
reason yields

${\begin{split}T_{vv}=&1101214110115211021681021613\\\
&172161326132913192914135914\end{split}}$ (5)

and

${\begin{split}T_{vev}=&11110131215141101113159211021567\\\
&89102161913117521613152196132119\\\
&15132119292414189141511731951914\end{split}}$ (6)

Figure 2:  A twin odd-elegant graph $\odot_{2}\langle T_{1},T_{2}\rangle$
cited from [9].

It is not easy to reconstruct $\odot_{2}\langle T_{1},T_{2}\rangle$ shown in
Fig.2 by $T_{vv}$ in (5) or $T_{vev}$ in (6), 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 process of getting text-based
passwords from Topsnut-gpws is _irreversible_. On the other hands, 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:

  1. (1)

In general, for $n\geq 4$, how many ways are there to form a Topsnut-gpw
$K_{n}=\odot\langle T_{i}\rangle^{m}_{1}$ with $E(T_{i})\cap
E(T_{j})=\emptyset$ as $i\neq j$, or $K_{n}=\ominus(H_{i})^{m}_{1}$ with
$V(K_{n})=V(H_{i})$ for $i\in[1,m]$ and $|E(H_{i})|=|E(H_{j})|$?

  2. (2)

Are the text-based passwords $D_{T}$ in (1) and $D_{H}$ in (2), $T_{vv}$ in
(5) and $T_{vev}$ in (6) computationally unbreakable?

Fig.3 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:

  1. $-$

How many configurations $T_{i}$ or $H_{i}$ are there for producing $K_{n}$
with $n\geq 4$?

  2. $-$

How many type of label-functions (also, called labellings hereafter) do
$T_{i}$ and $H_{i}$ admit?

  3. $-$

How to label the vertices or edges of $T_{i}$ or $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 label into one just results $K_{n}=\odot\langle
T_{i}\rangle^{m}_{1}$ or $K_{n}=\ominus(H_{i})^{m}_{1}$?

Figure 3:  Each Topsnut-gpw $T_{i}$ ($H_{i}$) consists of a topological
structure $T_{i,1}$ ($H_{i,1}$) and label-function $T_{i,2}$ ($H_{i,2}$).

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
properties 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 is 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.3). So, we are reasonable
to consider any labeled graph as a Topsnut-gpw here. Notice that Topsnut-gpws
can be defined by many labellings shown in [2].

###  I-B Preliminary

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

A _tree_ is a graph in which any pair of two vertices $x,y$ is connected by a
unique path $P(x,y)=xu_{1}u_{2}\cdots u_{m}y$; 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\subseteq V(G)\cup
E(G)\rightarrow[a,b]$ such that $h(x)\neq h(y)$ for any pair of elements $x,y$
of $S$, and write the label set $h(S)=\\{h(x):x\in S\\}$. A _dual labelling_
$h^{\prime}$ of a labelling $h$ is defined as: $h^{\prime}(z)=\max h(S)+\min
h(S)-h(z)$ for $z\in S$. Moreover, $h(S)$ is called the _vertex label set_ if
$S=V(G)$, $h(S)$ the _edge label set_ if $S=E(G)$, and $h(S)$ a _universal
label set_ if $S=V(G)\cup E(G)$.

We, in the following discussion, need four pair of graph operations on four
basic elements of vertex, edge, path and cycle as follows: In Fig.4, 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$, we call $N(x)$ the _neighbor set_. In Fig.4, after split
operations, we have to emphasize that the neighbor sets hold
$N(y^{\prime})\cap N(y^{\prime\prime})=\emptyset$, $N(u^{\prime})\cap
N(u^{\prime\prime})=\emptyset$ and $N(v^{\prime})\cap
N(v^{\prime\prime})=\emptyset$. The _path/cycle-split operation_ and the
_path/cycle-identifying operation_ are shown in Fig.5, it stresses that the
neighbor sets $N(u^{\prime}_{j})\cap N(u^{\prime\prime}_{j})=\emptyset$ with
$j\in[1,n]$.

Figure 4:  A scheme for illustrating four graph operations: vertex-split
operation; vertex-identifying operation; edge-split operation; edge-
identifying operation.
Figure 5:  A path-split operation from (a) to (b), and a path-identifying
operation from (b) to (a). Also, a cycle-split operation from (a) to (b), and
a cycle-identifying operation from (b) to (a).

##  II Matching diversity

###  II-A Configuration matching partition

Let $W$ be a _universal graph_ having a labelling $f$. If $W$ contains _edge
disjoint subgraph_ $G_{i}$ having a labelling $f_{i}$ induced by $f$ with
$i\in[1,m]$ such that $V(W)=\bigcup^{m}_{i=1}V(G_{i})$ and
$E(W)=\bigcup^{m}_{i=1}E(G_{i})$ after identifying the vertices of
$G_{1},G_{2},\dots,G_{m}$ having the same label into one vertex (see an
example $K_{4}=\odot\langle T_{i}\rangle^{3}_{1}$ shown in Fig.1), we write
this case as $W=\odot\langle G_{i}\rangle^{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},\dots,G_{m}\\}\setminus\\{G_{i}\\}$ on the edge-disjoint
matching partition $W$, then we denote simply $W$ as $\odot\langle
G_{i},Z_{i}\rangle$. Also, we allow the case $V(G_{i})=V(W)$ with $i\in[1,m]$
in an edge-disjoint matching partition $W=\odot\langle G_{i}\rangle^{m}_{1}$.

In encryption of networks, each $G_{i}$ with $i\in[1,m]$ can be considered as
a _key_ , so $W=\odot\langle G_{i}\rangle^{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=\odot\langle G_{i},Z_{i}\rangle$
is a _one-more authentication_.

Similarly, we have a _multiple-edge matching partition_
$W=\ominus(H_{i})^{m}_{1}$ as each subgraph $H_{i}$ having a labelling $f_{i}$
induced by $f$ with $i\in[1,m]$ holds $V(H_{i})=V(W)$ and $E(H_{i})\cap
E(G_{j})\neq\emptyset$ for some $i\neq j$ by identifying the vertices of
$\bigcup^{m}_{i=1}V(H_{i})$ having the same label into one vertex and
eliminating multiple edges. A _mixed matching partition_
$W=\bigcup^{m}_{i=1}G_{i}$ has some $G_{j}$ holding $V(G_{j})\neq V(W)$ and
$E(G_{s})\cap E(G_{t})\neq\emptyset$ for some $s\neq t$.

######  Experiment 1.

Naturally, a labelling $h$ and its dual labelling $h^{\prime}$ of a graph $G$
are matching with each other, $(h,h^{\prime})$ is 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^{\prime}$ of $h$, so we
have a graph $\odot_{k}\langle G_{1},G_{2}\rangle$ obtained by identifying
those vertices of $V(G_{1})\cup V(G_{2})$ having the same label into one
vertex, where $k=|h(G_{1})\cap h^{\prime}(G_{2})|$.

######  Experiment 2.

As $W=K_{n}$, $V(K_{n})=V(G_{i})$ with $i=1,2$ and $E(G_{1})\cap
E(G_{2})=\emptyset$ holding $E(K_{n})=E(G_{1})\cup E(G_{2})$, 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}=\odot\langle G_{1},G_{2}\rangle$. 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}$.

######  Experiment 3.

As $W$ is an Eulerian graph, the edge-disjoint matching partition
$W=\odot_{k}\langle G_{i}\rangle^{m}_{1}$ has its vertex degree
$\textrm{deg}_{W}(u)=\sum^{m}_{i=1}\textrm{deg}_{G_{i}}(u)$ to be even for
each vertex $u\in V(W)$. Here, $W$ admits some v-set e-proper labelling
$(F,g)$ defined in Definition 6. For $m=2$, let $G_{1},G_{2}$ are not Eulerian
graphs, but $\odot_{k}\langle G_{1},G_{2}\rangle$ is Eulerian, then we say
both $G_{1},G_{2}$ are _Eulerian matching_ to each other.

######  Experiment 4.

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}=\odot_{k}\langle G_{i}\rangle^{m}_{1}$ may be
_computationally unbreakable_ :

(i) Anton Kotzig (1964) proposed the _Perfect 1-Factorization Conjecture_ :
For any $n\geq 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$ 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\geq 3$, given $n$ disjoint trees $T_{k}$ of $k$ vertices with
respect to $1\leq k\leq n$. Then the complete graph $K_{n}$ can be decomposed
into the union of $n$ edge-disjoint trees $H_{k}$, such that $T_{k}\cong
H_{k}$ with $k\in[1,n]$. Also, we write this case as $\langle
T_{1},T_{2},\dots,T_{m}|K_{n}\rangle$.

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

###  II-B Coloring/labelling matchings

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

######  Experiment 5.

As $W$ is a _maximal planar graph_ , each $G_{i}$ with $i\in[1,m]$ is a _semi-
maximal planar graph_ ([11, 12, 13, 14]) having a common even-cycle $C$, and
$E(G_{i})\cap E(G_{j})=E(C)$ for $i\neq j$. If each $G_{i}$ is $4$-colorable
such that the even-cycle $C$ is colored with $1,2$ only, then we identify
those vertices $1$ of $\bigcup^{m}_{i=1}V(G_{i})$ into one, and identify those
vertices $2$ of $\bigcup^{m}_{i=1}V(G_{i})$ into one, and eliminate multiple
edges. The resulting Topsnut-gpw, like a “book”, is denoted as
$W=\ominus_{C}(G_{i})^{m}_{1}$, and $G_{i}\cup G_{j}$ for $i\neq j$ is a
maximal planar graph, we say $W=\ominus_{C}(G_{i})^{m}_{1}$ 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. 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 $\overline{G}^{L}$, and call $G^{L}$ and $\overline{G}^{L}$ are matching
to each other (see Fig.6). Determining particular _semi-maximal planar
matchings_ $(G^{L},\overline{G}^{L})$ can provide more complex models for
authentication of public keys and private keys, such as both $G^{L}-V(L)$ and
$\overline{G}^{L}-V(L)$ are trees.

Figure 6:  A maximal planar graph $G=\ominus_{L}(G^{L},\overline{G}^{L})$ with
its two semi-maximal planar graphs $G^{L}$ and $\overline{G}^{L}$. As known,
every planar graph is $4$-colorable, no mathematical proof for this fact up to
now.

######  Definition 1.

([2, 21, 32]) Suppose that a $(p,q)$-graph $G$ admits a vertex labelling
$f:V(G)\rightarrow[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}$, we call $f$ an _odd-
graceful labelling_ of $G$ (called an _odd-graceful graph_). Furthermore, if
$G$ is a bipartite graph with partition $(X,Y)$ holding $\max\\{f(x):~{}x\in
X\\}<\min\\{f(y):~{}y\in Y\\}$ ($f_{\max}(X)<f_{\min}(Y)$ for short), then $f$
is called a _set-ordered odd-graceful labelling_. $\Box$

In [22], we expand the odd-graceful labelling as: Let $G$ be a $(p,q)$-graph,
we have:

(i) If $G$ admits a vertex labelling $f:V(G)\rightarrow[0,2q]$ (it is allowed
$f(E(G))\subset[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)|$ such that
$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$ as: $g:V(H)\rightarrow[0,2q-1]$, every edge $uv\in E(H)$ has its
label $g(uv)=|g(u)-g(v)|$ holding $g(E(H))=[1,2q-1]^{o}$, such that
$f(V(G))\cup g(V(H))=[0,2q]$, or $[0,2q-1]$ and $|f(V(G))\cap g(V(H))|=k$ (see
examples shown in Fig.7). We call $H$ with a $k$-matching odd-graceful
labelling as an _odd-graceful Topsnut-matching_ of $G$, denoted as
$\odot_{k}\langle G,H\rangle$. (see Fig. 7 and Fig.8)

(iii) A _$k$ -sequential odd-graceful labelling_ $h:V(G)\rightarrow[k,2q-1+k]$
such that the induced edge labelling $h(uv)=|h(u)-h(v)|$ for $uv\in E(G)$
holding $g(E(G))=[1,2q-1]^{o}$.

######  Definition 2.

[33] A $(p,q)$-graph $G$ admits a labelling $f:V(G)\rightarrow[0,2q-1]$ such
that each edge $uv\in E(G)$ is labeled as $f(uv)=f(u)+f(v)~{}(\bmod~{}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_). $\Box$

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.7, we have six odd-
graceful Topsnut-matchings $G_{i}=\odot_{0}\langle G,H_{i}\rangle$ with
$i\in[1,6]$, since $G$ admits an odd-graceful labelling. Here,
$V(G_{i})=V(G)\cup V(H_{i})$ and $E(G_{i})=E(G)\cup E(H_{i})$ with
$i\in[1,6]$. Here, we present an algorithm for finding odd-graceful Topsnut-
matchings.

ODD-GRACEFUL-GRAPH Algorithm:

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

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

_Step 1._ Build up $R(f,G)=[0,2q-1]\setminus f(V(G))$ (or
$R^{\prime}(f,G)=[0,2q]\setminus f(V(G))$), and make a candidate edge set
$C_{0}=\\{x^{o}x^{e}:x^{o},x^{e}\in R(f,G),x^{o}\textrm{ is odd,
}x^{e}\textrm{ is even}\\}$, and a graph $H_{0}$ is constructed by identifying
the end-vertices of edges of $C_{0}$ into one vertex, these end-vertices have
the same label.

_Step 2._ If the graph $H_{k}$ contains no two edges $x^{o}_{i}x^{e}_{i}$ and
$x^{o}_{j}x^{e}_{j}$ holding $|x^{o}_{i}-x^{e}_{i}|=|x^{o}_{j}-x^{e}_{j}|$, go
to Step 3; otherwise, do $H_{k+1}:=x^{o}_{i}x^{e}_{i}+H_{k}-E(k+1)$ with
$E(k+1)=\\{x^{o}_{j}x^{e}_{j}:|x^{o}_{j}-x^{e}_{j}|=k+1\\}\subset C_{0}$ and
$x^{o}_{i}x^{e}_{i}$ with $|x^{o}_{i}-x^{e}_{i}|=k+1$, such that $H_{k+1}$ is
connected.

_Step 3._ Return a connected Topsnut-matching $H$ admitting an odd-graceful
labelling.

Figure 7:  A $(7,7)$-graph $G$ admitting an odd-graceful labelling has six
odd-graceful matchings $H_{i}$ with a matching odd-graceful labelling $g_{i}$
for $i\in[1,6]$, such that each odd-graceful Topsnut-matching $\odot\langle
G,H_{i}\rangle$ holds $f(V(G))\cup g_{i}(V(H_{i}))=[0,14]$ and $f(V(G))\cap
g_{i}(V(H_{i}))=\emptyset$ with $i\in[1,6]$.
Figure 8:  Two odd-graceful Topsnut-matchings $\odot\langle G,L_{1}\rangle$
and $\odot\langle G,L_{2}\rangle$ of a $(7,7)$-graph $G$ shown in Fig.7 hold
$f(V(G))\cap g_{1}(V(L_{1}))=\\{2\\}$, $f(V(G))\cap g_{2}(V(L_{2}))=\\{10\\}$
and $f(V(G))\cup g(V(L_{i}))\neq[0,14]$ with $i=1,2$.

Let $H$ be a (pan-)odd-graceful graph with vertices $v_{1},v_{2},\dots,v_{p}$.
If each vertex $v_{i}$ matches with a (pan-)odd-graceful graph $T_{i}$ with
$i\in[1,p]$ such that there exists an odd-graceful Topsnut-matching
$\odot_{1}\langle H,T_{i}\rangle^{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 label. We say $\odot_{1}\langle H,T_{i}\rangle^{p}_{1}$
a _(pan-)odd-graceful Topsnut-matching team_ (see Fig.9). Moreover,
$\odot_{1}\langle H,T_{i}\rangle^{p}_{1}$ is called a _perfect (pan-)odd-
gracefully Topsnut-matching team_ if $T_{i}\cong T_{j}$ for $i\neq j$.

Figure 9:  An odd-graceful Topsnut-matching team.

######  Theorem 1.

Each caterpillar $H$ of $p$ vertices has a (pan-)odd-graceful Topsnut-matching
team $\odot_{1}\langle H,T_{i}\rangle^{p}_{1}$.

###### Proof.

There is a path $P=u_{1}u_{2}\cdots u_{n}$ in a caterpillar $H$, such that
each $u_{i}$ has its own leaf set $L(u_{i})=\\{v_{i,j}:j\in[1,m_{i}]\\}$ with
$m_{i}\geq 0$ and $i\in[1,n]$. And $V(H)=V(P)\cup L(u_{1})\cup
L(u_{2})\cup\cdots\cup L(u_{n})$. See a caterpillar shown in Fig.10.

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\in[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\in[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\in[1,m_{6}]$. For $i\geq
2$, we let

$h(u_{2i-1})=h(v_{2i-2,m_{2i-2}})+2=2(i-1+\sum^{i-1}_{k=1}m_{2k})$

and
$h(v_{2i,j})=h(u_{2i-1})+2j=2(i-1+j+\sum^{i-1}_{k=1}m_{2k})$ with
$j\in[1,m_{2i}]$.

Clearly, $h(v_{2i-2,m_{2i-2}})<h(u_{2i-1})$ and $h(v_{2i,j})<h(v_{2i,j+1})$
with $j\in[1,m_{2i}-1]$ and $i\geq 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\in[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\in[1,m_{n-3}]$.

For $i\geq 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\in[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\in[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\in[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\in[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\in[1,m_{n-2i}]$ for $i\geq 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\in[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\in V(T)=V(H)$. Clearly, $h^{*}(V(H))\cup
h(V(T))=[0,2(P-1)]$ and $h^{*}(V(H))\cup h(V(T))=\emptyset$. Now, we make
another caterpillar $T-v_{n,1}$ with a labelling $f$ defined by $f(y)=h(y)$
for $y\in V(T)\setminus\\{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^{\prime}_{i}$ of $T-v_{n,1}$ by an edge $w_{i}w^{\prime}_{i}$, the
resulting tree is denoted as $T_{i}=T-v_{n,1}+w_{i}w^{\prime}_{i}$, and define
a labelling $f_{i}$ of $T_{i}$ as $f_{i}(x)=f(x)$ for $x\in
V(T_{i})\setminus\\{w_{i}\\}$, and $f_{i}(w_{i})\in h^{*}(V(H))$ such that
$|f_{i}(w_{i})-f_{i}(w^{\prime}_{i})|=1$, which means
$f_{i}(V(T_{i}))=[1,2p-3]^{o}$. Thereby, $|f_{i}(V(T_{i}))\cap
h^{*}(V(H))|=1$, and the graph $\odot_{1}\langle H,T_{i}\rangle$ is a pan-odd-
graceful Topsnut-matching, and so we can claim that $\odot_{1}\langle
H,T_{i}\rangle^{p}_{1}$ is a (pan-)odd-graceful Topsnut-matching team. ∎

Figure 10: A caterpillar.

In the proof of Theorem 1, we can see $H-v_{n,1}\cong T-v_{n,1}\cong
T_{i}-w_{i}$ with $i\in[1,p]$, so $\odot_{1}\langle H,T_{i}\rangle^{p}_{1}$ is
approximately a perfect (pan-)odd-gracefully Topsnut-matching team. Thereby,
we can get a result: “ _If a tree $T$ of $p$ vertices has an odd-graceful
labelling $f$ such that $f(uv)=1$ for an edge $uv\in E(T)$, where $v$ is a
leaf of $T$, that is, $deg_{T}(v)=1$. Then we have a (pan-)odd-graceful
Topsnut-matching team $\odot_{1}\langle H,T_{i}\rangle^{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 has a pan-odd-graceful labelling $g$ defined by $g(x)=f(x)+1$ for $x\in
V(T)=V(H)$_.”

For designing complex Topsnut-gpws, Wang _et al._ ([27, 9]) have defined
firstly the twin-type of labellings by means of the matching of view (also,
_key-vs-lock_).

######  Definition 3.

[27] 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=\odot_{k}\langle G_{1},G_{2}\rangle$
admits a vertex labelling $f$: $V(G)\rightarrow[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\in E(G_{2})\\}=[1,q-1]^{o}$; (iii)
$|f(V(G_{1}))\cap f(V(G_{2}))|=k$ and $f(V(G_{1}))\cup
f(V(G_{2}))\subseteq[0,q-1]$. Then $f$ is called a _twin odd-graceful
labelling_ (Tog-labelling) of $G$, and $G$ a _Tog-matching partition_. $\Box$

######  Definition 4.

[9] 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=\odot_{k}\langle G_{1},G_{2}\rangle$
admits a vertex labelling $f$: $V(G)\rightarrow[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}))\cap
f(V(G_{2}))|=k$ and $f(V(G_{1}))\cup f(V(G_{2}))\subseteq[0,q-1]$. Then $f$ is
called a _twin odd-elegant labelling_ (Toe-labelling) of $G$ (called a _Toe-
graph_), and $\odot_{k}\langle G_{1},G_{2}\rangle$ is called a _Toe-matching
partition_ , where $G_{1}$ is the _Toe-source_ and $G_{2}$ is a _Toe-
association_. $\Box$

Fig.2 shows an example for understanding Definition 4. If each $G_{i}$ with
$i=1,2$ is a connected graph in Definition 4, and $G_{1}$ is a bipartite
connected graph with bipartition $(X_{1},Y_{1})$ holding
$f_{\max}(X_{1})<f_{\min}(Y_{1})$, 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=\odot_{k}\langle
G_{1},G_{2}\rangle$, such as

######  Theorem 2.

_[9]_ 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 $\odot_{2}\langle
T,T_{i}\rangle$ with $i=1,2$ admits a set-ordered twin odd-elegant labelling.

Wang _et al._ have constructed large scale of Toe-graphs $\odot_{2}\langle
H_{1},H_{2}\rangle$ by smaller $\odot_{2}\langle T_{i},T^{\prime}_{i}\rangle$
with $i\in[1,m]$ for exploring Topsnut-chains. Moreover, they have mixed odd-
graceful labelling with odd-elegant labelling together in Definition 5 below.

######  Definition 5.

[9] 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=\odot_{k}\langle G_{1},G_{2}\rangle$
admits a vertex labelling $f$: $V(G)\rightarrow[0,q]$ such that (i) $f$ is an
odd-graceful labelling of $G_{1}$; (ii) $f:V(G_{2})\rightarrow[0,2|E(G_{2})|]$
holding $f(E(G_{2}))=\\{f(uv)=f(u)+f(v)(\bmod~{}2|E(G_{2})|):~{}uv\in
E(G_{2})\\}=[1,2|E(G_{2})|-1]^{o}$. Then $f$ is called a _2-odd graceful-
elegant labelling_ (a 2odd2-labelling) of $G$ (called a _2odd2-graph_), and
$\odot_{k}\langle G_{1},G_{2}\rangle$ is called a _2odd2-matching partition_.
$\Box$

In Definition 5, if $f$ is an set-ordered odd-graceful labelling of $G_{1}$,
and $G_{2}$ has its bipartition $(X,Y)$ holding $f_{\max}(X)<f_{\min}(Y)$,
then we call $f$ a _set-ordered 2odd2-labelling_ of $G$. The results on the
2odd2-matching partition can be found in [9]. Wang et al. propose several
conjectures on twin type of odd-graceful/odd-elegant labellings, which mean
that Topsnut-gpes made by such labellings are computational security ([7, 8,
9, 27]).

Figure 11:  Three 2odd2-graphs $\odot_{2}\langle G_{i},H_{i}\rangle$ for
$i\in[1,3]$ cited from [9], where $G_{i}$ has black edges, and $H_{i}$ has
blue edges.

###  II-C 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\\}$.

######  Definition 6.

∗ Let $G$ be a $(p,q)$-graph $G$. We have:

(i) A set mapping $F:V(G)\cup E(G)\rightarrow[0,p+q]^{2}$ is called a _total
set-labelling_ of $G$ if $F(x)\neq F(y)$ for distinct elements $x,y\in
V(G)\cup E(G)$.

(ii) A vertex set mapping $F:V(G)\rightarrow[0,p+q]^{2}$ is called a _vertex
set-labelling_ of $G$ if $F(x)\neq F(y)$ for distinct vertices $x,y\in V(G)$.

(iii) An edge set mapping $F:E(G)\rightarrow[0,p+q]^{2}$ is called an _edge
set-labelling_ of $G$ if $F(uv)\neq F(xy)$ for distinct edges $uv,xy\in E(G)$.

(iv) A vertex set mapping $F:V(G)\rightarrow[0,p+q]^{2}$ and a proper edge
mapping $g:E(G)\rightarrow[a,b]$ are called a _v-set e-proper labelling
$(F,g)$_ of $G$ if $F(x)\cap F(y)=\emptyset$ for distinct vertices $x,y\in
V(G)$ and two edge labels $g(uv)\neq g(wz)$ for distinct edges $uv,wz\in
E(G)$.

(v) An edge set mapping $F:E(G)\rightarrow[0,p+q]^{2}$ and a proper vertex
mapping $f:V(G)\rightarrow[a,b]$ are called an _e-set v-proper labelling
$(F,f)$_ of $G$ if $F(uv)\neq F(wz)$ for distinct edges $uv,wz\in E(G)$ and
two vertex labels $f(x)\neq f(y)$ for distinct vertices $x,y\in V(G)$. $\Box$

######  Experiment 6.

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

Figure 12:  (a) A v-set e-proper graceful labelling; (b) a v-set e-proper odd-
graceful labelling.
Figure 13:  A lobster $T$ admits: (a) a labelling with null edge-labels: (b) a
pan-edge-magic total labelling; (c) a pan-edge-magic total labelling; (d) a
felicitous labelling; (e) an edge-magic graceful labelling; (f) an edge-odd-
graceful labelling.

######  Experiment 7.

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

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

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

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

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

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

$F(uv)=\\{\bullet,2,3,10,13\\}$.

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

######  Theorem 3.

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\in E(T)\\}\geq
5$.

###### Proof.

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

We define the following labellings:

  1. (L-1)

$h_{1}(w)=f^{*}(w)$ for $w\in V(T)$, $h_{1}(x_{i}y_{j})=null$ for each edge
$x_{i}y_{j}\in E(T)$.

  2. (L-2)

We construct a labelling $h_{2}$ by setting $h_{2}(w)=f^{*}(w)$ for $w\in
V(T)$, and $h_{2}(x_{i}y_{j})=f^{*}(x_{i}y_{j})$ for each edge $x_{i}y_{j}\in
E(T)$. We verify

${\begin{split}&\quad h_{2}(x_{i})+h_{2}(x_{i}y_{j})+h_{2}(y_{j})\\\
&=f^{*}(x_{i})+f^{*}(x_{i}y_{j})+f^{*}(y_{j})\\\
&=f(x_{i})+f(x_{i}y_{j})+f(y_{t-j+1})\\\ &=i-1+(s+j-i+1)+s+(t-j+1)-1\\\
&=2s+t=p+s.\end{split}}$

Thereby, $h_{2}$ is really a _pan-edge-magic total labelling_ of $T$.

  3. (L-3)

Suppose that $h_{3}(w)=f^{*}(w)$ for $w\in V(T)$,
$h_{3}(x_{i}y_{j})=p-1+f^{*}(x_{i}y_{j})$ for each edge $x_{i}y_{j}\in E(T)$.
Hence, $h_{3}$ is another _pan-edge-magic total labelling_ of $T$.

  4. (L-4)

Define a labelling $h_{4}$ by setting $h_{4}(w)=f^{*}(w)$ for $w\in V(T)$ and
$h_{4}(x_{i}y_{j})=h_{4}(x_{i})+h_{4}(y_{j})~{}(\bmod~{}p-1)$ for each edge
$x_{i}y_{j}\in E(T)$. We compute

${\begin{split}h_{4}(x_{i}y_{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_{i}y_{j})\\\ &=p+s-f(x_{i}y_{j}),\end{split}}$

which distributes a set
$\\{p+s-1,p+s-2,\dots,p,p-1,p-2,\dots,s+1\\}~{}(\bmod~{}p-1)=\\{s,s-1,\dots,1,0,p-2,\dots,s+1\\}=[0,p-2]$.
So we claim that $h_{4}$ is a _felicitous labelling_ of $T$.

  5. (L-5)

We define a labelling $h_{5}$ as: $h_{5}(w)=f^{*}(w)$ for $w\in V(T)$ and
$h_{5}(x_{i}y_{j})=p-f^{*}(x_{i}y_{j})=p-f(x_{i}y_{j})$ for each edge
$x_{i}y_{j}\in E(T)$. Because

${\begin{split}&\quad|h_{5}(x_{i})+h_{5}(y_{j})-h_{5}(x_{i}y_{j})|\\\
&=|f^{*}(x_{i})+f^{*}(y_{j})+f^{*}(x_{i}y_{j})-p|\\\
&=|f(x_{i})+f(y_{t-j+1})+f(x_{i}y_{j})-p|\\\
&=|i-1+s+(t-j+1)-1+s+j-i+1-p|=s-1,\end{split}}$

then we know that $h_{5}$ is an _edge-magic graceful labelling_ of $T$
according to Definition 14.

  6. (L-6)

Let $h_{6}$ be defined by $h_{6}(w)=f^{*}(w)$ for $w\in V(T)$ and
$h_{6}(x_{i}y_{j})=2f^{*}(x_{i}y_{j})-1=2f(x_{i}y_{j})-1$ for each edge
$x_{i}y_{j}\in E(T)$. We get

${\begin{split}&\quad h_{6}(x_{i})+h_{6}(x_{i}y_{j})+h_{6}(y_{j})\\\
&=f(x_{i})+f(y_{t-j+1})+2f(x_{i}y_{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_{i}y_{j})-1\\\ &=p+s-2+f(x_{i}y_{j})\end{split}}$

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

We can see relationships between the above labellings:
$h_{2}(x_{i}y_{j})+p-1=h_{3}(x_{i}y_{j})$,

$h_{2}(x_{i}y_{j})+h_{4}(x_{i}y_{j})=f(x_{i}y_{j})+p+s-f(x_{i}y_{j})\equiv
s-1~{}(\bmod~{}p-1)$

and

$h_{2}(x_{i}y_{j})+h_{5}(x_{i}y_{j})=f(x_{i}y_{j})+p-f(x_{i}y_{j})=p.$

Now, we define the desired e-set v-proper labelling $F$ in the way:
$F(x_{i}y_{j})=\\{h_{k}(x_{i}y_{j}):~{}k\in[1,6]\\}$ for each edge
$x_{i}y_{j}\in E(T)$, so $T$ admits an e-set v-proper labelling $(F,f^{*})$
with $\max\\{|F(uv)|:uv\in E(T)\\}\geq 6$. ∎

######  Definition 7.

∗ If a $(p,q)$-graph $G$ admits an e-set v-proper labelling $(F,f)$ by
$f:V(G)\rightarrow[0,a(p,q)]$ and $F:E(G)\rightarrow[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},\dots,T_{m}$ with $m\geq 2$ and
$E(G)=\bigcup^{m}_{i=1}E(T_{i})$ (allow $E(T_{i})\cap E(T_{j})\neq\emptyset$
for some $i\neq 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=\oplus_{F}\langle T_{i}\rangle^{m}_{1}$. $\Box$

Figure 14:  A multiple-tree matching partition $G$ for illustrating Definition
7.

######  Experiment 8.

A multiple-tree matching partition $G$ shown in Fig.14 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)\in f(V(G))$ for $x\in V(T_{1})=V(G)$, each edge $uv\in E(T_{1})$ is
labeled as $f_{1}(uv)=|f_{1}(u)-f_{1}(v)|\in F(uv)$; and $f_{2}(u)\in f(V(G))$
for $y\in V(T_{2})=V(G)$, $f_{2}(uv)\in F(uv)$ for each edge $uv\in E(T_{2})$,
such that $f_{2}(u)+f_{2}(uv)+f_{2}(v)=28$ for $uv\in E(T_{2})$. We can see
$T_{0}=T_{1}\cap T_{2}$, called the _common body_ of $G$, each edge of $T_{0}$
is labeled with a set.

Similarly with Definition 7, we propose:

######  Definition 8.

∗ If a $(p,q)$-graph $G$ admits a vertex labelling $f:V(G)\rightarrow[0,p-1]$,
such that $G$ can be decomposed into graphs $G_{1},G_{2},\dots,G_{m}$ with
$m\geq 2$ and $E(G)=\bigcup^{m}_{i=1}E(G_{i})$ and $E(G_{i})\cap
E(G_{j})=\emptyset$ for $i\neq 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=\odot_{f}\langle G_{i}\rangle^{m}_{1}$. $\Box$

In Fig.15, we can see that $E(G_{i})\cap E(G_{j})=\emptyset$ for $i\neq 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\in[2,4]$.
$H_{j}=\odot_{k_{j}}\langle G_{1},G_{j}\rangle$, with $j\in[2,4]$, admits the
labelling $f$ such that $f(E(G_{1}))=\\{|f(u)-f(v)|:~{}uv\in
E(G_{1})\\}=[1,11]$, $f(E(G_{j}))=\\{f(x)+f(y)(\bmod~{}11):~{}xy\in
E(G_{j})\\}=[1,11]$ (where we consider $0\equiv 11$), so each
$H_{j}=\odot_{k_{j}}\langle G_{1},G_{j}\rangle$ with $j\in[2,4]$ is called a
_graceful-felicitous matching partition_.

Figure 15:  An example for illustrating Definition 8.

######  Theorem 4.

If a tree $T$ admits a set-ordered graceful labelling, then $T$ matches with a
multiple-tree matching partition $G=\oplus_{F}\langle T_{i}\rangle^{m}_{1}$
with $m\geq 2$.

###### Proof.

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\in[1,s]\\}$ and
$Y=\\{y_{j}:j\in[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\in[1,s]$,
$f(y_{j})=s+j-1$ for $j\in[1,t]$ and $f(x_{i}y_{j})=f(y_{j})-f(x_{i})=s+j-i$
for each edge $x_{i}y_{j}\in 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.

  1. (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\in[1,s]$,
$f_{2}(y_{j})=f(y_{t-j+1})+1$ for $j\in[1,t]$, and
$f_{2}(x_{i}y_{j})=f(x_{i}y_{j})+p$ for each edge $x_{i}y_{j}\in E(T)$. Notice
that $f_{2}(V(T_{2}))=[1,p]$. Furthermore,

${\begin{split}&\quad f_{2}(x_{i})+f_{2}(x_{i}y_{j})+f_{2}(y_{j})\\\
&=f(x_{i})+f(x_{i}y_{j})+p+f(y_{t-j+1})\\\ &=s+2p+1.\end{split}}$ (7)

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)$.

  2. (Equ-2)

$T_{3}$ is a copy of $T$, and admits an edge-magic total labelling $f_{3}$
defined as: $f_{3}(x_{i})=f(x_{s-i+1})+1$ for $i\in[1,s]$,
$f_{3}(y_{j})=f(y_{j})+1$ for $j\in[1,t]$, and
$f_{2}(x_{i}y_{j})=f(x_{i}y_{j})+p$ for each edge $x_{i}y_{j}\in E(T)$. So
$f_{3}(V(T_{3}))=[1,p]$. By the same way used in Equ-1, $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)$.

  3. (Equ-3)

$T_{4}$ is isomorphic to $T$, and admits a super felicitous labelling $f_{4}$
made by: $f_{4}(x_{i})=f(x_{i})$ for $i\in[1,s]$, $f_{4}(y_{j})=f(y_{t-j+1})$
for $j\in[1,t]$. Moreover, we have

${\begin{split}&\quad 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-\big{[}f(y_{j})-f(x_{i})\big{]}\\\
&=s+p-1-f(x_{i}y_{j}),\end{split}}$ (8)

The above form (8) induces two sets
$S_{1}=\\{s+p-1-1,s+p-1-2,\dots,s+p-1-(s-1),s+p-1-s\\}$ and
$S_{2}=\\{p-2,p-3,\dots,s\\}$. Under modulo $(p-1)$, $S_{1}\equiv[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)$.

  4. (Equ-4)

$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\in[1,s]$, $f_{5}(y_{j})=f(y_{j})$ for $j\in[1,t]$. The remainder proof is
as the same as that in Equ-3.

  5. (Equ-5)

Let $T_{6}\cong T$. We define a labelling $f_{6}$ of $T_{6}$ in the way:
$f_{6}(x_{i})=f(x_{i})+1$ for $i\in[1,s]$,
$f_{6}(y_{j})=f(y_{t-j+1})+1=s+p-f(y_{j})$ for $j\in[1,t]$, and
$f_{6}(x_{i}y_{j})=2p-f(x_{i}y_{j})$ for each edge $x_{i}y_{j}\in 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_{i}y_{j})+f_{6}(y_{j})=s+3p+1-2f(x_{i}y_{j})$

which produces a set $\\{p+s+3,p+s+3+2,p+s+3+4,\dots,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)$.

  6. (Equ-6)

Take a tree $T_{7}\cong 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\in[1,s]$,
$f_{7}(y_{j})=f(y_{j})+1=s+p-f(y_{j})$ for $j\in[1,t]$, and
$f_{7}(x_{i}y_{j})=2p-f(x_{i}y_{j})$ for each edge $x_{i}y_{j}\in E(T_{7})$.
The remainder proof is very similar with that in Equ-5.

  7. (Equ-7)

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\in[1,s]$,
$f_{8}(y_{j})=f(y_{t-j+1})$ for $j\in[1,t-1]$, and $f_{8}(y_{t})=0$. For each
edge $x_{k}y_{t}\in E(T_{8})$, we have

${\begin{split}&\quad f_{8}(x_{k})+f_{8}(y_{t})\\\
&=f_{8}(x_{k})+0=f_{8}(x_{k})+(p-1)~{}(\bmod~{}p-1)\\\
&=f(x_{k})+f(y_{t})~{}(\bmod~{}p-1)\\\
&=f(x_{k})+s+p-1-f(y_{1})~{}(\bmod~{}p-1)\\\
&=s+p-1-\big{[}f(y_{1})-f(x_{k})\big{]}~{}(\bmod~{}p-1)\\\
&=s-f(x_{k}y_{1}).\end{split}}$ (9)

Under modulo $(p-1)$,
$f_{8}(E(T_{8}))=\\{f_{8}(x_{i}y_{j})=f_{8}(x_{i})+f_{8}(y_{j})~{}(\bmod~{}p-1):x_{i}y_{j}\in
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)$.

  8. (Equ-8)

Let $T_{9}\cong 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\in[1,s]$, $f_{9}(y_{j})=f(y_{j})$ for $j\in[1,t-1]$, and $f_{9}(y_{t})=0$.
By the same way used in Equ-7, we can show $f_{9}$ is a harmonious labelling
of $T_{9}$ and $\max f_{9}(X)<\min f_{9}(Y)$.

  9. (Equ-9)

By Definition 13 we define a Dgemm-labelling $f_{10}$ of $T_{10}$ that holds
$T_{10}\cong T$ as following: $f_{10}(x_{i})=f(x_{i})$ for $i\in[1,s]$,
$f_{10}(y_{j})=f(y_{j})$ for $j\in[1,t]$, and
$f_{10}(x_{i}y_{j})=p-f(x_{i}y_{j})$ for each edge $x_{i}y_{j}\in E(T_{10})$.
We verify:

(i) each edge $x_{i}y_{j}$ corresponds an edge $x^{\prime}_{i}y^{\prime}_{j}$
such that

${\begin{split}f_{10}(x_{i}y_{j})&=p-f(x_{i}y_{j})=p-|f(x_{i})-f(y_{j})|\\\
&=|f(x^{\prime}_{i})-f(y^{\prime}_{j})|.\end{split}}$

(ii) for each edge $x_{i}y_{j}\in E(T_{10})$, $T_{10}$ has $p-1$ edges, and

${\begin{split}s(x_{i}y_{j})&=|f_{10}(x_{i})-f_{10}(y_{j})|-f_{10}(x_{i}y_{j})\\\
&=|f(x_{i})-f(y_{j})|-p+f(x_{i}y_{j})\\\ &=2f(x_{i}y_{j})-p\end{split}}$

distributes a set $\\{2-p,4-p,\dots,0,2,4,\dots,p-2\\}$ when $p$ is even.
Clearly, each edge $x_{i}y_{j}$ matches with another edge
$x^{\prime}_{i}y^{\prime}_{j}\in E(T_{10})$ holding
$s(x_{i}y_{j})+s(x^{\prime}_{i}y^{\prime}_{j})=0$. If $p$ is odd,
$s(x_{i}y_{j})$ induces another set $\\{2-p,4-p,\dots,-1,1,3,\dots,p-2\\}$, so
$s(x_{i}y_{j})+s(x^{\prime}_{i}y^{\prime}_{j})=0$ is true.

(iii) For each edge $x_{i}y_{j}\in E(T_{10})$, we have

${\begin{split}&\quad f_{10}(x_{i}y_{j})+|f_{10}(x_{i})-f_{10}(y_{j})|\\\
&=p-f(x_{i}y_{j})+|f_{10}(x_{i})-f_{10}(y_{j})|\\\ &=p.\end{split}}$

(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))\setminus\\{0\\}$, we have $f(x_{i}y_{j})=f(w)$ for
each edge $x_{i}y_{j}$ matching with a vertex $w$, which implies
$f_{10}(x_{i}y_{j})+f_{10}(w)=p-f(x_{i}y_{j})+f(w)=p$; conversely, each vertex
$w$ corresponds an edge $x_{i}y_{j}$ holding

$f_{10}(w)+f_{10}(x_{i}y_{j})=p-f(x_{i}y_{j})+f(w)=p,$

except the _singularity_ $f(x_{0})=\lfloor p\rfloor$.

We identify the vertices of $T_{1},T_{2},\dots,T_{10}$ with the same label
into one, and delete the multiple edges, the resulting graph is just the
desired multiple-tree matching partition $G=\oplus_{F}\langle
T_{i}\rangle^{10}_{1}$ with the v-proper labelling $f$ holding
$f(V(G))=[0,p-1]$ and the e-set labelling $F$ satisfying
$F(x_{i}y_{j})=\\{f_{k}(x_{i}y_{j}):~{}k\in[1,10]\\}$ for each edge
$x_{i}y_{j}\in E(G)$.

The labellings $f_{2},f_{3},\dots,f_{10}$ shown in the above proof can deduce
the set-ordered graceful labelling $f$, we omit the proof since the proof
methods are similarly with that in [20]. ∎

######  Theorem 5.

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.

###### Proof.

Suppose that $G$ has its own vertex bipartition $(X,Y)$ with
$X=\\{x_{i}:i\in[1,s]\\}$ and $Y=\\{y_{j}:j\in[1,t]\\}$ holding
$s+t=|V(G)|=p$. By the hypothesis of this theorem, $G$ admits a set-ordered
graceful labelling $f$ defined by $f(x_{i})=i-1$ for $i\in[1,s]$,
$f(y_{j})=s+j-1$ for $j\in[1,t]$ and $f(x_{i}y_{j})=f(y_{j})-f(x_{i})=s+j-i$
for each edge $x_{i}y_{j}\in E(G)$, such that $f(E(G))=[1,q]$.

We define a total set-labelling $F:V(G)\cup E(G)\rightarrow[0,p+q]^{2}$ as
follows: $F(x_{i})=[0,i-1]$ with $i\in[1,s]$, $F(y_{j})=[0,s+j-1]$ with
$j\in[1,t]$ and $F(x_{i}y_{j})=F(y_{j})\setminus F(x_{i})=[i,s+j-1]$ for each
edge $x_{i}y_{j}\in E(G)$. Clearly, $F(u)\neq F(w)$ for distinct elements
$u,w\in V(G)\cup E(G)$. Moreover, we have

${\begin{split}&\quad\\{|F(x_{i}y_{j})|:i\in[1,s],j\in[1,t]\\}\\\
&=\\{s+j-i:i\in[1,s],j\in[1,t]\\}\\\ &=\\{f(x_{i}y_{j}):x_{i}y_{j}\in
E(G)\\}\\\ &=f(E(G))=[1,q],\end{split}}$ (10)

and $F(x_{i})\subset 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^{\prime}:V(G)\cup E(G)\rightarrow[0,p+q]^{2}$ in
the following way: $F^{\prime}(x_{i})=[0,2(i-1)]$ with $i\in[1,s]$,
$F^{\prime}(y_{j})=[0,2(s+j)-3]$ with $j\in[1,t]$ and
$F^{\prime}(x_{i}y_{j})=F^{\prime}(y_{j})\setminus
F^{\prime}(x_{i})=[2(i-1)+1,2(s+j)-3]$ for each edge $x_{i}y_{j}\in E(G)$.
Furthermore, $F^{\prime}(x_{i})\subset F^{\prime}(y_{j})$ with
$2i-1=|F^{\prime}(x_{i})|<|F^{\prime}(y_{j})|=2(s+j)-2$, and
$\\{|F^{\prime}(x_{i}y_{j})|:i\in[1,s],j\in[1,t]\\}=f(E(G))=[1,2q-1]^{o}$.

The proof of the theorem is complete. ∎

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

The graceful graph $G$ shown in Fig.16(b) is a _graceful matching_ of $K_{5}$
having a v-set e-proper graceful labelling, and an odd-graceful graph $H$
shown in Fig.16(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 of graph
theory. Two graphs shown in Fig.16(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\circ
v$ if $N(u)\cap N(v)=\emptyset$ until, any pair of vertices $x,y$ of the last
graph $H^{*}$ hold $|N(u)\cap N(v)|\geq 1$. Clearly, $|E(H)|=|E(H^{*})|$. We
call $H^{*}$ a non-contracted graph, $H$ has a _non-contracted
$H^{*}$-kernel_. Two graphs shown in Fig.16(b) and (d) both have a non-
contracted $K_{5}$-kernel.

######  Lemma 6.

Each complete graph $K_{n}$ admits a v-set e-proper (odd-)graceful labelling.

###### Proof.

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})\rightarrow[0,M_{n}]$ with $F(x_{i})\cap F(x_{j})=\emptyset$ for
distinct $x_{i},x_{j}\in V(K_{n})$ and $f(E(K_{n}))=[1,M_{n}]$, where
$M_{n}=\frac{1}{2}n(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}\in V(K_{n})$ such that $M_{n}+n-a_{i,k_{i}}=M_{n}+k_{i}$ for
$a_{i,k_{i}}\in F(x_{i})=\\{a_{i,1},a_{i,2},\dots,a_{i,m_{i}}\\}$ with $1\leq
m_{i}\leq M_{n}$, we put $x_{i}$ into a set $S$ such that each $F(x_{j})$ with
$x_{j}\in\overline{S}=V(K_{n})\setminus S$ has no element of
$F(x_{j})=\\{a_{j,1},a_{j,2},\dots,a_{j,m_{j}}\\}$ with $1\leq m_{j}\leq
M_{n}$ holds $M_{n}+n-a_{j,l}=M_{n}+l$ true. We add an number
$b_{j}\in[M_{n}+1,M_{n}+n]\setminus\\{n-k_{i}:x_{i}\in S\\}$ to $F(x_{j})$ for
$x_{j}\in\overline{S}$, one-vs-one, thus, we get a v-set e-proper graceful
labelling $(F^{\prime},f^{\prime})$ of $K_{n+1}$ holding
$F^{\prime}:V(K_{n+1})\rightarrow[0,\frac{1}{2}n(n+1)]$ with
$F^{\prime}(x)\cap F^{\prime}(y)=\emptyset$ for distinct $x,y\in V(K_{n+1})$
and $f^{\prime}(E(K_{n+1}))=[1,\frac{1}{2}n(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
odd-graph admits a v-set e-proper graceful labelling. ∎

Lemma 6 enables us to obtain the following result:

######  Theorem 7.

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

Figure 16:  (a) $K_{5}$ admits a v-set e-proper graceful labelling; (b) $G$
admits a proper graceful labelling; (c) $K_{5}$ admits a v-set e-proper odd-
graceful labelling;; (d) $H$ admits a proper odd-graceful labelling.
Figure 17:  (a) $K_{5}$ admits a v-set e-proper felicitous labelling; (b) $L$
admits a felicitous labelling $f$ holding $f(uv)=f(u)+f(v)~{}(\bmod~{}10)$
true; (c) $K_{5}$ admits a v-set e-proper edge-magic total labelling;; (d) $T$
admits an edge-magic total labelling.

######  Lemma 8.

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

###### Proof.

Our proof is based on induction. 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^{\prime})$-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^{\prime}-m)$-graph, where $m=|N(x)|$,
and the neighbor set $N(x)$ collects all neighbors $x_{1},x_{2},\dots x_{m}$
of the vertex $x$. By the hypothesis of induction, the connected
$(p,q^{\prime}-m)$-graph $G-x$ can be split into a tree $H$ of $q^{\prime}-m$
vertices. Suppose that each vertex $x_{i}\in N(x)$ was split into
$x_{i,1},x_{i,2},\dots,x_{i,m_{i}}$ in $H$. We add new vertices
$x^{\prime}_{i}$ to $x_{i,1}$ by an edge $x^{\prime}_{i}x_{i,1}$ with
$i\in[1,m]$, the result graph is just a tree $H^{\prime}$ of $q^{\prime}-m+m$
vertices. Thereby, $H^{\prime}$ is the desired tree split from $G$, and the
leaves $x^{\prime}_{1},x^{\prime}_{2},\dots,x^{\prime}_{m}$ of $H^{\prime}$
are the result of splitting the vertex $x$ of $G$. ∎

By Lemma 8 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]$ ($f(E(G))=[1,2q-1]$) and $\bigcup_{u\in
V(G)}F(u)=[0,q]$ ($\bigcup_{u\in V(G)}F(u)\subset[0,2q-1]$), then it can be
split into a (an odd-)graceful tree_. For a connected $(p,q)$-graph $G$
holding $q\equiv 0,3~{}(\bmod~{}4)$, 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 [15], the authors show some Euler graphs admit v-set e-proper
$X$-labellings with $X\in\\{$graceful, odd-graceful, harmonious, $k$-graceful,
odd sequential, elegant, odd-elegant, felicitous, odd-harmonious, edge-magic
total$\\}$.

###  II-D Magic type of matching labellings

######  Definition 9.

∗ Let $f:V(G)\cup E(G)\rightarrow[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)|$,
then we call $f$ a _relaxed edge-magic total labelling_ (relaxed Emt-
labelling) of $G$ (called a _relaxed Emt-graph_) (see Fig.22(a)). $\Box$

######  Definition 10.

∗ Suppose that a $(p,q)$-graph $G$ admits a vertex labelling
$f:V(G)\rightarrow[0,2q-1]$ and an edge labelling
$g:E(G)\rightarrow[1,2p-1]^{o}$. If there is a constant $k$ such that
$f(u)+g(uv)+f(v)=k$ for each edge $uv\in 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.18(c), and Fig.21(a) and (b). $\Box$

######  Definition 11.

∗ Suppose that a $(p,q)$-graph $G$ admits a vertex labelling
$f:V(G)\rightarrow[0,2q-1]$ and an edge labelling
$g:E(G)\rightarrow[1,2q-1]^{o}$, and let $s(uv)=|f(u)-f(v)|-g(uv)$ for $uv\in
E(G)$. If (i) each edge $uv$ corresponds an edge $u^{\prime}v^{\prime}$ such
that $g(uv)=|f(u^{\prime})-f(v^{\prime})|$; (ii) and there exists a constant
$k^{\prime}$ such that each edge $xy$ has a matching edge
$x^{\prime}y^{\prime}$ holding $s(xy)+s(x^{\prime}y^{\prime})=k^{\prime}$
true; (iii) there exists a constant $k$ such that $f(uv)+|f(u)-f(v)|=k$ for
each edge $uv\in 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.21(a) and (b)) $\Box$

Figure 18:  A caterpillar admits: (a) a set-ordered graceful labellings; (b) a
set-ordered odd-graceful labellings; (c) an odd-edge-magic matching labelling
$(f,g)$; (d) an ee-difference odd-magic matching labelling $(f,g)$.

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

######  Definition 12.

∗ A total labelling $f:V(G)\cup E(G)\rightarrow[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$;

(ii) (ee-difference) each edge $uv$ matches with another edge $xy$ 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)|-g(uv)$ for $uv\in E(G)$, then there
exists a constant $k^{\prime}$ such that each edge $uv$ matches with another
edge $u^{\prime}v^{\prime}$ holding $s(uv)+s(u^{\prime}v^{\prime})=k^{\prime}$
(or $2(p+q)+s(uv)+s(u^{\prime}v^{\prime})=k^{\prime}$) 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))\subseteq f(E(G))$, or
$f(E(G))\subseteq 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^{\prime\prime}$ such that each
edge $uv$ matches with one vertex $w$ such that $f(uv)+f(w)=k^{\prime\prime}$,
and each vertex $z$ matches with one edge $xy$ such that
$f(z)+f(xy)=k^{\prime\prime}$, except the _singularity_
$f(x_{0})=\lfloor\frac{p+q+1}{2}\rfloor$;

(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 call $f$ a _6C-labelling_. $\Box$

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))\setminus X^{*}$ and $f(V(G))\cap g(V(H))=X^{*}$, where
$X^{*}=\\{\lfloor\frac{p+q+1}{2}\rfloor\\}$, we identify the vertex $x_{0}$ of
$G$ having $f(x_{0})=\lfloor\frac{p+q+1}{2}\rfloor$ with the vertex $w_{0}$ of
$H$ having $g(w_{0})=\lfloor\frac{p+q+1}{2}\rfloor$ into one to form a graph
$\odot_{1}\langle G,H\rangle$, called a _6C-complementary matching_. See
examples shown in Fig.19 and Fig.20.

Figure 19:  A caterpillar $T$ admitting a 6C-labelling has three
6C-complementary matchings $\odot_{1}\langle T,G_{i}\rangle$ with $i=1,2,3$.

######  Theorem 9.

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

###### Proof.

Suppose that $(X,Y)$ is the bipartition of vertex set of a tree $T$, where
$X=\\{x_{i}:i\in[1,s]\\}$ and $Y=\\{y_{j}:j\in[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\in[1,s]$ and
$g(y_{j})=s+j-1$ for $j\in[1,t]$, and furthermore each edge $x_{i}y_{j}\in
E(T)$ has its label $g(x_{i}y_{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\in V(T)$, and $f(x_{i}y_{j})=p-g(x_{i}y_{j})=p-|g(x_{i})-g(y_{j})|$ for
$x_{i}y_{j}\in E(T)$. Clearly,

$f(V(T))=[p,2p-1],\quad f(E(T))=[1,p-1].$ (11)

(i) (e-magic) Each edge $x_{i}y_{j}\in E(T)$ holds
$f(x_{i}y_{j})+|f(x_{i})-f(y_{j})|=p-g(x_{i}y_{j})+g(x_{i}y_{j})=p$ true.

(ii) (ee-difference) Each edge $x_{i}y_{j}\in E(T)$ matches with another edge
$x^{\prime}_{i}y^{\prime}_{j}\in E(T)$ holding
$p-g(x_{i}y_{j})=g(x^{\prime}_{i}y^{\prime}_{j})$ such that

${\begin{split}f(x_{i}y_{j})&=p-g(x_{i}y_{j})=g(x^{\prime}_{i}y^{\prime}_{j})\\\
&=|g(x^{\prime}_{i})-g(y^{\prime}_{j})|\\\
&=|p+g(x^{\prime}_{i})-[p+g(y^{\prime}_{j})]|\\\
&=|f(x^{\prime}_{i})-f(y^{\prime}_{j})|.\end{split}}$

(iii) (ee-balanced) Let $s(x_{i}y_{j})=|f(x_{i})-f(y_{j})|-f(x_{i}y_{j})$ for
$x_{i}y_{j}\in E(T)$, so

${\begin{split}s(x_{i}y_{j})&=|f(x_{i})-f(y_{j})|-f(x_{i}y_{j})\\\
&=|g(x^{\prime}_{i})-g(y^{\prime}_{j})|-p+g(x_{i}y_{j})\\\
&=2g(x_{i}y_{j})-p,\end{split}}$

which distributes $\\{2-p,4-p,\dots,-2,0,2,4,\dots,p-2\\}$ if $p$ is even, or
$\\{2-p,4-p,\dots,-3,-1,1,3,\dots,p-2\\}$ if $p$ is odd. Thereby, each edge
$x_{i}y_{j}\in E(T)$ matches with another edge
$x^{\prime\prime}_{i}y^{\prime\prime}_{j}\in E(T)$ such that
$s(x_{i}y_{j})+s(x^{\prime\prime}_{i}y^{\prime\prime}_{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 (11).

(v) (ve-matching) The form (11) 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^{\prime})=p$.

(vi) (set-ordered) $f_{\max}(X)<f_{\min}(Y)$ for the bipartition $(X,Y)$ of
$V(G)$ according to (11).

Hence, we claim that the labelling $f$ admits really a 6C-labelling defined in
Definition 12.

_The proof of “only if”_. Suppose that $T$ admits a 6C-labelling $h$. By the
property (iv) and $h(V(T)\cup 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\in V(T)$, which gives $h^{*}(V(T))=[0,p-1]$; and
$h^{*}(x_{i}y_{j})=p-h(x_{i}y_{j})$ for each edge $x_{i}y_{j}\in E(T)$, so
$h^{*}(E(T))=[1,p-1]$. The property (i) enables us to compute

${\begin{split}h^{*}(x_{i}y_{j})&=p-h(x_{i}y_{j})\\\
&=p-[p-|h(x_{i})-h(y_{j})|]\\\ &=|[h(x_{i})-p]-[h(y_{j})-p]|\\\
&=|h^{*}(x_{i})-h^{*}(y_{j})|,\end{split}}$ (12)

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

Figure 20:  (a) $G=\odot_{1}\langle T,G_{3}\rangle$ admits a 6C-labelling
defined in Definition 12, where $T$ and $G_{3}$ are shown in Fig.19; (b) an
_odd-even separable 6C-labelling_ ; (c) an odd-even separable 6C-labelling.

In Fig.20(a), $G=\odot_{1}\langle T,G_{3}\rangle$ is obtained by identifying
two singularities of $T$ and $G_{3}$ shown in Fig.19 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. Observe the 6C-labelling $\theta$ of
$G=\odot_{1}\langle T,G_{3}\rangle$, we can see such properties:
$\theta(E(G))\subset\theta(V(G))$; $13~{}(=p)$ is the common singularity of
two trees $T$ and $G_{3}$; and $\theta(uv)+|\theta(u)-\theta(v)|=13~{}(=p)$
for each edge $uv\in E(T)$, $\theta(xy)-|\theta(x)-\theta(y)|=13~{}(=p)$ for
each edge $xy\in E(G_{3})$. The particular properties of the 6C-labelling
$\theta$ of $G=\odot_{1}\langle T,G_{3}\rangle$ enables us to define a new
labelling. Fig.20(b) and Fig.20(c) show two _odd-even separable
6C-labellings_. Thereby, we can have the following results (the proofs of
these two results are similar with that in the proof of Theorem 9):

######  Corollary 10.

If a tree admits a set-ordered graceful labelling if and only if it admits an
odd-even separable 6C-labelling defined in Definition 12.

######  Corollary 11.

Suppose two trees $T$ and $H$ of $p$ vertices admit two set-ordered graceful
labellings. Then $G=\odot_{1}\langle T,H\rangle$ admits a 6C-labelling
$\theta$ with $\theta(uv)+|\theta(u)-\theta(v)|=p$ for each edge $uv\in E(T)$,
$\theta(xy)-|\theta(x)-\theta(y)|=p$ for each edge $xy\in E(H)$.

Similarly with Definitions 10 and 11, 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.21(c) and (d)).

######  Definition 13.

∗ Suppose that a $(p,q)$-graph $G$ admits a vertex labelling
$f:V(G)\rightarrow[0,p-1]$ and an edge labelling $g:E(G)\rightarrow[1,q]$, and
let $s(uv)=|f(u)-f(v)|-g(uv)$ for $uv\in E(G)$. If: (i) each edge $uv$
corresponds an edge $u^{\prime}v^{\prime}$ such that
$g(uv)=|f(u^{\prime})-f(v^{\prime})|$ (or
$g(uv)=p-|f(u^{\prime})-f(v^{\prime})|$); (ii) and there exists a constant
$k^{\prime\prime}$ such that each edge $xy$ has a matching edge
$x^{\prime}y^{\prime}$ holding
$s(xy)+s(x^{\prime}y^{\prime})=k^{\prime\prime}$ true; (iii) there exists a
constant $k$ such that $|f(u)-f(v)|+f(uv)=k$ for each edge $uv\in E(G)$; (iv)
there exists a constant $k^{\prime}$ such that each edge $uv$ matches with one
vertex $w$ such that $f(uv)+f(w)=k^{\prime}$, and each vertex $z$ matches with
one edge $xy$ such that $f(z)+f(xy)=k^{\prime}$, 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 Fig.21(c)
and (d)) $\Box$

Figure 21:  (a) An ee-difference odd-magic matching labelling; (b) an ee-
difference odd-magic matching labelling; (c) an ee-difference graceful-magic
matching labelling; (d) an ee-difference graceful-magic matching labelling.

###  II-E Inverse matchings

######  Definition 14.

[10] If there exists a constant $k\geq 0$, such that a $(p,q)$-graph $G$
admits a total labelling $f:V(G)\cup E(G)\rightarrow[1,p+q]$, each edge $uv\in
E(G)$ holds $|f(u)+f(v)-f(uv)|=k$ and $f(V(G)\cup E(G))=[1,p+q]$, 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]$. $\Box$

######  Definition 15.

[22] 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)\cup
E(G)\rightarrow[1,p+q]$, each edge $uv\in E(G)$ holds $h(uv)=|h(u)-h(v)|$ (or
$h(uv)=|h(u)-h(v)|=k$, or $h(uv)=h(u)+h(v)~{}(\bmod~{}q)$, or
$|h(u)+h(v)-h(uv)|=k$, or $h(u)+h(uv)+h(v)=k$), such that $h(V(G)\cup
E(G))=[1,p+q]$, $h(V(G))\setminus\\{a_{0}\\}=f(E(G))$ and
$h(E(G))=f(V(G))\setminus\\{a_{0}\\}$, where
$a_{0}=\lfloor\frac{p+q+1}{2}\rfloor$ is the singularity of two labellings $f$
and $h$. (see Fig.22(b) and (c)). $\Box$

Figure 22:  (a) A relaxed Emt-graph: (b) an edge-magic graceful labelling $f$;
(c) a ve-exchanged matching labelling of $f$ with the singularity 7.

By Definition 15, 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))\setminus X^{*}$ and $f(V(G))\setminus X^{*}=g(E(H))$
for $X^{*}=f(V(G))\cap 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.22(b) and (c), we have the _total-magic matching labelling_
$(f,f^{\prime})$ of a $(p,q)$-graph $G$ defined as: Two total labellings
$f:V(G)\cup E(G)\rightarrow[1,p+q]$ and $f^{\prime}:V(G)\cup
E(G)\rightarrow[1,p+q]$ such that $f(x)+f^{\prime}(x)=f(uv)+f^{\prime}(uv)$
for any vertex $x\in V(G)$ and edge $uv\in E(G)$. We can ask for $f$ (or
$f^{\prime}$) is an edge-magic total labelling, or an edge-magic graceful
labelling, or other labelling defined on $V(G)\cup E(G)$ and $[1,p+q]$.

###  II-F Self-matchings

For a partition $K_{n}=G\cup\overline{G}$ with the same vertex set
$V(K_{n})=V(G)=V(\overline{G})$ and edge-disjoint sets $E(G)\cap
E(\overline{G})=\emptyset$, we say that $G$ and $\overline{G}$ are
_complementary_ to each other, and we say $G$ is _self-complementary_ if $G$
is isomorphic to $\overline{G}$. So, we can consider this case as a _self-
matching_. Motivated from complete graph $K_{n}=G\cup\overline{G}$, we propose

######  Definition 16.

∗ Let $W$ be a universal graph, and two graphs $G,H$ of $W$ hold $E(G)\cap
E(H)=\emptyset$ and $V(W)=V(G)\cup V(H)$. If $E(W)=E(G)\cup E(H)$, we say $G$
and $H$ to be _complementary_ to each other based on $W$, and moreover we call
$G$ to be _self-matching_ (also, self-complementary) if $G$ is isomorphic to
$H$, that is, $G\cong H$. $\Box$

For example, if $T$ is isomorphic to $T^{\prime}$ in a universal graph
$\odot_{k}\langle T,T^{\prime}\rangle$, then we say that $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$ are 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)\cup E(G))+\min
f(V(G)\cup E(G))-f(x)$ for $x\in V(G)\cup 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)\rightarrow[0,2q-1]$, then there exists a connected graph $H$ admitting
a pan-odd-graceful labelling $g:V(H)\rightarrow[1,2q]$ such that
$\odot_{k}\langle G,H\rangle$ admits a _twin odd-graceful labelling_. For
showing this claim, we let $H\cong G$, and define $g(x)=f(x)+1$ for $x\in
V(H)=V(G)$, and then identify the vertices of $G$ and $H$ with the same label
into one for obtaining $\odot_{k}\langle G,H\rangle$. 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 $\odot_{k}\langle G,H\rangle$ is a
_self-matching_ when $G\cong H$ (see for examples $T$ and $G_{1}$ shown in
Fig.19).

######  Corollary 12.

If a tree $T$ admits a set-ordered graceful labelling, then we have a self-
matching $\odot_{1}\langle T,T\rangle$ admitting a 6C-labelling.

######  Corollary 13.

If a tree $T$ admits a set-ordered odd-graceful/odd-elegant labelling, then
there exists a self-matching $\odot_{1}\langle T,T\rangle$ admitting a twin
odd-graceful/odd-elegant labelling.

###### Proof.

By the hypothesis of the corollary, a tree $T$ has its own vertex bipartition
$(X,Y)$ with $X=\\{x_{i}:i\in[1,s]\\}$ and $Y=\\{y_{j}:j\in[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\in[1,s]$
and $f(y_{j})=s+j-1$ for $j\in[1,t]$, and
$f(x_{i}y_{j})=f(y_{j})-f(x_{i})=s+j-i$ for each edge $x_{i}y_{j}\in E(T)$.
Clearly, $f(X)<f(Y)$.

(1) We define a labelling $g$ of a copy $T^{\prime}$ of $T$ with
$(X^{\prime},Y^{\prime})=(X,Y)$ as: $g(x^{\prime}_{i})=2f(x_{i})=2(i-1)$ for
$i\in[1,s]$ and $g(y^{\prime}_{j})=2f(y_{j})-1=2(s+j)-3$ for $j\in[1,t]$,
immediately,

${\begin{split}g(x^{\prime}_{i}y^{\prime}_{j})&=|g(y^{\prime}_{j})-g(x^{\prime}_{i})|\\\
&=|2(s+j)-3-2(i-1)|\\\ &=2s+2(j-i)-1\\\ &=2(s+j-i)-1\\\
&=2f(x_{i}y_{j})-1.\end{split}}$

So, $g$ is an odd-graceful labelling of $T^{\prime}$, since
$g(X^{\prime})=\\{0,2,\dots,2(s-1)\\}$ is an even-set,
$g(Y^{\prime})=\\{2s-1,2s+1,\dots,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^{\prime\prime}$ of $T$ with $(X^{\prime\prime},Y^{\prime\prime})=(X,Y)$,
and make a _complementary labelling_ $g^{\prime\prime}$ of the odd-graceful
labelling $g^{\prime}$ by setting $g^{\prime\prime}(w)=g^{\prime}(w)+1$ for
$w\in V(T)$, clearly, $g^{\prime\prime}(E(T))=g^{\prime}(E(T))$. Moreover,
$g^{\prime\prime}(X)=[1,2s-1]^{o}$,
$g^{\prime\prime}(Y)=\\{2s,2s+2,\dots,2p-2\\}$, we can see

$g^{\prime\prime}(V(T))\cap g^{\prime}(V(T))=\\{2s-1\\}$

and

$g^{\prime\prime}(V(T))\cup g^{\prime}(V(T))=[0,2p-2].$

$T^{\prime\prime}$ is the _complementary matching_ of $T^{\prime}$. Thereby,
$\odot_{1}\langle T^{\prime},T^{\prime\prime}\rangle$ admits a twin odd-
graceful labelling and it is a self-matching.

(2) The proof of $\odot_{1}\langle T^{\prime},T^{\prime\prime}\rangle$
admitting a twin odd-elegant labelling is very similar with that of the above
(1), here, it takes $\bmod~{}2p-2$. ∎

###  II-G Set-ordered matchings

Suppose that a $(p,q)$-graph $G$ admits an $\varepsilon$-labelling
$f:V(G)\rightarrow[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\in X\\}<\min\\{f(y):~{}y\in Y\\}$

and we call $f$ a _set-ordered $\varepsilon$-labelling_ of $G$. As known, many
set-ordered $\varepsilon$-labellings have good properties, and have been
connected with other labellins equivalently ([16, 17, 18, 19, 20]). However,
determining a graph whether admits a set-ordered $\varepsilon$-labelling seems
to be not easy.

######  Theorem 14.

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

###### Proof.

Let $(X,Y)$ be the bipartition of vertices of $G$ such that each edge $uv\in
E(G)$ satisfies $u\in X$ and $v\in Y$. We take a copy of $G$, denoted as $H$
with its bipartition $(X^{\prime},Y^{\prime})=(X,Y)$. Suppose that $G$ admits
an $\varepsilon$-labelling $f$, so $H$ admits an $\varepsilon$-labelling
$f^{\prime}$ which is a copy of $f$. Now, we use an edge to join any vertex
$u$ of $G$ with its isomorphic vertex $u^{\prime}$ of $H$ for producing the
desired graph $G\ominus H$. Clearly, $G\ominus H$ is a bipartite
$(2p,2q+1)$-graph with bipartition $(X\cup Y^{\prime},X^{\prime}\cup Y)$. We
define a labelling $g$ as: $g(x)=f(x)$ for $x\in X$,
$g(y^{\prime})=f(y^{\prime})$ for $y^{\prime}\in Y^{\prime}$, $g(w)=f(w)+p$
for $w\in X^{\prime}$, and $g(z)=f(z)+p$ for $z\in Y$. Obviously,
$g_{\max}(X\cup Y^{\prime})<g_{\min}(X^{\prime}\cup Y)$, so $g$ is a set-
ordered $\varepsilon$-labelling of $G\ominus H$. ∎

If the graph $G\ominus H$ based on two disjoint graphs $G$ and $H$ admits a
set-ordered $\varepsilon$-labelling, we say $G$ to be a _set-ordered matching_
of $H$, and vice versa. It may be interesting to look for $G\not\cong H$ in
the set-ordered matching $G\ominus H$.

###  II-H Labellings with extremal conditions

######  Definition 17.

∗ Let $f:V(G)\rightarrow[0,q]$ be a labelling of a $(p,q)$-graph $G$, and let
$S_{um}(G,f)=\sum_{uv\in 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$. $\Box$

A tree $T$ shown in Fig.23 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.

  1. (Extr-1)

Each complete graph $K_{n}$ holds

${\begin{split}&\quad\min_{g}S_{um}(K_{n},g)=\max_{f}S_{um}(K_{n},f)\\\
&=\sum^{n-1}_{i=1}\sum^{n-i}_{k=1}k=\frac{1}{2}\sum^{n-1}_{i=1}(n-i+1)(n-i).\end{split}}$

  2. (Extr-2)

Let $G$ be a caterpillar, then

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

${\begin{split}\min_{f}S_{um}(G,f)&\leq\min_{g}S_{um}(G+e,g)\\\
&\leq\min_{f}S_{um}(G,f)+3.\end{split}}$

(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)\leq\min_{f}S_{um}(G,f).$

  3. (Extr-3)

If a disconnected graph $G$ has its components $G_{1},\dots,G_{m}$, then

$\max_{f}S_{um}(G,f)=\sum^{m}_{i=1}\max_{g}S_{um}(G_{i},g),$
$\min_{f}S_{um}(G,f)=\sum^{m}_{i=1}\min_{g}S_{um}(G_{i},g).$

  4. (Extr-4)

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)\leq\max_{h}S_{um}(G+uv,h)$.

  5. (Extr-5)

If $f$ and $f^{*}$ are dual to each other, then $S_{um}(G,f)=S_{um}(G,f^{*})$.

  6. (Extr-6)

For a tree $T$ of $p$ vertices, a _path_ $P_{p}$ of $p$ vertices and a _star_
$K_{1,p-1}$, we have

${\begin{split}p-1=&\min_{f}S_{um}(P_{p},f)\leq\min_{f}S_{um}(T,f)\\\
&\leq\min_{f}S_{um}(K_{1,p-1},f)=\frac{p^{2}}{4},\frac{p^{2}-1}{4}.\end{split}}$
(13)

  7. (Extr-7)

A difference-sum labelling $h$ of a tree $T$ holds
$\max_{f}S_{um}(T,f)=S_{um}(T,h)$ if and only if $h_{\max}(X)<h_{\min}(Y)$
with the partition $(X,Y)$ of $T$.

###### Proof.

Let $V(T)=X\cup Y$ with $X\cap Y=\emptyset$, where
$X=\\{x_{1},x_{2},\dots,x_{a}\\}$, $Y=\\{y_{1},y_{2},\dots,y_{b}\\}$. Suppose
$G$ admits a vertex labelling $f:V(T)\rightarrow[0,p-1]$ such that

${\begin{split}0=&f(x_{1})<f(x_{s})<\cdots f(x_{i})<f(x_{i+1})<\cdots\\\
&<f(x_{a})<f(y_{1})<f(y_{2})<\cdots f(y_{j})<\\\
&f(y_{j+1})<\cdots<f(y_{b})=p-1\end{split}}$ (14)

We exchange two labels $f(x_{i})$ and $f(y_{j})$ for some $i\neq j$. In other
word, we define another vertex labelling $g:V(T)\rightarrow[0,p-1]$ such that
$g(x_{i})=f(y_{j})$, $g(y_{j})=f(x_{i})$ and $g(w)=f(w)$ for $w\in
V(T)\setminus\\{x_{i},y_{j}\\}$. Clearly, there is no
$g_{\max}(X)<g_{\min}(Y)$. We claim

$S_{um}(T,f)>S_{um}(T,g).$ (15)

Let the set of neighbors of the vertex $x_{i}$ is denoted as
$N(x_{i})=\\{y_{i_{1}},y_{i_{2}},\dots y_{i_{m}}\\}$, the set of neighbors of
the vertex $y_{j}$ is written as $N(y_{j})=\\{x_{j_{1}},x_{j_{2}},\dots
x_{j_{n}}\\}$. We compute

${\begin{split}&|g(x_{i})-g(y_{i_{s}})|=|f(y_{j})-f(y_{i_{s}})|\leq
f(y_{i_{s}})-\\\ &f(y_{1})<f(y_{i_{s}})-f(x_{a})\leq
f(y_{i_{s}})-f(x_{i}),\end{split}}$ (16)

and

${\begin{split}&|g(y_{j})-g(x_{j_{t}})|=|f(x_{i})-f(x_{j_{t}})|\leq
f(x_{a})-\\\ &f(x_{j_{t}})<f(y_{1})-f(x_{j_{t}})\leq
f(y_{1})-f(x_{j_{t}}).\end{split}}$ (17)

Thereby, our assertion (15) holds true. ∎

  8. (Extr-8)

Max-min-sum Algorithm for computing $\max_{f}S_{um}(T,f)$.

Initiation. take a labelling $f_{0}:V(T)\rightarrow[0,p-1]$.

Iteration. For a optimal labelling $f_{k}:V(T)\rightarrow[0,p-1]$, find a pair
of vertices $x,y$, and check whether

$\sum_{x_{i}\in N(x)}|f_{k}(y)-f(x_{i})|\geq(\leq)\sum_{x_{i}\in
N(x)}|f_{k}(x)-f(x_{i})|$ (18)

and

$\sum_{y_{j}\in N(y)}|f_{k}(x)-f(y_{j})|\geq(\leq)\sum_{y_{j}\in
N(y)}|f_{k}(y)-f(y_{j})|.$ (19)

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\in
V(T)\setminus\\{x,y\\}$.

Termination. If no two vertices $x,y$ hold the forms (18) and (19), output the
labelling $f_{k}$ with $S_{um}(T,f_{k})=\max_{f}S_{um}(T,f)$.

Similarly, we can use $(\leq)$ in (18) and (19) to deal with the case
$\min_{f}S_{um}(T,f)$.

  9. (Extr-9)

If $T$ is a caterpillar, then we can compute the exact value of
$\min_{f}S_{um}(T,f)$.

###### Proof.

We show an algorithmic proof here. A caterpillar $T$ shown in Fig.10 contains
a path $P=u_{1}u_{2}\cdots 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\in[1,m_{i}]\\}$ with
$m_{i}\geq 0$ and $i\in[1,n]$. So, each vertex $u_{i}$ has its own degree
$\textrm{deg}(u_{1})=|L(u_{1})|+1=m_{1}+1$,
$\textrm{deg}(u_{j})=|L(u_{j})|+2=m_{j}+2$ with $j\in[2,n-1]$,
$\textrm{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})\cup\\{u_{2}\\}$, we set
$f(v_{1,j})=j-1$ with $j\in[1,m_{1}]$, $f(u_{1})=m_{1}$, $f(u_{2})=m_{1}+1$.
Compute the sum

${\begin{split}&\quad\sum^{m_{1}}_{j=1}|f(v_{1,j})-f(u_{1})|=\sum^{m_{1}}_{j=1}[m_{1}-f(v_{1,j})]\\\
&=1+2+\cdots+m_{1}=\frac{1}{2}(m_{1}+1)m_{1},\end{split}}$ (20)

and $|f(u_{1})-f(u_{2})|=m_{1}+1-m_{1}=1$.

Step 2. Notices that $u_{i}\in N(u_{i-1})$ with $i\in[2,n]$, so $f(u_{i})$ has
been defined well. For the vertices of
$N(u_{i})=L(u_{i})\cup\\{u_{i-1},u_{i+1}\\}$ with $i\in[2,n-1]$, we set
$f(v_{i,j})=f(u_{i})+j$ with $j\in[1,m_{i}]$, $f(u_{i+1})=f(u_{i})+m_{i}+1$.
Thereby, we have

${\begin{split}&\quad\sum^{m_{i}}_{j=1}|f(v_{i,j})-f(u_{i})|=\sum^{m_{i}}_{j=1}[f(u_{i})+j-f(u_{i})]\\\
&=1+2+\cdots+m_{i}=\frac{1}{2}(m_{i}+1)m_{i},\end{split}}$ (21)

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})\cup\\{u_{n-1}\\}$, we set
$f(v_{n,j})=f(u_{n})+j$ with $j\in[1,m_{n}]$. We get

${\begin{split}&\quad\sum^{m_{n}}_{j=1}|f(v_{n,j})-f(u_{n})|=\sum^{m_{n}}_{j=1}[f(u_{n})+j-f(u_{n})]\\\
&=1+2+\cdots+m_{n}=\frac{1}{2}(m_{n}+1)m_{n}.\end{split}}$ (22)

Therefore, we summarize the above sub-sums as

${\begin{split}S_{um}(T,f)&=\frac{1}{2}(m_{1}+1)m_{1}+1+\frac{1}{2}(m_{n}+1)m_{n}\\\
&\quad\sum^{n-1}_{k=2}\frac{1}{2}(m_{k}+1)m_{k}+\sum^{n}_{k=2}(m_{k}+1)\\\
&=n-m_{1}+\frac{1}{2}\sum^{n}_{k=1}m_{k}(m_{k}+3)\end{split}}$ (23)

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\in[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\in V(T)\setminus\\{v_{i,j},u_{i}\\}$. Now, we inspect the sum
$S_{um}(T,g)$. From

${\begin{split}&\quad|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\end{split}}$

and

${\begin{split}&\quad|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.\end{split}}$

we have

${\begin{split}&\quad|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})|.\end{split}}$

and

${\begin{split}&\quad\sum^{m_{i}}_{k=1}|g(u_{i})-g(v_{i,k})|\\\
&=|f(v_{i,j})-f(u_{i})|+\sum^{m_{i}}_{k=1,k\neq j}|f(v_{i,j})-f(v_{i,k})|\\\
&<\sum^{m_{i}}_{k=1}|f(u_{i})-f(v_{i,k})|\end{split}}$ (24)

We select $a_{i,0}=\lfloor\frac{m_{i}+1}{2}\rfloor$ with $i\in[1,n]$, thus,
each sum

${\begin{split}&\quad\sum^{m_{i}}_{k=1}|g(u_{i})-g(v_{i,k})|=\sum^{m_{i}}_{k=1,k\neq
a_{i,0}}|f(v_{i,a_{i,0}})-f(v_{i,k})|\\\
&=2(1+2+\cdots+a_{i,0})=a_{i,0}(1+a_{i,0})\end{split}}$

Clearly, $a_{i,0}(1+a_{i,0})<\sum^{m_{i}}_{j=1}|f(v_{i,j})-f(u_{i})|$ shown in
(21). Furthermore, using (18) and (19) checks the sum $S_{um}(T,g)$, we can
see $S_{um}(T,g)=\min_{f}S_{um}(T,f)$ true. This algorithm is correct and has
the complex of polynomial time. ∎

Figure 23:  A lobster admits four difference-sum labellings with the maximum
sum 84, sum 80, sum 72 and the minimum sum 20.

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._[6] 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.24), as follow:

######  Definition 18.

∗ Let $f:V(G)\rightarrow[0,q]$ be a labelling of a $(p,q)$-graph $G$, and let

$F_{um}(G,f)=\sum_{uv\in E(G)}[f(u)+f(v)~{}(\bmod~{}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.24) $\Box$

Figure 24:  As understanding Definition 18, a tree admits four felicitous-sum
labellings with the maximum sum 52, sum 52, the minimum sum 14 and the minimum
sum 14.

Observe Fig.23 and Fig.24, we can get two particular matching graphs
$A=\odot_{12}\langle G_{a},G_{d}\rangle$ with $G_{a},G_{d}$ shown in Fig.23
and $B=\odot_{9}\langle F_{b},F_{c}\rangle$ with $F_{b},F_{c}$ shown in
Fig.24. These two particular matching graphs enable us to define two new
concepts in Definition 19 and Definition 20, respectively.

######  Definition 19.

∗ 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)$, $G_{m}$ admits another difference-
sum labelling $f_{m}$ holding $S_{um}(G_{m},f_{m})=\min_{f}S_{um}(G,f)$. The
identifying graph $H=\odot_{k}\langle G_{M},G_{m}\rangle$ is called a _Max-min
difference-sum matching partition_ , moreover if $H=\odot_{p}\langle
G_{M},G_{m}\rangle$ holds $E(G_{M})\cap E(G_{m})=\emptyset$, we call $H$ a
_perfect Max-min difference-sum matching partition_. (See a perfect Max-min
difference-sum matching partition shown in 25(a)) $\Box$

######  Definition 20.

∗ 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)$, $H_{m}$ admits another felicitous-
sum labelling $h_{m}$ holding $F_{um}(H_{m},h_{m})=\min_{f}F_{um}(G,f)$. The
identifying graph $G=\odot_{k}\langle H_{M},H_{m}\rangle$ is called a _Max-min
felicitous-sum matching partition_ , and furthermore we call $G$ a _perfect
Max-min felicitous-sum matching partition_ if $G=\odot_{p}\langle
H_{M},H_{m}\rangle$ holds $E(H_{M})\cap E(H_{m})=\emptyset$. (See a perfect
Max-min felicitous-sum matching partition shown in 25(b)) $\Box$

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

Figure 25:  (a) A perfect Max-min difference-sum matching partition
$A=\odot_{12}\langle G_{a},G_{d}\rangle$, where $G_{a},G_{d}$ are shown in
Fig.23; (b) a perfect Max-min felicitous-sum matching partition
$B=\odot_{9}\langle F_{b},F_{c}\rangle$, where $F_{b},F_{c}$ are shown in
Fig.24.

##  III Matchings from proper total colorings

###  III-A 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 no 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
$\chi^{\prime\prime}(G)$. Let $f:V(G)\cup
E(G)\rightarrow[1,\chi^{\prime\prime}(G)]$ be a proper total coloring of $G$
with $\chi^{\prime\prime}(G)=|\\{f(x):x\in V(G)\cup E(G)\\}|$, and we call
such coloring $f$ to be a _total chromatic number pure_ (tcn-pure). Let
$d_{f}(uv)=f(u)+f(uv)+f(v)$, and

$B_{tol}(G,f)=\max_{uv\in E(G)}\\{d_{f}(uv)\\}-\min_{uv\in
E(G)}\\{d_{f}(uv)\\}.$

Determine a new parameter $\min_{f}B_{tol}(G,f)$ over all tcn-pure colorings
of $G$, and call $\min_{f}B_{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$.

In Fig.26, a complete bipartite graph $K_{2,3}$ admits six tcn-pure colorings:
each $h_{i}$ is the _dually total coloring_ (also, _matching total coloring_)
of $f_{i}$ with $i\in[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$.

Figure 26:  Six tcn-pure colorings of three complete bipartite graphs, in
which $h_{i}$ is the matching coloring of the tcn-pure coloring $f_{i}$ with
$i=1,2,3$.

There are some obvious facts:

  1. Tot-1.

Any path $P_{n}$ of $n$ vertices admits an edge-magic proper total coloring,
that is, $\min_{f}B_{tol}(P_{n},f)=0$.

  2. Tot-2.

A cycle $C_{n}$ of $n$ vertices admits an edge-magic proper total coloring if
$n\equiv 0~{}(\bmod~{}3)$, and admits an equitably total coloring, otherwise.

  3. Tot-3.

If $h$ is the _matching proper total coloring_ of a tcn-pure coloring $f$
defined as: $h(w)=[\max f(V(G)\cup E(G))+\min f(V(G)\cup E(G))]-f(w)$ for
$w\in V(G)\cup E(G)$, then,

${\begin{split}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),\end{split}}$

thus,

${\begin{split}B_{tol}(G,h)&=\max_{uv\in E(G)}\\{d_{h}(uv)\\}-\min_{uv\in
E(G)}\\{d_{h}(uv)\\}\\\ &=\max_{uv\in E(G)}\\{d_{f}(uv)\\}-\min_{uv\in
E(G)}\\{d_{f}(uv)\\}\\\ &=B_{tol}(G,f).\end{split}}$

It seems to be not easy to determine the exact value of the pan-bandwidth
total chromatic number $\min_{f}B_{tol}(G,f)$ for any given simple graph $G$,
since $\min_{f}B_{tol}(G,f)$ is related with the total chromatic number
$\chi^{\prime\prime}(G)$. There is a long standing conjecture: For any simple
graph $G$, the elements of $V(G)\cup E(G)$ can be colored with at most
$\Delta(G)+2$ colors so that no two adjacent or incident elements receive the
same color, also $\chi^{\prime\prime}(G)\leq\Delta(G)+2$, proposed by Behzad
in 1965 and Vizing in 1964. Unfortunately, there are less significant results
on the total labelling of graphs 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},\dots,m_{k}}$, and
join graph $G+H$ and so on. We, as exercise, verify a simple result.

######  Lemma 15.

Let $T$ be a tree, then the total chromatic number
$\chi\,^{\prime\prime}(T)=\Delta(T)+1$.

###### Proof.

The assertion is true if $T$ is a star $K_{1,n-1}$ or a double star $S_{s,t}$,
so assume $T\neq K_{1,n-1}$ and $T\neq S_{s,t}$. The following part of the
proof is by induction on orders of trees and constrained by diameter $D(T)\geq
4$.

_Case 1._ If there is a leaf $u$ of $T$ such that $\textrm{deg}_{T}(u)=2$, so
there is that $\textrm{deg}_{T}(v)=1$ in the neighbor set $N(u)=\\{v,w\\}$.
Let $T_{1}=T-v$, then $\Delta(T_{1})=\Delta(T)$. We take a proper
$\chi\,^{\prime\prime}(T_{1})$-total coloring $f$ of $T_{1}$, hence, set
$f\,^{\prime}(v)=f(uw)$, $f\,^{\prime}(uv)=f(w)$ and $f\,^{\prime}(x)=f(x)$
for $x\in[E(T)\cup V(T)]\setminus\\{v,uv\\}$. It is clear that the coloring
$f\,^{\prime}$ is a proper $\chi\,^{\prime\prime}(T_{1})$-total coloring of
$T$ such that
$\chi\,^{\prime\prime}(T)=\chi\,^{\prime\prime}(T_{1})=\Delta(T_{1})+1=\Delta(T)+1$.

_Case 2._ If $\textrm{deg}_{T}(u)\geq 3$, we take a vertex $u$ of $T$ with its
neighbor set $N(u)=\\{u_{1},u_{2},\dots,u_{k},u_{0}\\}$, where
$k=\textrm{deg}_{T}(u)-1$, $u_{i}$ is a leaf of $T$ with $i\in[1,k]$ and
$\textrm{deg}(u_{0})\geq 2$, and let $T_{2}=T-u_{1}$.

Now, we take a proper $\chi\,^{\prime\prime}(T_{2})$-total coloring $g$ of
$T_{2}$ having $\chi\,^{\prime\prime}(T_{2})=\Delta(T_{2})+1$, and then build
a proper $\chi\,^{\prime\prime}(T)$-total coloring $g^{\prime}$ of $T$ as: Let
$C=[1,\chi\,^{\prime\prime}(T_{2})]$ be the color set of $T_{2}$ under $g$ and
$C(g,w)=\\{g(xw):xw\in E(T_{2})\\}\cup\\{g(w)\\}$ for $w\in(T_{2})$.

_Case 2.1._ If $\Delta(T_{2})=\Delta(T)$, then $|C(g,u)|\leq\Delta(T_{2})$, so
there is a color $\alpha\in C$ but $\alpha\notin C(g,u)$. We have that
$g^{\prime}(v)=g(u_{0})$, $g^{\prime}(uv)=\alpha$ and $g^{\prime}(x)=g(x)$ for
$x\in[E(T)\cup V(T)]\setminus\\{v,uv\\}$. Hence,
$\chi\,^{\prime\prime}(T)=\chi\,^{\prime\prime}(T_{2})=\Delta(T_{2})+1=\Delta(T)+1$.

_Case 2.2._ If $\Delta(T_{2})=\Delta(T)-1$, so
$\chi\,^{\prime\prime}(T_{2})=\Delta(T_{2})+1=\Delta(T)$, and then we set
$g^{\prime}(v)=g(u_{0})$, $g^{\prime}(uv)=\chi\,^{\prime\prime}(T_{2})+1$ and
$g^{\prime}(x)=g(x)$ for $x\in(E(T)\cup V(T))\setminus\\{v,uv\\}$. Therefore,

$\chi\,^{\prime\prime}(T)=\chi\,^{\prime\prime}(T_{2})+1=\Delta(T)+1.$ (25)

The proof of this lemma is finished. ∎

######  Lemma 16.

A star also is a complete graph $K_{1,n}$ with its vertex set
$V(K_{1,n})=\\{x_{0},x_{1},x_{2},\dots,x_{n}\\}$ and edge set
$E(K_{1,n})=\\{x_{i}x_{0}:i\in[1,n]\\}$. Then $K_{1,n}$ admits an edge-magic
proper total coloring for even $n$, that is, $\min_{f}B_{tol}(K_{1,n},f)=0$,
or an equitably proper total coloring for odd $n$.

###### Proof.

Clearly, $\Delta(K_{1,n})=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_{0}x_{i})=1+i$ and
$f(x_{i})=n+2-i$ with $i\in[1,n]$. We can compute
$\chi^{\prime\prime}(K_{1,n})=\Delta(K_{1,n})+1=n+1$, and
$d_{f}(u_{0}u_{i})=f(x_{0})+f(x_{0}x_{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_{0}x_{i})=1+i$ with $i\in[1,n]$,
$f(x_{i})=n+2-i$ with $i\in[1,n]$ and $i\neq(n+1)/2$, and
$f(x_{(n+1)/2})=n+1-(n+1)/2$. Clearly,
$\chi^{\prime\prime}(K_{1,n})=\Delta(K_{1,n})+1=n+1$,
$d_{f}(u_{0}u_{i})=f(x_{0})+f(x_{0}x_{i})+f(x_{i})=1+1+i+n-i=n+2$ with
$i\in[1,n-1]$ and $i\neq(n+1)/2$, and

$d_{f}(u_{0}u_{(n+1)/2})=f(x_{0})+f(x_{0}x_{(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. ∎

######  Lemma 17.

A bi-star $S_{m,n}$ has its own vertex set
$V(S_{m,n})=\\{x_{0},x_{1},x_{2},\dots,x_{m}\\}\cup\\{y_{0},y_{1},y_{2},\dots,y_{n}\\}$
and edge set
$E(S_{m,n})=\\{x_{i}x_{0}:i\in[1,m]\\}\cup\\{y_{j}y_{0}:j\in[1,n]\\}\cup\\{x_{0}y_{0}\\}$.
Then $S_{m,n}$ admits an equitably proper total coloring.

###### Proof.

Without loss of generality, assume that $m\geq 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_{0}x_{i})=1+i$ with $i\in[1,2a]$, $g(x_{0}y_{0})=2a+2$,
$g(y_{0})=2$, $g(x_{i})=2a+3-i$ with $i\in[1,2a]$ and $i\neq a+1$,
$g(x_{a+1})=g(x_{a+2})$; if $a\neq b$, $g(y_{0}y_{j})=2+j$ with $j\in[1,2b]$,
$g(y_{j})=2a+1-j$ with $i\in[1,2b]$; if $a=b$, $g(y_{0}y_{j})=2+i$ with
$j\in[1,2b-1]$, $g(y_{0}y_{2b})=1$, $g(y_{2b})=2a+2$, $g(y_{j})=2a+1-j$ with
$j\in[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})\rightarrow[1,2a+2]=[1,\Delta(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 with that of the case $m=2a$ and $n=2b$. We
claim that $S_{m,n}$ admits an equitably proper total coloring. ∎

######  Theorem 18.

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

###### Proof.

A spider $S_{m_{1},m_{2},\dots,m_{n}}$ has $n$ paths (called _legs_)
$P_{i}=u_{i,1}u_{i,2}\cdots u_{i,m_{i}}$ with $m_{i}\geq 1$ for $i\in[1,n]$,
and a body $u_{0}$ is joined with $u_{i,1}$ by an edge $u_{0}u_{i,1}$ with
$i\in[1,n]$. As $n$ is even, the star $K_{1,n}$ having its vertex set
$\\{u_{0},u_{1,1},u_{2,1},\dots,u_{n,1}\\}$ and edge set
$\\{u_{0}u_{i,1}:i\in[1,n]\\}$ admits an edge-magic proper total coloring $f$
by Lemma 16. So, $f(u_{0})=1$, $f(u_{0}u_{i,1})=1+i$ and $f(u_{i,1})=n+2-i$
with $i\in[1,n]$. Notice that

${\begin{split}d_{f}(u_{0}u_{i,1})&=f(u_{0})+f(u_{0}u_{i,1})+f(u_{i,1})\\\
&=1+n+2-i+1+i\\\ &=n+3\end{split}}$ (26)

with $i\in[1,n]$. Clearly,
$\chi^{\prime\prime}(K_{1,n})=n+1=\Delta(K_{1,n})+1$.

We expend the coloring $f$ to the spider $S_{m_{1},m_{2},\dots,m_{n}}$ by
coloring a leg $P_{i}=u_{i,1}u_{i,2}\cdots u_{i,m_{i}}$ as:
$f(u_{i,1}u_{i,2})=1$ and $f(u_{i,2})=f(u_{0}u_{i,1})=1+i$, which shows
$d_{f}(u_{i,1}u_{i,2})$ obeys (26); next, $f(u_{i,2}u_{i,3})=f(u_{i,1})=n+2-i$
and $f(u_{i,3})=f(u_{0})=1$, so $d_{f}(u_{i,2}u_{i,3})$ obeys (26) too. Go on
in this way, we have shown that the spider $S_{m_{1},m_{2},\dots,m_{n}}$
admits $f$ as its a proper total coloring such that

$\chi^{\prime\prime}(S_{m_{1},m_{2},\dots,m_{n}})=n+1=\Delta(S_{m_{1},m_{2},\dots,m_{n}})+1$

and

$B_{tol}(S_{m_{1},m_{2},\dots,m_{n}},f)=0.$

The proof of the theorem is complete. ∎

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

######  Lemma 19.

For any tree $T$, we can add a leaf $u$ to $T$ with $u\not\in V(T)$ such that
the tree $T+uv$ with $v\in V(T)$ holds
$\min_{f}B_{tol}(T,f)=\min_{g}B_{tol}(T+uv,g)$.

See a generalized spider admitting an edge-magic proper total coloring shown
in Fig.28 for understanding Lemma 19, which can help us to design random
Topsnut-gpws or _rooted Topsnut-gpw_.

Figure 27:  Left is $K_{1,6}$, Right is a spider $S_{1,3,3,4,3,5}$.
Figure 28:  A generalized spider $H$ admits an edge-magic proper total
coloring, where $K_{1,6}$ is the root, so $H$ is called a rooted Topsnut-gpw.

######  Theorem 20.

Each tree admits an equitable proper total coloring.

###### Proof.

We consider a tree $T$ having diameter $D_{ia}(T)\geq 4$ since $T$ with
$D_{ia}(T)\leq 3$ follows Lemma 16 and Lemma 17. Select a vertex $u$ of $T$
such that the neighbor set $N(u)=\\{u_{1},u_{2},\dots,u_{k},u_{0}\\}$, where
$k=\textrm{deg}_{T}(u)-1$, $\textrm{deg}_{T}(u_{i})=1$ with $i\in[1,k]$ and
$\textrm{deg}(u_{0})\geq 2$. Assume that $k+2\leq\Delta(T)$.

Suppose that a proper total coloring $f$ holds
$B_{tol}(T,f)=\min_{g}B_{tol}(T,g)=1$. Notice that
$\chi^{\prime\prime}(T)=\Delta(T)+1$, there exists a vertex $w$ of $T$ such
that $\textrm{deg}_{T}(w)=\Delta(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})\neq f(u_{i}u)$ with $i\in[1,k]$, then we set
$f(ux)=f(u_{0})$, $f(x)=f(u_{0}u)$. Obviously, $|d_{f}(u_{0}u)-d_{f}(ux)|=0$.

_Case 2._ If $f(u_{j})\neq f(u_{i}u)$ for some $i\neq j$, then we set
$f(ux)=f(u_{j})$, $f(x)=f(u_{j}u)$, thus, $|d_{f}(u_{j}u)-d_{f}(ux)|=0$.

_Case 3._ Without loss of generality, we assume $f(u_{0})=f(u_{j}u)$ for some
$j$, and $f(u_{i})=f(u_{i^{\prime}}u)$ for each $i\in[1,k]$. We have a color
set

$S=\\{f(u_{0}u),f(u_{1}u),f(u_{2}u),\dots,f(u_{k}u),f(u)\\}$

such that $|S|=\Delta(T)$. We can arrange

$f(u_{0}u)<f(u_{1}u)<f(u_{2}u)<\dots<f(u_{k}u).$

By $\chi^{\prime\prime}(T)=\Delta(T)+1$, the color set $|f(V(T)\cup
E(T))|=\Delta(T)+1$, so there exists one color $c\in f(V(T)\cup E(T))\setminus
S$. So, $f(u_{j}u)<c<f(u_{j+1}u)$.

_Case 3.1._ If $f(u)<f(u_{j}u)$ or $f(u_{j+1}u)<f(u)$, immediately, we have
$c-f(u_{j}u)=1$ and $f(u_{j+1}u)-c=1$, $f(u_{j+1}u)-f(u_{j}u)=2$. We set
$f(ux)=c$, $f(x)=f(u_{j}u)$, and furthermore

${\begin{split}&\quad|d_{f}(u_{j+1}u)-d_{f}(ux)|\\\
&=|[f(u_{j+1})+f(u_{j+1}u)+f(u)]\\\ &\quad-[f(x)+f(ux)+f(u)]|\\\
&=|f(u_{j+1})-f(u_{j}u)+f(u_{j+1}u)-c|\\\ &=|c+1-2-c|=1.\end{split}}$ (27)

_Case 3.2._ If $f(u_{j}u)<f(u)<c<f(u_{j+1}u)$, according to
$\chi^{\prime\prime}(T)=\Delta(T)+1$, we get $f(u)-f(u_{j}u)=1$, $c-f(u)=1$
and $f(u_{j+1}u)-c=1$. We let $f(ux)=c$, $f(x)=f(u_{j+1}u)$, and moreover we
can compute

${\begin{split}&\quad|d_{f}(u_{j+1}u)-d_{f}(ux)|\\\
&=|[f(u_{j+1})+f(u_{j+1}u)+f(u)]\\\ &\quad-[f(x)+f(ux)+f(u)]|\\\
&=|f(u_{j+1})+f(u_{j+1}u)-f(u_{j+1}u)-c|\\\ &=|c+1-c|=1.\end{split}}$ (28)

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$. ∎

According to Lemma 16 and Lemma 17 we claim that a tree $T$ admits an edge-
magic proper total coloring if its maximum degree $\Delta(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) Planarity of $G$, and so on. In Fig.29, we can get
a text-based password

${\begin{split}D_{vev}=&5231631721721635272635235145163\\\
&5217217235235217213613.\end{split}}$

Clearly, no way by $D_{vev}$ to reconstruct the non-planar rooted Topsnut-gpw
$G$ shown in Fig.29.

Figure 29:  A non-planar rooted Topsnut-gpw $G$ with maximum degree $6$ and an
edge-magic proper total coloring.

###  III-B Consecutive integer sets of complete graphs with proper total
colorings

A complete graph $K_{m}$ admits a proper total coloring $f$ with
$\chi^{\prime\prime}(K_{m})=m+1$ for even $m$, and
$\chi^{\prime\prime}(K_{m})=m$ for odd $m$. Let

$f^{*}(E(K_{m}))=\\{f(u)+f(uv)+f(v):uv\in E(K_{m})\\}.$

Hence, we guess: $f^{*}(E(K_{m}))$ is a consecutive integer set $[a,b]$ (see
Fig.30).Four proper total colorings $h$ shown in Fig.31 match with four proper
total colorings $f$ shown in Fig.30, 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\in
E(T)\\}$ is a consecutive integer set.

Figure 30:  Several examples for illustrating the consecutive integer sets of
proper total colorings.
Figure 31:  Four proper total colorings of four complete graphs match with
four total colorings of four complete graphs shown in Fig.30.

In Fig.26, we have $f^{*}_{1}(E(K_{2,3}))=\\{f_{1}(u)+f_{1}(uv)+f_{1}(v):uv\in
E(K_{2,3})\\}=[6,8]$,
$f^{*}_{2}(E(K_{2,4}))=\\{f_{2}(u)+f_{2}(uv)+f_{2}(v):uv\in
E(K_{2,4})\\}=[6,9]$ and
$f^{*}_{3}(E(K_{3,3}))=\\{f_{3}(u)+f_{3}(uv)+f_{3}(v):uv\in
E(K_{3,3})\\}=[6,10]$, and furthermore the matching colorings
$h_{1},h_{2},h_{3}$ distribute

$h^{*}_{1}(E(K_{2,3}))=\\{h_{1}(u)+h_{1}(uv)+h_{1}(v):uv\in
E(K_{2,3})\\}=[7,9]$,

$h^{*}_{2}(E(K_{2,4}))=\\{h_{2}(u)+h_{2}(uv)+h_{2}(v):uv\in
E(K_{2,4})\\}=[9,12]$ and

$h^{*}_{3}(E(K_{3,3}))=\\{h_{3}(u)+h_{3}(uv)+h_{3}(v):uv\in
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})\cup
E(K_{m,n})\rightarrow[1,\chi^{\prime\prime}(K_{m,n})]$ such that
$g^{*}(E(K_{m,n}))=\\{f(u)+f(uv)+f(v):uv\in E(K_{m,n})\\}$ is a consecutive
integer set $[a,b]$.

###  III-C New proper total colorings

We use the successful experience of graph labelling definitions to propose new
proper total colorings. Let $f:V(G)\cup E(G)\rightarrow[1,k]$ be a proper
total coloring of a graph $G$. If each edge $uv$ holds $f(uv)=|f(u)-f(v)|$, 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
$\chi^{\prime\prime}_{ved}(G)$, called the _ve-matching difference total
chromatic number_. See two ve-matching difference total colorings shown in
Fig.32(a) and (b). We can see
$\chi^{\prime\prime}(G)\leq\chi^{\prime\prime}_{ved}(G)$, in general.

For a proper total coloring $h:V(G)\cup E(G)\rightarrow[1,m]$, if each edge
$uv$ holds $h(uv)=h(u)+h(v)$, 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 $\chi^{\prime\prime}_{ves}(G)$, called the _ve-
matching sum total chromatic number_. Two ve-matching sum total colorings are
shown in Fig.32(c) and (d). Clearly,
$\chi^{\prime\prime}(G)\leq\chi^{\prime\prime}_{ves}(G)$.

Figure 32:  Four ve-matching difference/sum total colorings.

###  III-D New parameters on proper vertex colorings

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

$B_{sub}(G,f)=\sum_{xy\in E(G)}|f(x)-f(y)|,$ (29)

and try to determine $\min_{f}B_{sub}(G,f)$ and $\max_{f}B_{sub}(G,f)$.
Clearly, if $G$ is a bipartite graph, then

$\min_{f}B_{sub}(G,f)=\max_{f}B_{sub}(G,f)=|E(G)|.$

If a connected graph $G$ holds

$\min_{f}B_{sub}(G,f)<M<\max_{f}B_{sub}(G,f)$ (30)

for each $M$, there exist 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.33).

Figure 33:  The graph $C+uv$ admits a group of consecutive difference proper
vertex colorings, which forms a _Topsnut-matching chain_.

Let $g:V(G)\rightarrow[1,k]$ be a proper vertex coloring of a graph $G$ with
$k=\chi(G)$. We define another parameter

$B_{sum}(G,g)=\sum_{xy\in E(G)}[f(x)+f(y)]$ (31)

and try to compute two extremal values $\min_{g}B_{sum}(G,g)$ and
$\max_{h}B_{sum}(G,h)$. If $G$ has a proper vertex coloring $g_{Q}$ for each
$Q$ satisfying

$\min_{g}B_{sum}(G,g)<Q<\max_{h}B_{sum}(G,h)$ (32)

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.34).

Observed that the labeled graph (a) in Fig.33 is equal to the labeled graph
(a) in Fig.34, so we ask for a problem: _If a proper vertex coloring $h^{*}$
holds $B_{sub}(G,h^{*})=\min_{f}B_{sub}(G,f)$, then $h^{*}$ holds
$B_{sum}(G,h^{*})=\min_{f}B_{sum}(G,f)$ too_.

Figure 34:  The graph $C+uv$ admits a group of consecutive sum proper vertex
colorings, which forms a _Topsnut-matching chain_.

For making Topsnut-gpes 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._ [31] show a famous
conjecture: “For every graph $G$ with no $K_{2}$ or $C_{5}$ component, then
the adjacent strong edge chromatic number
$\chi^{\prime}_{as}(G)\leq\Delta(G)+2$.” (ii) Zhang _et al._ [30] introduced a
concept of adjacent vertex distinguishing total coloring (AVDTC), and show a
conjecture: Let $G$ be a simple graph with order $n\geq 2$; then $G$ has its
AVDTC chromatic number $\chi^{\prime\prime}_{as}(G)\leq\Delta(G)+2$. (iii)
Yang _et al._ propose the following conjectures: ([28, 29] conjecture: Every
simple graph $G$ having at least a $4$-avdtc holds
$\chi^{\prime\prime}_{4as}(G)\leq\Delta(G)+4$.

##  IV Graph labelling analysis

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

###  IV-A Pan-labellings

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

For a $(p,q)$-graph $G$, a pan-labelling $f$ is defined on a domain
$S\subseteq V(G)\cup E(G)$, and yields the main-range $f(S)=\\{f(x):x\in
S\\}$. Furthermore, $f$ gives a mapping $f^{\prime}$ based on the edge-domain
$E(G)$ and produces the derivative range
$f^{\prime}(E(G))=\\{f^{\prime}(uv)=F(f(u),f(v)):uv\in 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 21 is one of generalized labelling definitions for connecting more
well-defined graph labellings.

######  Definition 21.

[23] 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. There are
the following restrict conditions:

  1. Seq-1.

A vertex mapping $f:V(G)\rightarrow A_{M}$ such that $f(u)\neq f(v)$ for
distinct $u,v\in V(G)$.

  2. Seq-2.

A total mapping $f:V(G)\cup E(G)\rightarrow A_{M}\cup B_{q}$ such that
$g(x)\neq g(y)$ for distinct $x,y\in V(G)\cup E(G)$.

  3. Seq-3.

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

  4. Seq-4.

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

  5. Seq-5.

$f(E(G))\subseteq B_{q}$.

  6. Seq-6.

$f(V(G)\cup E(G))\subseteq A_{M}\cup B_{q}$.

  7. Seq-7.

$f(V(G))\subseteq A_{M}$ and $f(E(G))=B_{q}$.

  8. Seq-8.

$f(V(G))=A_{M}$ and $f(E(G))=B_{q}$.

We call $f$: (1) a _sequence- $(A_{M},B_{q})$ labelling_ of $G$ if Seq-1 and
Seq-3 hold true; (2) a _full sequence- $(A_{M},B_{q})$ labelling_ if Seq-2,
Seq-4 and Seq-7 hold true; (3) a _graceful sequence- $(A_{M},B_{q})$
labelling_ if Seq-1, Seq-3 and Seq-8 hold true; (4) a _total sequence-
$(A_{M},B_{q})$ labelling_ if Seq-2 and Seq-4 hold true; (5) a _sequence-
$(A_{M},B_{q})$ $F$-total graceful labelling_ if Seq-2, Seq-4 and Seq-8 hold
true simultaneously. $\Box$

If two sets $A_{M}=\\{a_{i}\\}_{1}^{M}$ and $B_{q}=\\{b_{j}\\}_{1}^{q}$
defined in Definition 21 correspond a graph labelling admitted by graphs, we
say $(A_{M},B_{q})$ a _graph-realized sequence matching_.

###  IV-B Topsnut-matchings labeled by graphs

Let $\\{G_{i}\\}^{m}_{1}$ be a set of graphs $G_{1},G_{2},\dots,G_{m}$, where
$G_{k}$ is labeled by a labelling $g_{k}$ with $k\in[1,m]$, and a
$(p,q)$-graph $H$ be a _base_.

$\ast$ Addition and subtraction. Define a mapping
$f:V(H)\rightarrow\\{G_{i}\\}^{m}_{1}$, and an induced edge label
$f^{\prime}(uv)=F(i,j)$ for each edge $uv\in 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”.

  1. Gr-1.

If $f^{\prime}(E(H))=\\{|i-j|:uv\in E(H)\\}=[1,q]$, we call $H(f,f^{\prime})$
a _graceful graph-set labelling_ (graceful gs-labelling). And, we have a
_graceful gs-compound_ $G=\langle\\{G_{i}\\}^{m}_{1};H(f,f^{\prime})\rangle$
obtained by joining $G_{i}=f(u)$ with $G_{j}=f(v)$ for each edge $uv\in E(H)$.
In general, the number of such graphs
$G=\langle\\{G_{i}\\}^{m}_{1};H(f,f^{\prime})\rangle$ is not one.

  2. Gr-2.

If $f^{\prime}(E(H))=\\{|i-j|:uv\in E(H)\\}=[1,2q-1]^{o}$, then
$H(f,f^{\prime})$ is an _odd-graceful graph-set labelling_ (odd-graceful gs-
labelling), and we have an _odd-graceful gs-compound_
$G=\langle\\{G_{i}\\}^{m}_{1};H(f,f^{\prime})\rangle$.

  3. Gr-3.

If $f^{\prime}(E(H))=\\{i+j~{}(\bmod~{}q):uv\in E(H)\\}=[0,q-1]$, we have a
_felicitous graph-set labelling_ (felicitous gs-labelling) $H(f,f^{\prime})$,
and a _felicitous gs-compound_
$G=\langle\\{G_{i}\\}^{m}_{1};H(f,f^{\prime})\rangle$.

  4. Gr-4.

If $f^{\prime}(E(H))=\\{i+j~{}(\bmod~{}2q-1):uv\in E(H)\\}=[0,2q-3]^{o}$, we
have an _odd-elegant graph-set labelling_ (felicitous gs-labelling)
$H(f,f^{\prime})$, and an _odd-elegant gs-compound_
$G=\langle\\{G_{i}\\}^{m}_{1};H(f,f^{\prime})\rangle$.

$\ast$ Magic type. Define a mapping $f:V(H)\cup
E(H)\rightarrow\\{G_{i}\\}^{m}_{1}$, such that $f(u)=G_{i}$, $f(v)=G_{j}$ and
$f(uv)=G_{k}$ for each edge $uv\in E(H)$.

  1. Mg-1.

If there exists a constant $k^{*}$, such that $i+k+j=k^{*}$ for each edge
$uv\in E(H)$, we call $f$ an _edge-magic total graph-set labelling_ (edge-
magic total gs-labelling), the graph
$G=\langle\\{G_{i}\\}^{m}_{1};H(f)\rangle$ is obtained by joining $G_{i}$ with
$G_{k}$ and joining $G_{k}$ with $G_{j}$ for each edge $uv\in E(H)$ is called
an _edge-magic total gs-compound_.

  2. Mg-2.

If there exists a constant $k^{*}$ such that $|i-k+j|=k^{*}$ for each edge
$uv\in E(H)$, we call $f$ an _edge-magic total graceful graph-set labelling_
(edge-magic total graceful gs-labelling), the graph
$G=\langle\\{G_{i}\\}^{m}_{1};H(f)\rangle$ is obtained by joining $G_{i}$ with
$G_{k}$ and joining $G_{k}$ with $G_{j}$ for each edge $uv\in E(H)$ is called
an _edge-magic total graceful gs-compound_.

  3. Mg-3.

If there exists a constant $k^{*}$ such that $k+|i-j|=k^{*}$ for each edge
$uv\in E(H)$, we call $f$ an _edge-magic graceful total graph-set labelling_
(edge-magic graceful total gs-labelling), the graph
$G=\langle\\{G_{i}\\}^{m}_{1};H(f)\rangle$ is obtained by joining $G_{i}$ with
$G_{k}$ and joining $G_{k}$ with $G_{j}$ for each edge $uv\in E(H)$ is called
an _edge-magic graceful total gs-compound_.

###  IV-C Topsnut-matchings produced by graph operations

  1. 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)\rightarrow S_{og}(p)$ such that each edge $uv\in E(G)$
labeled as $f(uv)=\odot_{k}\langle f(u),f(v)\rangle$ 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\in
E(G)\\}=[a,b]$, we say the graph $\langle G\odot S_{og}(p)\rangle$ obtained by
joining $f(u)$ with $f(uv)$ and joining $f(uv)$ with $f(v)$ for each edge
$uv\in E(G)$ an _$[a,b]$ -twin odd-graceful/odd-elegant graph_.

  2. Op-2.

Euler’s graph matching. Let $E_{g}$ be a set of non-eulerian graphs. A
$(p,q)$-graph $G$ admits a graph labelling $f:V(G)\rightarrow E_{g}$, and
induced edge label $f(uv)=\odot_{k}\langle f(u),f(v)\rangle$ is just an
Euler’s graph of $k_{uv}$ vertices, we call $(f(u),f(v))$ an _Euler’s Topsnut-
matching_. The graph $\langle G\odot E_{g}\rangle$ obtained by joining $f(u)$
with $f(uv)$ and joining $f(uv)$ with $f(v)$ for each edge $uv\in E(G)$ an
_$[a,b]$ -Euler’s graph_, where $\\{k_{uv}:uv\in E(G)\\}=[a,b]$.

  3. Op-3.

Hamilton graph matching. Let $H_{ag}$ be a set of graphs. A $(p,q)$-graph $G$
admits a graph labelling $f:V(G)\rightarrow H_{ag}$, and induced edge label
$f(uv)=\odot_{k}\langle f(u),f(v)\rangle$ is just a Hamilton graph of $k_{uv}$
vertices, we call $(f(u),f(v))$ an _Hamilton Topsnut-matching_. The graph
$\langle G\odot E_{ag}\rangle$ obtained by joining $f(u)$ with $f(uv)$ and
joining $f(uv)$ with $f(v)$ for each edge $uv\in E(G)$ an _$[a,b]$ -Hamilton
graph_, where $\\{k_{uv}:uv\in E(G)\\}=[a,b]$.

  4. Op-4.

Pan-matching with operation $(\bullet)$. Let $P_{ag}$ be a set of graphs. A
$(p,q)$-graph $G$ admits a graph labelling $F:V(G)\rightarrow H_{ag}$, and
induced edge label $F(uv)=F(u)(\bullet)F(v)$ is just a graph having a
P-matching, where $(\bullet)$ 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, and so on. We call the graph
$\langle G(\bullet)P_{ag}\rangle$ obtained by joining $F(u)$ with $F(uv)$ and
joining $F(uv)$ with $F(v)$ for each edge $uv\in E(G)$ a _P-matching
$\\{k_{uv}\\}$-graph_.

A $\\{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)\rightarrow
H_{ag}$, where $P_{ag}$ is a set of graphs, and let $F(uv)=\odot_{k}\langle
F(u),F(v)\rangle$ be a graph having a $\\{a;b\\}$-factor for each edge $uv\in
E(G)$.

Figure 35:  Left is a tree $T$, Right is a collection $T^{*}$ of graph-
labelling graphs based on $T$ and the intersect operation.
Figure 36:  A graph $H$ is one of the collection $T^{*}$ shown in Fig.35.

In Fig.35 and Fig.36, a tree $T$ admits a graph labelling $F:V(T)\rightarrow
F(G)$, where $F(x_{i})=G_{i}$ with $i\in[1,7]$, and
$F(x_{i}x_{j})=F(x_{i})\cap F(x_{j})=G_{i}\cap G_{j}=H_{ij}$. The graph $H$
shown in Fig.36 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}+\overline{K}_{2}$ is a $\\{2;1\\}$-factor,
$H_{23}=K_{2}+\overline{K}_{2}$ is a $\\{2;2\\}$-factor,
$H_{34}=K_{2}+\overline{K}_{2}$ is a $\\{2;3\\}$-factor,
$H_{45}=K_{2}+\overline{K}_{3}$ is a $\\{2;4\\}$-factor,
$H_{46}=K_{2}+\overline{K}_{4}$ is a $\\{2;5\\}$-factor, and
$H_{47}=K_{2}+\overline{K}_{5}$ is a $\\{2;6\\}$-factor. So, The edges of the
graph $H$ form a graceful sequence of $\\{2;k\\}$-factors with $k\in[1,6]$.

######  Theorem 21.

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}$.

###### Proof.

A caterpillar $T$ shown in Fig.10 contains a path $P=u_{1}u_{2}\cdots 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\in[1,m_{i}]\\}$ with $m_{i}\geq 0$ and $i\in[1,n]$. We
take a non-decreasing sequence-pair $\\{a_{i,j}\\}$ and $\\{b_{i,j}\\}$ for
$j\in[1,m_{i}]$ and $i\in[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})=\sum^{m_{1}}_{j=1}a_{1,j}$ and $B(m_{1})=\sum^{m_{1}}_{j=1}b_{1,j}$,
and set $F(v_{1,j})=K(a_{1,j},b_{1,j})$ and $F(u_{1}v_{1,j})=F(u_{1})\cap
F(v_{1,j})$ with $j\in[1,m_{1}]$.

For $i:=i+1$, we set
$F(u_{i+1})=K(\sum^{i+1}_{k=1}A(m_{k})+\sum^{i}_{k=1}c_{k,k+1},\sum^{i+1}_{k=1}B(m_{k})+\sum^{i}_{k=1}d_{k,k+1})$
with $A(m_{k})=\sum^{m_{k}}_{j=1}a_{k,j}$ and
$B(m_{k})=\sum^{m_{k}}_{j=1}b_{k,j}$, and set
$F(v_{i+1,j})=K(a_{i+1,j},b_{i+1,j})$ and $F(u_{1}v_{i+1,j})=F(u_{i+1})\cap
F(v_{i+1,j})$ with $j\in[1,m_{i+1}]$.

At the last, we let
$F(u_{n})=K(1+\sum^{n}_{k=1}A(m_{k})+\sum^{n-1}_{k=1}c_{k,k+1},\sum^{n}_{k=1}B(m_{k})+\sum^{n-1}_{k=1}d_{k,k+1})$,
and set $F(v_{n,j})=K(a_{n,j},b_{n,j})$ and $F(u_{n}v_{n,j})=F(u_{n})\cap
F(v_{n,j})$ with $j\in[1,m_{n}]$.

Let $\alpha(r)=\sum^{r}_{k=1}m_{k}$. We write $a^{*}_{j}=a_{1,j}$ and
$b^{*}_{1,j}=b_{1,j}$ with $j\in[1,m_{1}]$; $c_{12}=a^{*}_{1+\alpha(1)}$ and
$d_{12}=b^{*}_{1+\alpha(1)}$; $a^{*}_{1+\alpha(1)+j}=a_{2,j}$ and
$b^{*}_{1+\alpha(1)+j}=b_{2,j}$ with $j\in[1,m_{2}]$;
$c_{2,3}=a^{*}_{2+\alpha(2)}$ and $d_{2,3}=b^{*}_{2+\alpha(2)}$; $\cdots$;
$c_{n-1,n}=a^{*}_{n-1+\alpha(n-1)}$ and $d_{n-1,n}=b^{*}_{n-1+\alpha(n-1)}$;
$a^{*}_{n-1+\alpha(n-1)+j}=a_{n,j}$ and $b^{*}_{n-1+\alpha(n-1)+j}=b_{n,j}$
with $j\in[1,m_{n}]$. Furthermore, we let $a^{*}_{k}\leq a^{*}_{k+1}$ and
$b^{*}_{k}\leq b^{*}_{k+1}$ with $k\in[1,n-1+\alpha(n)]$.

So, we have shown the result of the theorem. ∎

We give the values of $\\{a^{*}_{i}\\}^{q}_{1}$ and $\\{b^{*}_{i}\\}^{q}_{1}$
in Theorem 21 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\\}$-factor, 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 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}$.

###  IV-D Properties of Labellings

The previous subsections show the labellings with the following
properties.Other properties of labellings can be found in [2]. Let $k$ be a
constant, $G$ be a $(p,q)$-graph. We have

  1. C-1.

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

  2. C-2.

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

  3. C-3.

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

  4. C-4.

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

  5. C-5.

(ee-sum) Each edge $uv$ matches with another edge $xy$ holding
$f(uv)=f(x)+f(y)~{}(\bmod~{}B)$ such that the resulting edge labels are
distinct and nonzero.

  6. C-6.

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

  7. C-7.

(ee-bandwiden) Each edge $uv$ matches with another edge $u^{\prime}v^{\prime}$
holding $s(uv)+s(u^{\prime}v^{\prime})=0$, where $s(xy)=|f(x)-f(y)|-f(xy)$.

  8. C-8.

(ve-matching) Each edge $uv$ matches with one vertex $w$ such that
$f(uv)+f(w)=k^{\prime}$, and vice versa, except the _singularity_.

  9. C-9.

(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))\subseteq f(E(G))$, $f(E(G))\subseteq f(V(G))$.

  10. C-10.

(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)$.

  11. C-11.

(reciprocal-inverse) $h(V(G)\cup E(G))=[1,p+q]$,
$h(V(G))\setminus\\{a_{0}\\}=f(E(G))$ and
$h(E(G))=f(V(G))\setminus\\{a_{0}\\}$, where $a_{0}=\lfloor(p+q+1)/2\rfloor$
is the singularity of two labellings $f$ and $h$.

  12. C-12.

(odd-even separable) $h(V(G)\cup E(G))=[1,p+q]$, $h(V(G))$ is an odd-set
containing only odd numbers, and $h(E(G))$ is an even-set containing only even
numbers.

###  IV-E Some indices for analyzing graph labellings

We design parameters for theoretically metricizing Topsnut-gpws, such as:

  1. Deg-1.

_Difficulty_. A labelling $f$ holds $m$ conditions, we say $f$ to be $m$-rank
difficulty.

  2. Deg-2.

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

  3. Deg-3.

_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.

  4. Deg-4.

_Computationally unbreakable._ Consider giant space, no-constructive
algorithm, non-mathematical intervention (physics, chemistry, biology, music,
national language).

  5. Deg-5.

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

  6. Deg-6.

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

  7. Deg-7.

_Closure._ Labellings are closed to graph properties or labelling properties.

  8. Deg-8.

_Connections._ 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 _ect._

  9. Deg-9.

_Compound._ Graphs are labeled by Topsnut-gpws and graphic groups.

  10. Deg-10.

_Transformation._ Suppose that $f$ is set-ordered on $(X,Y)$, so we have an
affine transformation $g$ defined by $g(x)=af(x)+b$ for $x\in X$,
$g(y)=cf(y)+d$ for $y\in Y$.

  11. Deg-11.

_Generalization._ What is a hyperlabelling? What is a network labelling? What
is an random labelling? What is a functional (chemistry, physical, biological)
labelling?

##  V 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.

###  V-A 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}\cup[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\geq 2$ and $q\geq 1$, the previous labelling
definitions enable us to obtain the following set problems:

  1. Set-1.

From Definition 9: Partition $[1,p+q]$ into two disjoint subsets $V$ and $E$
with $V\cup E=[1,p+q]$ such that: (i) each $c\in E$ corresponds to distinct
$a,b\in V$ holding $c=|a-b|$; (ii) there exists a constant $k$, each
$c^{\prime}\in E$ matches with distinc $a^{\prime},b^{\prime}\in V$ holding