Parameterized Colorings And Labellings
Of Graphs In Topological Coding
Bing YAO, Xiaohui ZHANG, Hui SUN, Jing SU, Fei Ma, Hongyu WANG
()

###### Contents

  1. 1 Introduction and preliminary
    1. 1.1 Requirements of information security
    2. 1.2 Techniques of topological coding
      1. 1.2.1 Parameterized number-based strings
      2. 1.2.2 The problems of integer partition and integer factorization
      3. 1.2.3 Topological structure decomposition problems
    3. 1.3 Our works
    4. 1.4 Preliminary
      1. 1.4.1 Terminologies and notations
      2. 1.4.2 Basic graph operations
  2. 2 Parameterized total colorings
    1. 2.1 Basic labelings and colorings
    2. 2.2 Labelings and results on disconnected graphs
  3. 3 Graphs admitting parameterized total colorings
    1. 3.1 Graphs admitting $W$-constraint $(k,d)$-total colorings
    2. 3.2 Graphs admitting graceful $(k,d)$-total colorings
    3. 3.3 Graphs admitting harmonious $(k,d)$-total colorings
    4. 3.4 Connections between parameterized total colorings
    5. 3.5 Trees admitting magic-constraint total colorings
  4. 4 Magic-constraint parameterized algorithms
    1. 4.1 Parameterized graceful-difference total labelings/colorings
    2. 4.2 Parameterized edge-difference total labelings/colorings
    3. 4.3 Parameterized felicitous-difference total labelings/colorings
    4. 4.4 Parameterized edge-magic total labelings/colorings
  5. 5 Parameterized labelings on trees having perfect matchings
    1. 5.1 Basic labelings on trees having perfect matchings
    2. 5.2 $(k,d)$-constraint labelings on trees with perfect matchings
    3. 5.3 The $\pm e$-operations and the $\pm e$-graphs
  6. 6 Topics related with parameterized colorings/labelings
    1. 6.1 Topcode-matrices having parameterized elements
      1. 6.1.1 Algebraic operations on Topcode-matrices
      2. 6.1.2 Parameterized Topcode-matrices
    2. 6.2 Number-based strings containing parameters
    3. 6.3 Graphic lattices related with parameterized total colorings
      1. 6.3.1 Operation-type graphic lattices
      2. 6.3.2 Uncolored tree-graphic lattices
      3. 6.3.3 $(k,d)$-colored tree-graphic lattices
      4. 6.3.4 Tree-graphic lattice homomorphisms
    4. 6.4 Graphic groups based on parameterized total colorings
    5. 6.5 Various parameterized colorings
      1. 6.5.1 Parameterized total set-colorings
      2. 6.5.2 Set-colorings with multiple intersections
      3. 6.5.3 Parameterized hypergraphs
      4. 6.5.4 VSET-coloring algorithm
      5. 6.5.5 PWCSC-algorithms on colored trees
      6. 6.5.6 Graph homomorphisms with parameterized set-colorings
      7. 6.5.7 Normal set-colorings based on hyperedge sets
    6. 6.6 Miscellaneous colorings with parameters
      1. 6.6.1 Total colorings subject to $(abc)$-magic-type functions
      2. 6.6.2 Real-valued parameterized total colorings
      3. 6.6.3 Parameterized Topcode-matrices to non-isomorphic graphs
      4. 6.6.4 Colorings/labelings with fractional numbers
  7. 7 Conclusion and further researching topics
  8. 8 Acknowledgment

Parameterized Colorings And Labellings
Of Graphs In Topological Coding
Bing Yao111 College of Mathematics and Statistics, Northwest Normal
University, Lanzhou, 730070, CHINA, email<EMAIL_ADDRESS>Xiaohui Zhang222
School of Computer, Qinghai Normal University, Xining, 810001, CHINA, email:
<EMAIL_ADDRESS>Hui Sun333 School of Electronics Engineering and Computer
Science, Peking University, Beijing, 100871, CHINA, email:
<EMAIL_ADDRESS>Jing Su444 School of Electronics Engineering and Computer
Science, Peking University, Beijing, 100871, CHINA, email<EMAIL_ADDRESS>Fei Ma555 School of Electronics Engineering and Computer Science, Peking
University, Beijing, 100871, CHINA, email<EMAIL_ADDRESS>Hongyu Wang666
National Computer Network Emergency Response Technical Team/Coordination
Center of China, Beijing, 100029, CHINA, email<EMAIL_ADDRESS>
()

> Abstract: The coming quantum computation is forcing us to reexamine the
> cryptosystems people use. We are applying graph colorings of topological
> coding to modern information security and future cryptography against
> supercomputer and quantum computer attacks in the near future. Many of
> techniques introduced here are associated with many mathematical conjecture
> and NP-problems. We will introduce a group of $W$-constraint $(k,d)$-total
> colorings and algorithms for realizing these colorings in some kinds of
> graphs, which are used to make quickly _public-keys_ and _private-keys_ with
> anti-quantum computing, these $(k,d)$-total colorings are: graceful
> $(k,d)$-total colorings, harmonious $(k,d)$-total colorings, $(k,d)$-edge-
> magic total colorings, $(k,d)$-graceful-difference total colorings and
> $(k,d)$-felicitous-difference total colorings. One of useful tools we used
> is called _Topcode-matrix_ with elements can be all sorts of things, for
> example, sets, graphs, number-based strings. Most of parameterized graphic
> colorings/labelings are defined by _Topcode-matrix algebra_ here. From the
> application point of view, many of our coloring techniques are given by
> algorithms and easily converted into programs. Some operations based on
> Topcode-matrices help us to define new parameterized colorings, to generate
> number-based strings containing parameters, and to build up graphic lattices
> including tree-graphic lattices and tree-graphic lattice homomorphisms. More
> complex homomorphism phenomenon is from a colored graph homomorphism to a
> Topcode-matrix homomorphism, and then to a graph-set homomorphism. We
> investigate parameterized set-colorings, hypergraphs based on parameterized
> set-colorings, and set-colorings with multiple intersections, as well as
> graph homomorphisms with parameterized set-colorings. We point that the
> techniques of topological coding are related with the subgraph isomorphic
> problem, the problems of integer partition and integer factorization, the
> parameterized number-based string partition problem, the topological
> structure decomposition problem, and the parametric reconstitution of
> number-based string.
>  Mathematics Subject classification: 05C60, 68M25, 06B30, 22A26, 81Q35
>  Keywords: Lattice-based cryptosystem; parameterized graphic coloring; set-
> coloring; topological coding; quantum computation; integer factorization;
> algorithm; quantum computation.

##  1 Introduction and preliminary

###  1.1 Requirements of information security

The coming quantum computation is forcing us to reexamine the cryptosystems we
use.

The authors in [3] pointed: Most research in quantum algorithms has revolved
around the hidden subgroup problem. The hidden subgroup problem is a problem
defined on a group, and many problems reduce to it. Factoring and discrete log
reduce to the hidden subgroup problem when the underlying group is finite or
countable. Pell’s equation reduces to the hidden subgroup problem when the
group is uncountable. For these cases there are efficient quantum algorithms
to solve the hidden subgroup problem, and hence the underlying problem,
because the group is _abelian_. Graph isomorphism reduces to the hidden
subgroup problem for the symmetric group, and the unique shortest lattice
vector problem is related to the hidden subgroup problem when the group is
dihedral.

“Quantum cryptography” also called “quantum key distribution” expands a short
shared key into an effectively infinite shared stream. The prerequisite for
quantum cryptography is that the users, say Alice and Bob, both know (e.g.)
256 unpredictable secret key bits. The result of quantum cryptography is that
Alice and Bob both know a stream of (e.g.) 1012 unpredictable secret bits that
can be used to encrypt messages. The length of the output stream increases
linearly with the amount of time that Alice and Bob spend on quantum
cryptography.

Peikert, in [8], pointed that lattice-based ciphers have the following
advantages: Conjectured security against quantum attacks; Algorithmic
simplicity, efficiency, and parallelism; Strong security guarantees from
worst-case hardness.

Lattice-based systems provide a good alternative since they are based on a
long-standing open problem for classical computation [3].

###  1.2 Techniques of topological coding

Topological Coding consists of two different kinds of mathematical branches:
Topological coding involves millions of things in the world, and people use
topological structures to connects things together to form complete “stories”
under certain constraints in asymmetric encryption system [38]. The authors,
in [9], use the topological graph to generate the honeywords, which is the
first application of graphic labeling of topological coding in the honeywords
generation. They propose a method to protect the _hashed passwords_ by using
_topological graphic sequences_.

Topsnut-gpws, the abbreviation of the sentence “graphic passwords made by
topological structures and mathematical constraints”, belong to topological
coding in [43] and [44]. However, Topsnut-gpws differ from the existing
graphical passwords, since they are saved and implemented in computer by
popular matrices. There are many NP-hard problems and conjectures in Topsnut-
gpws, for example, the Subgraph Isomorphic Problem, a NP-hard problem. As
known, a Topcode-matrix can bring a group of “things” together topologically
by mathematical constraints, in general.

Topsnut-gpws correspond to matrices of order $3\times q$, called _Topcode-
matrices_ , which can generate quickly number-based strings with longer bytes
for ciphering digital files. And moreover, Topsnut-gpws are easy to induce
asymmetric public-keys and private-keys, such as, one public-key vs two or
more private-keys, more public-keys vs more private-keys. However, it is
irreversible to find the original Topsnut-gpw from a number-based string made
by the Topcode-matrix of this Topsnut-gpw, since a Topsnut-gpw is made by a
topological structure and a group of mathematical constraints.

After years of research, we summarize the following advantages of Topsnut-gpws
[36]:

  1. (1)

Run fast in communication networks because they are saved in computer by
popular matrices rather than pictures.

  2. (2)

Produce easily text-based strings, or number-based strings for encrypting
files in real applications.

  3. (3)

Diversity of asymmetric ciphers, such as one _public-key_ corresponds to more
_private-keys_ , or more _public-keys_ correspond to more _private-keys_.

  4. (4)

Supported by many branches of mathematics. Number theory (especially
computational number theory), information theory, probability theory, random
process, combinatorial mathematics, linear algebra, matrix algebra, discrete
mathematics and graph theory are the solid foundation and strong technical
support to Topsnut-gpws of topology coding.

  5. (5)

Irreversibility, Topsnut-gpws can generate quickly text-based strings, or
number-based strings with bytes as long as desired, but these strings can not
reconstruct the original Topsnut-gpws, since this work must span two
fundamentally different branches of mathematics: topological structures and
non-topological mathematical constraints.

  6. (6)

Computational security There are enormous numbers of graph colorings and
labelings in graph theory, and new graph colorings/labelings come into being
everyday. As known, there are no polynomial algorithms for creating the
topological structures (see Eq.(4)) of Topsnut-gpws.

  7. (7)

Provable security, since Topsnut-gpws are related with many long-standing
mathematical conjectures, NP-complete and NP-hard problems from number theory,
combinatorics, discrete mathematics and graph theory.

In other word, Topsnut-gpws have part of the advantages of lattice-based
cryptosystems.

####  1.2.1 Parameterized number-based strings

A _number-based string_ $S=c_{1}c_{2}\cdots c_{m}$ is defined by
$c_{i}\in[0,9]=\\{0,1,2,\dots,9\\}$. We can get the following number-based
strings

${\begin{split}D_{1}(1,2)&=001919170415171513461117159647151356639917\\\
D_{2}(1,2)&=617936459137669151511441317151500171719190\\\
D_{3}(1,2)&=170019191704151715134611159647151356639917\end{split}}$ (1)

from a Topcode-matrix $T_{code}(1,2)$ of order $3\times 10$ shown in Eq.(2).
It is not difficult to see that there are $30!$ different number-based strings
made by $T_{code}(1,2)$, like three number-based strings shown in Eq.(1), in
total. The Topcode-matrix $T_{code}(1,2)$ is a particular case of a Topcode-
matrix $T_{code}(k,d)$ with parameterized elements shown in Eq.(3), as we take
$(k,d)=(1,2)$. Clearly, we have infinite different number-based strings from
the Topcode-matrix $T_{code}(k,d)$.

$\centering{\begin{split}T_{code}(1,2)=\left(\begin{array}[]{ccccccccccccccc}6&6&4&6&6&4&4&0&0&0\\\
1&3&5&7&9&11&13&15&17&19\\\
7&9&9&13&15&15&17&15&17&19\end{array}\right)_{3\times
10}\end{split}}\@add@centering$ (2)

$\centering
T_{code}(k,d)=\left(\begin{array}[]{ccccccccccccccc}3d&3d&2d&3d&3d&2d&2d&0&0&0\\\
k&k+d&k+2d&k+3d&k+4d&k+5d&k+6d&k+7d&k+8d&k+9d\\\
k+3d&k+4d&k+4d&k+6d&k+7d&k+7d&k+8d&k+7d&k+8d&k+9d\end{array}\right)\@add@centering$
(3)

Each Topsnut-gpw shown in Fig.1 consists of a topological structure (see
Fig.2) and a parameterized total coloring. Moreover, each Topsnut-gpw $A_{i}$
shown in Fig.1 admits a _colored graph homomorphism_ to $A$, that is
$A_{i}\rightarrow A$ with $i\in[1,5]=\\{1,2,3,4,5\\}$. Thereby, each colored
graph homomorphism $A_{i}\rightarrow A$ forms a _topological authentication_.

Figure 1: Six Topsnut-gpws with parameterized total colorings. Figure 2: Six
uncolored graphs correspond to six Topsnut-gpws with parameterized total
colorings shown in Fig.1.

######  Problem 1.

Motivated from the Number-based String Partition Problem proposed in [37], we
present the following PNBSP-problem (Parameterized Number-based String
Partition Problem):

> PNBSP-problem. For a given number-based string $S=c_{1}c_{2}\cdots c_{m}$
> with $c_{i}\in[0,9]$, partition it into $3q$ segments $c_{1}c_{2}\cdots
> c_{m}=a_{1}a_{2}\cdots a_{3q}$ with $a_{j}=c_{n_{j}}c_{n_{j}+1}\cdots
> c_{n_{j+1}}$ with $j\in[1,3q-1]$, where $n_{1}=1$ and $n_{3q}=m$, and use
> these segments $a_{1},a_{2},\dots,a_{3q}$ to reform a Topcode-matrix
> $T_{code}$, like the Topcode-matrix $T_{code}(1,2)$ shown in Eq.(2), and
> moreover use the Topcode-matrix $T_{code}$ to reconstruct all of Topsnut-
> gpws of $q$ edges, like six Topsnut-gpws corresponding to $T_{code}(k,d)$
> shown in Fig.1. By the found Topsnut-gpws corresponding to the common
> Topcode-matrix $T_{code}(k,d)$, find the desired _public Topsnut-gpw_ $A$
> and the desired _private Topsnut-gpws_ $A_{i}$, such that each mapping
> $\varphi_{i}:V(A)\rightarrow V(A_{i})$ forms a _colored graph homomorphism_
> (topological authentication) $A_{i}\rightarrow A$ with $i\in[1,5]$.

####  1.2.2 The problems of integer partition and integer factorization

The PNBSP-problem enables us to think the following problems related with the
_integer partition_ and the _integer factorization_ :

  1. Prob-1.

Since a parameterized Topcode-matrix $T_{code}(k,d)$ with parameters $k$ and
$d$ is related with one of graph colorings and graph labelings, as known there
are hundreds of graph colorings and graph labelings have been introduced, so
determining this Topcode-matrix $T_{code}(k,d)$ is not a slight job.

  2. Prob-2.

Let $G_{p}$ be the number of graphs of $p$ vertices, Harary and Palmer [7]
computed

${\begin{split}G_{23}&=559946939699792080597976380819462179812276348458981632\approx
2^{179}\\\
G_{24}&=195704906302078447922174862416726256004122075267063365754368\approx
2^{197}\end{split}}$ (4)

If a parameterized Topcode-matrix $T_{code}(k,d)$ corresponding to a number-
based string $D(k_{0},d_{0})$ has been determined, finding all non-isomorphic
Topsnut-gpws (colored graphs) corresponding to $T_{code}(k,d)$ will meet the
Subgraph Isomorphic Problem, as known, a NP-hard, see examples shown in Fig.2
and two numbers $G_{23}$, $G_{24}$ shown in Eq.(4).

  3. Prob-3.

As two parameters $k$ and $d$ both are prime numbers, determining a
parameterized Topcode-matrix $T_{code}(k,d)$ will meet the Integer
Factorization Problem with an odd number factorization $\alpha=k\cdot d$ if
$\alpha$ is as a _public-key_ , or the Integer Partition Problem, such as an
even number partition $\beta=k+d$ if $\beta$ is as a _public-key_.

  4. Prob-4.

No polynomial algorithm is for finding the colorings admitted by the _public-
key_ $A$ and the _private-key_ $A_{i}$ with $i\in[1,5]$. And no algorithm find
all possible colorings admitted by a graph, since it is a NP-type problem.

  5. Prob-5.

Since a number-based string $s=c_{1}c_{2}\cdots c_{m}$ can be induced by
different Topcode-matrices $T^{1}_{code}(k,d)$, $T^{2}_{code}(k,d)$, $\dots$,
$T^{n}_{code}(k,d)$, so no way is to realize the following processes:

$D_{j}(1,2)\rightarrow T_{code}(1,2)\rightarrow A;~{}D_{j}(1,2)\rightarrow
T_{code}(1,2)\rightarrow A_{j},~{}j\in[1,5]$

from the number-based strings to the public Topsnut-gpw $A$ and the desired
private Topsnut-gpws $A_{i}$, see Eq.(1), Eq.(2) and Fig.1.

  6. Prob-6.

As known, a number-based string $s=c_{1}c_{2}\cdots c_{m}$ can be generated by
degree sequences, vectors, matrices, graph colorings _etc._ , so it is
difficult to judge which way produces the given number-based string
$s=c_{1}c_{2}\cdots c_{m}$. For example, the number-based string $D_{3}(1,2)$
shown in Eq.(1), also, is an odd integer.

  7. Prob-7.

Different colored graphs induce the same number-based strings. For example, a
colored graph $G_{2}$ shown in Fig.3 admits a total set-coloring
$F:V(G_{2})\cup E(G_{2})\rightarrow M$, such that each $c\in F(uv)$
corresponds to some $a\in F(u)$ and $b\in F(v)$ holding $c=|a-b|$. So, we have
a Topcode-matrix as follows:

$\centering{\begin{split}T_{code}(G_{2})=\left(\begin{array}[]{ccccccccccccccc}11&11&11&11&44&44\\\
76&52&47&33&21&31\\\ 87&63&58&44&23&13\end{array}\right)_{3\times
6}\end{split}}\@add@centering$ (5)

Let $S_{tring}(G_{2})$ be the set of number-based strings $D_{k}(G_{2})$
induced from the Topcode-matrix $T_{code}(G_{2})$ shown in Eq.(5), such as

$D_{k}(G_{2})=111111114444765247332131876358442313$ (6)

with $36$ bytes. Clearly, the Topcode-matrix $T_{code}(G_{2})$ can induce
$|S_{tring}(G_{2})|=(18)!$ different number-based strings, in total.

Figure 3: (a) A tree $G_{1}$ admits a set-ordered graceful labeling; (b)
$G_{2}$ admits a set-coloring; (c) $G_{3}$ admits a proper total coloring.

Another colored graph $G_{3}$ shown in Fig.3 admits a total coloring
$f:V(G_{3})\cup E(G_{3})\rightarrow[1,10]$, such that $f(xy)=|f(x)-f(y)|$ for
each edge $xy\in E(G_{3})$. All number-based strings $D_{i}(G_{3})$ induced
from the Topcode-matrix $T_{code}(G_{3})$ shown in Eq.(7) are collected into
$S_{tring}(G_{3})$, which distributes us $|S_{tring}(G_{3})|=(36)!$ different
number-based strings.

$\centering{\begin{split}T_{code}(G_{3})=\left(\begin{array}[]{ccccccccccccccc}1&1&1&1&1&1&1&1&4&4&4&4\\\
7&6&5&2&4&7&3&3&2&1&3&1\\\ 8&7&6&3&5&8&4&4&2&3&1&3\end{array}\right)_{3\times
12}\end{split}}\@add@centering$ (7)

Since $S_{tring}(G_{2})\subset S_{tring}(G_{3})$, so we have more different
colored graphs, which induce the same number-based strings.

  8. Prob-8.

No method for cutting a number-based string like $D_{k}(G_{2})$ shown in
Eq.(6) into $3q$ segments $c_{1}c_{2}\cdots c_{m}=a_{1}a_{2}\cdots a_{3q}$
with $a_{j}=c_{n_{j}}c_{n_{j}+1}\cdots c_{n_{j+1}}$ with $j\in[1,3q-1]$, where
$n_{1}=1$ and $n_{3q}=m$, such that $a_{1},a_{2},\dots,a_{3q}$ are just the
elements of some Topcode-matrix of order $3\times q$.

######  Problem 2.

The above problems Prob-1, Prob-3 and Prob-8 form NP-hard problems. Since the
complexity of the PNBSP-problem consists of the Topcode-matrix Problem and
Subgraph Isomorphic Problem, so we can say PNBSP-problem to be (NP-
hard$)^{2}$.

######  Theorem 1.

There are different colored graphs, which induce the same number-based
strings.

####  1.2.3 Topological structure decomposition problems

There are topological structure decomposition problems related with the
Integer Factorization Problem and the Integer Partition Problem.

  1. TSDp-1.

Vertex-split Problem. Let $N(x)=\\{y_{1},y_{2},\dots,y_{d}\\}$ with the degree
$d=\textrm{deg}_{G}(x)\geq 2$ be the neighbor set of the vertex $x$ in a
$(p,q)$-graph $G$. We vertex-split $x$ into $m$ vertices
$x_{1},x_{2},\dots,x_{m}$ with $m\geq 2$, and join $x_{i}$ with the vertices
of a subset $N(x_{i})\subset N(x)$ by edges, here $|N(x_{i})|\geq 1$ and
$\bigcup^{m}_{i=1}N(x_{i})=N(x)$ and $N(x_{i})\cap N(x_{j})=\emptyset$ if
$i\neq j$, the resultant graph, called _vertex-split graph_ , is denoted as
$G\wedge_{m}x$.

Let $N(x_{i})=\\{y_{i,1},y_{i,2},\dots,y_{i,n_{i}}\\}$ with
$n_{i}=|N(x_{i})|$, then we have to partition the degree $d$ into

$d=\sum^{m}_{i=1}|N(x_{i})|=n_{1}+n_{2}+\cdots+n_{m}$ (8)

For each degree partition defined in Eq.(8), suppose that there are
$n(N(x),m)$ different ways to partition $N(x)$ into different groups of
subsets $N(x_{1})$, $N(x_{2})$, $\dots$, $N(x_{m})$. We assume that there are
$n(d,m)$ degree partitions holding Eq.(8). Thereby, we have

$\sum^{p-1}_{m=2}n(N(x),m)\cdot n(d,m)$ (9)

different vertex-split graphs $G\wedge_{m}x$.

  2. TSDp-2.

Leaf-added graphs related with Integer Partition Problem. We select $k$
vertices from a $(p,q)$-graph $G$ for adding $m$ new leaves to them, then we
have $A^{k}_{p}=p(p-1)\cdots(p-k+1)$ selections, rather than ${p\choose
k}=\frac{p!}{k!(p-k)!}$. Next, we partition $m$ into a sum of $k$ parts
$m_{1},m_{2},\cdots,m_{k}$ with each $m_{i}\neq 0$, that is
$m=m_{1}+m_{2}+\cdots+m_{k}$. Suppose there is $n(m,k)$ groups of such $k$
parts. For a group of $k$ parts $m_{1},m_{2},\cdots,m_{k}$, let
$m_{i_{1}},m_{i_{2}},\cdots,m_{i_{k}}$ be a permutation of
$m_{1},m_{2},\cdots,m_{k}$, so we have the number of such permutations is a
factorial $k!$. Since the $(p,q)$-graph $G$ is colored well by a
$W$-constraint coloring/labeling $f$, then we have the number $A_{leaf}(G,m)$
of all possible adding $m$ leaves as follows

$A_{leaf}(G,m)=\sum^{m}_{k=1}A^{k}_{p}\cdot n(m,k)\cdot
k!=\sum^{m}_{k=1}n(m,k)\cdot p!$ (10)

where $n(m,k)=\sum^{k}_{r=1}n(m-k,r)$. Here, computing $n(m,k)$ can be
transformed into finding the number $A(m,k)$ of solutions of _Diophantine
equation_ $m=\sum^{k}_{i=1}ix_{i}$. There is a recursive formula

$A(m,k)=A(m,k-1)+A(m-k,k)$ (11)

with $0\leq k\leq m$. It is not easy to compute the exact value of $A(m,k)$,
for example, the authors in [48] and [49] computed exactly

${\begin{split}A(m,6)=&\biggr{\lfloor}\frac{1}{1036800}(12m^{5}+270m^{4}+1520m^{3}-1350m^{2}-19190m-9081)+\\\
&\frac{(-1)^{m}(m^{2}+9m+7)}{768}+\frac{1}{81}\left[(m+5)\cos\frac{2m\pi}{3}\right]\biggr{\rfloor}\end{split}}$
(12)

On the other hands, for any odd integer $m\geq 7$, it was conjectured
$m=p_{1}+p_{2}+p_{3}$ with three prime numbers $p_{1},p_{2},p_{3}$ from the
famous Goldbach’s conjecture: “Every even integer, greater than 2, can be
expressed as the sum of two prime numbers.” In other word, determining
$A(m,3)$ is difficult, also, it is difficult to express an odd integer
$m=\sum^{3n}_{k=1}p\,^{\prime}_{k}$, where each $p\,^{\prime}_{k}$ is a prime
number.

  3. TSDp-3.

Power sets and hyperedge sets.  The symbol $[1,n]^{2}$ is the set of all
subsets of an integer set $[1,n]=\\{1,2,\dots,n\\}$, called _power set_. A
_hyperedge set_ $\mathcal{E}\subset[1,n]^{2}$ holds
$[1,n]=\bigcup_{e\in\mathcal{E}}e$ true. There is a theorem in [46]: If a
hyperedge set $\mathcal{E}=\bigcup^{m}_{j=1}\mathcal{E}_{j}$ satisfies
$\mathcal{E}_{i}\cap\mathcal{E}_{j}=\emptyset$, such that each hyperedge
$e\in\mathcal{E}$ belongs to some $\mathcal{E}_{j}$, and
$e\not\in\bigcup^{m}_{k=1,k\neq j}\mathcal{E}_{k}$. Then,
$\\{\mathcal{E}_{1},\mathcal{E}_{2},\dots,\mathcal{E}_{m}\\}$ is a _hyperedge
decomposition_ of the hyperedge set $\mathcal{E}$. As $n$ is a large odd
number, characterizing the power set $[1,n]^{2}$ will meet the integer
factorization

$n=p_{1}\cdot p_{2}\cdot\cdots\cdot p_{s}~{}(s\geq 2)$

and the integer partition

$n=m_{1}+m_{2}+\cdots+m_{r}~{}(r\geq 2)$

since it is related with the problems of colorings, connectivity, Hamilton
property and topological decomposition, as well as the application in Database
structure [46].

  4. TSDp-4.

Problem of Integer Partition And Trees. Partition a positive integer $m$ into
a sum $m=m_{1}+m_{2}+\cdots+m_{n}$ $(n\geq 2)$, such that there is a tree $T$
having vertices $u_{1},u_{2},\dots,u_{n}$ holding just degrees
$\textrm{deg}_{T}(u_{i})=m_{i}$ for $i\in[1,n]$. How many trees with this
degree sequence $m_{1},m_{2},\dots,m_{n}$ are there?

  5. TSDp-5.

Topological form of Integer Factorization Problem. The _$4$ -color triangle
base_ shown in Fig.4 (a)

$\textbf{{T}}_{\textrm{riangle}}=\\{T_{S,1},T_{S,2},T_{S,3},T_{S,4}\\}$ (13)

forms a _4-colorable planar-graphic lattice_ as follows

$\textbf{{L}}(Z^{0}[~{}\overline{\ominus}~{}]\textbf{{T}}_{\textrm{riangle}})=\big{\\{}[~{}\overline{\ominus}~{}]^{4}_{k=1}a_{k}T_{S,k}:a_{k}\in
Z^{0},T_{S,k}\in\textbf{{T}}_{\textrm{riangle}}\big{\\}}$ (14)

with $\sum^{4}_{k=1}a_{k}\geq 1$, where “$[~{}\overline{\ominus}~{}]$” is the
_edge-coinciding operation_ (see examples shown in Fig.4). So, there are the
following facts:

(i) Let $F_{ace}(G)$ be the face number of a maximal planar graph $G$, then
$F_{ace}(G)-1=\sum^{4}_{k=1}a_{k}$.

(ii) Different $4$-colorings of a maximal planar graph $G$ induce different
sums $\sum^{4}_{k=1}a_{k}$.

(iii) An integer $\sum^{4}_{k=1}a_{k}$ may correspond to two or more maximal
planar graphs.

######  Problem 3.

How partition an integer $m=a_{1}+a_{2}+a_{3}+a_{4}$, such that the operation
$[\ominus]^{4}_{k=1}a_{k}T_{S,k}$ defined in Eq.(14) produces _4-colorable
maximal planar graphs_? Or, the results of the operation
$[\ominus]^{4}_{k=1}a_{k}T_{S,k}$ are just _4-colorable semi-maximal planar
graphs_ $G^{in}$ and $G^{out}$ having 2-color no-changed cycles defined in
[15, 16]?

Figure 4: The triangular system, the triangle-splitting operation and the
triangle-coinciding operation.

######  Problem 4.

By the triangular system
$\textbf{{T}}_{sys}=\\{T_{S,1},T_{S,2},T_{S,3},T_{S,4}\\}$ shown in Fig.4, the
vertex-coinciding operation and the edge-coinciding operation, we tile the
whole $xOy$-plane, the resultant plane is called a _triangular $4$-colored-
plane_, denoted as $T4$-plane. At the infinity of the $T4$-plane, what is the
$T4$-plane’s boundary? Is any planar graph in the $T4$-plane?

######  Problem 5.

For the 4-colorable planar-graphic lattice defined in Eq.(14), we have the
following questions:

  1. Mpg-1.

In Eq.(14), $[~{}\overline{\ominus}~{}]^{4}_{k=1}a_{k}T_{S,k}$ produces
$4$-colored maximal planar graphs, consider $4$-colored maximal planar graphs
holding: (i) each $a_{k}$ is even; (ii) each $a_{k}$ is odd; (iii) each
$a_{k}$ is a prime number; (iv) $4m=\sum^{4}_{k=1}a_{k}$; (v)
$4n=1+\sum^{4}_{k=1}a_{k}$.

  2. Mpg-2.

Since $[~{}\overline{\ominus}~{}]^{4}_{k=1}a_{k}T_{S,k}$ produces $4$-colored
maximal planar graphs for a fixed group of $a_{1},a_{2},a_{3},a_{4}$, how many
different $4$-colored maximal planar graphs made by this fixed group of
$a_{1},a_{2},a_{3},a_{4}$?

  3. Mpg-3.

A maximal planar graph $G$ admits a $4$-coloring $f$ which corresponding to a
fixed group of $a_{1},a_{2},a_{3},a_{4}$, and $G$ admits another $4$-coloring
$g$ which corresponding to a fixed group of $b_{1},b_{2},b_{3},b_{4}$, do we
have $a_{k}=b_{k}$ for $k\in[1,4]$? If it is, then we call $G$ _recursive
maximal planar graph_.

  4. Mpg-4.

If $G$ is a recursive maximal planar graph, do we have $a_{k}=b_{k}$ with
$k\in[1,4]$ for any pair of $4$-colorings $f,g$ of $G$, where the $4$-coloring
$f$ corresponds to $a_{1},a_{2},a_{3},a_{4}$ in
$G=[\overline{\ominus}]^{4}_{k=1}a_{k}T_{S,k}$, and the $4$-coloring $g$
corresponds to $b_{1},b_{2},b_{3},b_{4}$ in
$G=[~{}\overline{\ominus}~{}]^{4}_{k=1}b_{k}T_{S,k}$?

  5. Mpg-5.

Suppose that a maximal planar graph $G$ admits a $4$-coloring $f$ which
corresponding to a fixed group of $a_{1},a_{2},a_{3},a_{4}$, and another
maximal planar graph $H$ admits a $4$-coloring $g$ which corresponding to a
fixed group of $b_{1},b_{2},b_{3},b_{4}$. If $a_{k}=b_{k}$ for $k\in[1,4]$, do
we have $G\cong H$?

  6. Mpg-6.

Characterize a maximal planar graph $G$ admitting a $4$-coloring $f$ which
corresponding to a fixed group of $a_{1},a_{2},a_{3},a_{4}$, such that
$|a_{i}-a_{j}|\leq 1$ for $i\neq j$, we say that this maximal planar graph $G$
admits a _structure-equitable $4$-coloring_.

###  1.3 Our works

Our goal is applying the techniques of topological coding to modern
information security and future cryptography against supercomputer and quantum
computer attacks, we will introduce a group of $W$-constraint $(k,d)$-total
colorings and algorithms for realizing these colorings in some kinds of
graphs, which are used to make quickly _public-keys_ and _private-keys_ with
anti-quantum computing.

Since topological codes based on trees are easy to produce number-based
strings by computer, and many Hanzi-graphs are forests consisted of trees.
Another important reason is that connected graph can be vertex-split into
trees for getting their own various colorings, or set-colorings obtained from
that of trees. For example, we investigate trees, which obey the following
$(k,d)$-total colorings: graceful $(k,d)$-total colorings, harmonious
$(k,d)$-total colorings, $(k,d)$-edge-magic total colorings, $(k,d)$-graceful-
difference total colorings and $(k,d)$-felicitous-difference total colorings,
and so on.

We use a useful tool, called _Topcode-matrix_ , to bring some particular
things together topologically, for example, these particular things are _sets_
, _graphs_ , _number-based strings_ , and so on. According to the needs of
practical applications, many of our coloring techniques are given by
algorithms and are easily converted into programs.

Part of $(k,d)$-type colorings/labelings were introduced in [24], [38] and
[40].

###  1.4 Preliminary

####  1.4.1 Terminologies and notations

Standard terminology and notation of graph theory used here can be found in
[2] and [4]. We often use the following terminology and notation:

  1. $\ast$

The symbol $Z^{0}$ is the set of non-negative integers, and the notation $Z$
stands for the set of integers.

  2. $\ast$

$[a,b]$ stands for an integer set $\\{a,a+1,a+2,\dots,b\\}$ with two integers
$a,b$ subject to $a<b$; $[\alpha,\beta]^{o}$ denotes an _odd-set_
$\\{\alpha,\alpha+2,\dots,\beta\\}$ with odd integers $\alpha,\beta$ falling
into $1\leq\alpha<\beta$.

  3. $\ast$

For integers $r,k\geq 0$ and $s,d\geq 1$, we have two parameterized sets

$S_{s,k,r,d}=\\{k+rd,k+(r+1)d,\dots,k+(r+s)d\\}$ (15)

and

$O_{s,k,r,d}=\\{k+[2(r+1)-1]d,k+[2(r+2)-1]d,\dots,k+[2(r+s)-1]d\\}$ (16)

  4. $\ast$

The _cardinality_ (or _number_) of elements of a set $S$ is denoted as $|S|$,
so $|S_{s,k,r,d}|=s+1$ and $|O_{s,k,r,d}|=s$.

  5. $\ast$

Let $\Lambda$ be a finite set. The set of all subsets of $\Lambda$ is denoted
as $\Lambda^{2}=\\{X:~{}X\subseteq\Lambda\\}$, called _power set_ , and the
power set $\Lambda^{2}$ contains no empty set at all. For example, for a given
set $\Lambda=\\{a,b,c,d,e\\}$, the power set $\Lambda^{2}$ has its own
elements $\\{a\\}$, $\\{b\\}$, $\\{c\\}$, $\\{d\\}$, $\\{e\\}$, $\\{a,b\\}$,
$\\{a,c\\}$, $\\{a,d\\}$, $\\{a,e\\}$, $\\{b,c\\}$, $\\{b,d\\}$, $\\{b,e\\}$,
$\\{c,d\\}$, $\\{c,e\\}$, $\\{d,e\\}$, $\\{a,b,c\\}$, $\\{a,b,d\\}$,
$\\{a,b,e\\}$, $\\{a,c,d\\}$, $\\{a,c,e\\}$, $\\{a,d,e\\}$, $\\{b,c,d\\}$,
$\\{b,c,e\\}$, $\\{b,d,e\\}$, $\\{c,d,e\\}$, $\\{a,b,c,d\\}$, $\\{a,b,c,e\\}$,
$\\{a,c,d,e\\}$, $\\{a,b,d,e\\}$, $\\{b,c,d,e\\}$ and $\Lambda$ holding
$|\Lambda^{2}|=2^{5}-1$.

Moreover, the integer set $[1,4]=\\{1,2,3,4\\}$ induces a power set
$[1,4]^{2}=\big{\\{}\\{1\\},\\{2\\},\\{3\\}$, $\\{4\\}$, $\\{1,2\\}$,
$\\{1,3\\},\\{1,4\\}$, $\\{2,3\\}$, $\\{2,4\\}$, $\\{3,4\\}$, $\\{1,2,3\\}$,
$\\{1,2,4\\}$, $\\{1,3,4\\}$, $\\{2,3,4\\}$, $[1,4]\big{\\}}$, so the number
of subsets is $2^{4}-1=15$ in total.

  6. $\ast$

Each graph mentioned here has no multiple-edge and loop-edge.

  7. $\ast$

A $(p,q)$-graph is a graph having $p$ vertices and $q$ edges.

  8. $\ast$

Since the _number_ (also, _cardinality_) of elements of a set $X$ is denoted
as $|X|$, so the _degree_ of a vertex $x$ in a $(p,q)$-graph $G$ is denoted as
$\textrm{deg}_{G}(x)=|N(x)|$, where $N(x)$ is the set of neighbors of the
vertex $x$.

  9. $\ast$

A _leaf_ is a vertex of degree one in a graph.

  10. $\ast$

A _bipartite graph_ $H$ has its own vertex set $V(H)=X\cup Y$ with $X\cap
Y=\emptyset$, such that each edge $uv\in E(H)$ holds $u\in X$ and $v\in Y$
true.

  11. $\ast$

A _tree_ is a bipartite graph, such that each pair of vertices is connected by
a unique _path_. So, a tree has at least two _leaves_ and has no cycle.

Let $M$ be a set of integers, and let a graph $G$ admit a mapping $f:S\subset
V(G)\cup E(G)\rightarrow M$, write the set of colors assigned to the elements
of $S$ by $f(S)=\\{f(x):x\in S\\}$. There are the following basic
colorings/labelings in graph theory:

  1. A-1.

As $S=V(G)$, $f(S)=f(V(G))$, we call $f$ _vertex coloring_.

  2. A-2.

As $S=E(G)$, $f(S)=f(E(G))$, we call $f$ _edge coloring_.

  3. A-3.

As $S=V(G)\cup E(G)$, $f(S)=f(V(G)\cup E(G))=f(V(G))\cup f(E(G))$, we call $f$
_total coloring_.

  1. B-1.

As $f$ is a _vertex coloring_ and $f(u)\neq f(v)$ for each edge $uv\in E(G)$,
we call $f$ _proper vertex coloring_. The number
$\chi(G)=\min_{f}\max\\{f(w):w\in V(G)\\}$ over all proper vertex colorings of
$G$ is called _chromatic number_.

  2. B-2.

As $f$ is an _edge coloring_ and $f(uv)\neq f(uw)$ for any two adjacent edges
$uv$ and $uw$ of $G$, we call $f$ _proper edge coloring_. The number
$\chi\,^{\prime}(G)=\min_{f}\max\\{f(w):w\in E(G)\\}$ over all proper edge
colorings of $G$ is called _chromatic index_.

  3. B-3.

As $f$ is a _total coloring_ holding $f(u)\neq f(v)$ for each edge $uv$ and
$f(uv)\neq f(uw)$ for any two adjacent edges $uv,uw$, we call $f$ _proper
total coloring_. The number $\chi\,^{\prime\prime}(G)=\min_{f}\max\\{f(w):w\in
V(G)\cup E(G)\\}$ over all proper total colorings of $G$ is called _total
chromatic number_.

  4. B-4.

As $f$ is a vertex coloring (resp. an edge coloring, or a total coloring)
holding $f(u)\neq f(x)$ for any two vertices $u$ and $x$ (resp. for any two
edges, or for any two elements $u,x\in V(G)\cup E(G)$), that is,
$|f(V(G))|=|V(G)|$ (resp. $|f(E(G))|=|E(G)|$, or $|f(V(G)\cup
E(G))|=|V(G)|+|E(G)|$), we call $f$ _labeling_.

  5. B-5.

If a coloring/labeling $f$ satisfies a mathematical constraint or a group of
mathematical constraints, we say $f$ to be a _$W$ -constraint
coloring/labeling_.

The labelings and colorings of graph theory not defined here can be found in
[2], [4] and [36].

######  Definition 1.

[30, 41] A _Topcode-matrix_ $T_{code}(G)$ of a $(p,q)$-graph $G$ is defined as

$\centering{\begin{split}T_{code}(G)=\left(\begin{array}[]{ccccc}x_{1}&x_{2}&\cdots&x_{q}\\\
e_{1}&e_{2}&\cdots&e_{q}\\\
y_{1}&y_{2}&\cdots&y_{q}\end{array}\right)_{3\times
q}=\left(\begin{array}[]{cccccccccccccc}X\\\ E\\\
Y\end{array}\right)=(X,E,Y)^{T}\end{split}}\@add@centering$ (17)

where the _v-vector_ $X=(x_{1},x_{2},\dots,x_{q})$, the _e-vector_ $E=(e_{1}$,
$e_{2}$, $\dots$, $e_{q})$, and the _v-vector_ $Y=(y_{1},y_{2},\dots,y_{q})$
consist of non-negative integers $e_{i}$, $x_{i}$ and $y_{i}$ for $i\in[1,q]$.
We say $T_{code}(G)$ to be _evaluated_ if there exists a function $\theta$
such that $e_{i}=\theta(x_{i},y_{i})$ for $i\in[1,q]$, and call $x_{i}$ and
$y_{i}$ _ends_ of $e_{i}$, denoted as $e_{i}=x_{i}y_{i}$, and $q$ _size_ of
$T_{code}(G)$, such that $V(G)=X\cup Y$ and $E(G)=E$. $\square$

######  Definition 2.

∗ Suppose that a $(p,q)$-graph $G$ admits a $W$-constraint total coloring
$f:V(G)\cup E(G)\rightarrow[a,b]$. A _colored Topcode-matrix_ $T_{code}(G,f)$
of the graph $G$ is defined as

$\centering{\begin{split}T_{code}(G,f)=\left(\begin{array}[]{ccccc}f(x_{1})&f(x_{2})&\cdots&f(x_{q})\\\
f(x_{1}y_{1})&f(x_{2}y_{2})&\cdots&f(x_{q}y_{q})\\\
f(y_{1})&f(y_{2})&\cdots&f(y_{q})\end{array}\right)_{3\times
q}=\left(\begin{array}[]{cccccccccccccc}X_{f}\\\ E_{f}\\\
Y_{f}\end{array}\right)=(X_{f},E_{f},Y_{f})^{T}\end{split}}\@add@centering$
(18)

holding the $W$-constraint $f(x_{i}y_{i})=W\langle f(x_{i}),f(y_{i})\rangle$
for $i\in[1,q]$. Moreover, if $G$ is a bipartite graph with the vertex set
$V(G)=X^{v}\cup Y^{v}$ and $X^{v}\cap Y^{v}=\emptyset$, we stipulate $x_{i}\in
X^{v}$ and $y_{i}\in Y^{v}$ such that $X_{f}\cap Y_{f}=\emptyset$ in Eq.(18),
where “$W$-constraint” is a mathematical constraint, or a group of
mathematical constraints. $\square$

######  Remark 1.

In Definition 2, if the $(p,q)$-graph $G$ admits a $W$-constraint vertex
coloring $g:V(G)\rightarrow[\alpha,\beta]$, we have a colored Topcode-matrix
$T_{code}(G,g)$ of $G$ defined as

$\centering{\begin{split}T_{code}(G,g)=\left(\begin{array}[]{ccccc}g(x_{1})&g(x_{2})&\cdots&g(x_{q})\\\
x_{1}y_{1}&x_{2}y_{2}&\cdots&x_{q}y_{q}\\\
g(y_{1})&g(y_{2})&\cdots&g(y_{q})\end{array}\right)_{3\times
q}=\left(\begin{array}[]{cccccccccccccc}X_{g}\\\ E\\\
Y_{g}\end{array}\right)=(X_{g},E,Y_{g})^{T}\end{split}}\@add@centering$ (19)

If $G$ is a bipartite graph with the vertex set $V(G)=X^{v}\cup Y^{v}$ and
$X^{v}\cap Y^{v}=\emptyset$, we have $X_{g}\cap Y_{g}=\emptyset$, also,
$X_{g}=X^{v}$ and $Y_{g}=Y^{v}$. And, if the $(p,q)$-graph $G$ admits a
$W$-constraint edge coloring $h:E(G)\rightarrow[\lambda,\gamma]$, we have a
colored Topcode-matrix $T_{code}(G,h)$ of $G$ defined as

$\centering{\begin{split}T_{code}(G,h)=\left(\begin{array}[]{ccccc}x_{1}&x_{2}&\cdots&x_{q}\\\
h(x_{1}y_{1})&h(x_{2}y_{2})&\cdots&h(x_{q}y_{q})\\\
y_{1}&y_{2}&\cdots&y_{q}\end{array}\right)_{3\times
q}=\left(\begin{array}[]{cccccccccccccc}X\\\ E_{h}\\\
Y\end{array}\right)=(X,E_{h},Y)^{T}\end{split}}\@add@centering$ (20)

If $G$ is a bipartite graph with the vertex set $V(G)=X^{v}\cup Y^{v}$ and
$X^{v}\cap Y^{v}=\emptyset$, refer to that in Definition 2. $\parallel$

######  Remark 2.

In Definition 1, if each of elements $x_{i},e_{j},y_{k}$ in the v-vectors and
the e-vector is a _set_ (resp. graph, matrix, string), we call $T_{code}(G)$
_set-type Topcode-matrix_ (resp. _graph-type Topcode-matrix_ , _matrix-type
Topcode-matrix_ , _string-type Topcode-matrix_) in this article.

In other word, the generalization of a Topcode-matrix is that each of elements
in the Topcode-matrix is a _thing_ in the world, such that the Topcode-matrix
brings these $3q$ things together topologically by a mathematical constraint,
or a group of mathematical constraints for getting a completely mathematical
“story” [21].

About part of Topcode-matrix algebra, readers can refer to [38] and [40].
$\parallel$

####  1.4.2 Basic graph operations

Graph operations are the _soul_ of topological structures of graphs.

We introduce the graph operations often used. Let $G_{i}$ and $G_{j}$ be two
disjoint connected graphs in the following argument.

(1) Vertex-coinciding operation. We coincide a vertex $u$ of $G_{i}$ with one
vertex $x$ of $G_{j}$ into one vertex $w=u\odot x$, the resulting graph is
denoted as $G_{i}\odot G_{j}$, called a _vertex-coincided graph_ based on the
_graph vertex-coinciding operation_ “$\odot$”, such that the vertex $w\in
V(G_{i}\odot G_{j})$ has the degree
$\textrm{deg}_{G_{i}}(u)+\textrm{deg}_{G_{j}}(x)$, see an illustration in
Fig.5 from (a) to (b).

Figure 5: A scheme for illustrating the vertex-coinciding operation and the
edge-joining operation.

(2) Edge-joining operation. We use a new edge to join a vertex $u$ of $G_{i}$
with one vertex $x$ of $G_{j}$ together, so we get a connected graph
$G_{i}\ominus G_{j}$, called an _edge-joined graph_ based on the _graph edge-
joining operation_ “$\ominus$”, see an example shown in Fig.5 from (a) to (c).

(3) Vertex-splitting tree-operation. A _vertex-splitting operation_ on a
connected graph is defined as: Let $x$ be a vertex of a cycle $C$ of a
connected graph $G$, and $N(x)=\\{x_{1},x_{2},\dots,x_{d}\\}$ with
$d=\textrm{deg}_{G}(x)\geq 2$ be the neighbor set of the vertex $x$. We
vertex-split $x$ into two vertices $x\,^{\prime}$ and $x\,^{\prime\prime}$,
and let $x\,^{\prime}$ to join with vertices $x_{1},x_{2},\dots,x_{k}$ by
edges, and let $x\,^{\prime\prime}$ to join with vertices
$x_{k+1},x_{k+2},\dots,x_{d}$ by edges, the resultant graph is a connected
graph, denoted as $G\wedge x$ and called _vertex-split graph_. See an example
shown in Fig.5 from (b) to (a). Clearly, the number of cycles of the vertex-
split graph $G\wedge x$ is less than that of the original connected graph $G$.

If $G_{1}=G\wedge x$ has cycles, we do the vertex-splitting operation to
$G_{1}$. Go on in this way, we get a graph $G_{m}=G_{m-1}\wedge y$ to be a
tree $T$ for some $m$. The process of vertex-splitting $G$ into a tree $T$ is
called the _vertex-splitting tree-operation_ , and write $T=\wedge(G)$ and
$G=\wedge^{-1}(T)$, or $G=\odot_{m}(T)$.

######  Theorem 2.

Each connected $(p,q)$-graph $G$ corresponds to a set $V_{\textrm{split}}(G)$
of trees of $q+1$ vertices, such that $G=\wedge^{-1}(T)$, also,
$G=\odot_{m}(T)$ for each tree $T\in V_{\textrm{split}}(G)$.

Fig.6 shows a connected $(5,8)$-graph $G$ that can be vertex-split into trees
$G_{4}$ and $T_{4}$ of $8$ edges.

Figure 6:  A connected graph $G$ can be vertex-split into trees $G_{4}$ and
$T_{4}$.

######  Theorem 3.

[22, 47] Suppose that two connected graphs $G$ and $H$ admit a mapping
$f:V(G)\rightarrow V(H)$. In general, a vertex-split graph $G\wedge u$ with
$\textrm{deg}_{G}(u)\geq 2$ is not unique, so we have a vertex-split graph set
$S_{G}(u)=\\{G\wedge u\\}$, similarly, we have another vertex-split graph set
$S_{H}(f(u))=\\{H\wedge f(u)\\}$. If each vertex-split graph $L\in S_{G}(u)$
corresponds to another vertex-split graph $T\in S_{H}(f(u))$ such that $L\cong
T$, and vice versa, we write this fact as $G\wedge u\cong H\wedge f(u)$ for
each vertex $u\in V(G)$, then we claim that $G$ is _isomorphic_ to $H$, that
is $G\cong H$.

######  Remark 3.

Although each graph $G\wedge u$ keeps all of edges of $G$, and each graph
$H\wedge f(u)$ keeps all of edges of $H$, however, it is not easy to show
$G\wedge u\cong H\wedge f(u)$ for each vertex $u\in V(G)$ defined in Theorem
3. The authors in [47] have shown two parameters of graphs based on the split
connectivity:

The v-split connectivity. A _v-split $k$-connected graph_ $H$ holds: $H\wedge
V^{*}$ (or $H\wedge\\{x_{i}\\}^{k}_{1}$) is disconnected, where
$V^{*}=\\{x_{1},x_{2},\dots,x_{k}\\}$ is a subset of $V(H)$, each component
$H_{j}$ of $H\wedge\\{x_{i}\\}^{k}_{1}$ has at least a vertex $w_{j}\not\in
V^{*}$, $|V(H\wedge\\{x_{i}\\}^{k}_{1})|=k+|V(H)|$ and
$|E(H\wedge\\{x_{i}\\}^{k}_{1})|=|E(H)|$. The smallest number of $k$ for which
$H\wedge\\{x_{i}\\}^{k}_{1}$ is disconnected is called the _v-split
connectivity_ of $H$, denoted as $\kappa_{d}(H)$ (see an example shown in
Fig.7).

The e-split connectivity. An _e-split $k$-connected graph_ $H$ holds:
$H\wedge\\{e_{i}\\}^{k}_{1}$ (or $H\wedge E^{*}$) is disconnected, where
$E^{*}=\\{e_{1},e_{2},\dots,e_{k}\\}$ is a subset of $E(H)$, each component
$H_{j}$ of $H\wedge\\{e_{i}\\}^{k}_{1}$ has at least a vertex $w_{j}$ being
not any end of any edge of $E^{*}$,
$|V(H\wedge\\{e_{i}\\}^{k}_{1})|=2k+|V(H)|$ and
$|E(H\wedge\\{e_{i}\\}^{k}_{1})|=k+|E(H)|$. The smallest number of $k$ for
which $H\wedge\\{e_{i}\\}^{k}_{1}$ is disconnected is called the _e-split
connectivity_ of $H$, denoted as $\kappa^{\prime}_{d}(H)$ (see an example
shown in Figure 7). $\parallel$

######  Lemma 4.

[47] A graph $G$ is $k$-connected if and only if it is v-divided
$k$-connected, namely, $\kappa_{d}(H)=\kappa(H)$.

######  Theorem 5.

[47] If a $k$-connected graph has a property related with its
$k$-connectivity, so do a $v$-divided $k$-connected graph.

######  Theorem 6.

[47] Any connected graph $G$ holds the inequalities
$\kappa^{\prime}_{d}(G)\leq\kappa_{d}(G)\leq 2\kappa^{\prime}_{d}(G)$ true,
and the boundaries are reachable.

Figure 7: (a) A graph $H$ with minimum degree $\delta(H)=4$; (b) an e-split
graph $H\wedge xw$ with $\kappa^{\prime}_{d}(H)=1$; (c) a v-split graph
$H\wedge\\{x,w\\}$ with $\kappa_{d}(H)=2$; (d) a v-deleted graph $H-\\{x,w\\}$
with $\kappa(H)=2$; (e) an e-deleted graph $H-\\{yx,yw,yu,yv\\}$ with
$\kappa^{\prime}(H)=4$, cited from [47].

(4) [50] Adding leaves operation. A graph operation called “adding leaves
operation” is defined as: Adding new vertices $w_{1},w_{2},\dots,w_{r}$ to a
graph $G$, and join each new vertex $w_{i}$ with some vertex $z_{i}$ of $G$ by
an edge $w_{i}z_{i}$, the resultant graph is denoted as $G+L_{eaf}(w)$, called
_leaf-added graph_ , where the leaf set
$L_{eaf}(w)=\\{w_{1},w_{2},\dots,w_{r}\\}$, and each vertex $w_{i}$ is called
a _leaf_ of $G+L_{eaf}(w)$. Conversely, removing all leaves of a graph $H$
produces a graph $H-L_{eaf}(H)$, where $L_{eaf}(H)$ is the set of all leaves
of the graph $H$.

We will use the following trees in the later sections: Let $T$ be a tree with
diameter $D(T)$ not less than 3, and let $L(T)$ be the set of all leaves of
the tree $T$. We have trees $T_{i+1}=T_{i}-L(T_{i})$ with $i\in[1,m]$ obtained
by removing all leaves of the leaf set $L(T_{i})$ such that $T_{m+1}$ is just
a star $K_{1,n}$ being a tree with diameter $D(K_{1,n})\leq 2$ and $n\geq 1$,
where $T_{1}=T$ and $m\geq 1$. Then we have a formula

$m+1=\left\lceil\frac{D(T)}{2}\right\rceil$ (21)

See examples shown Fig.8, we can see

(i) Trees $G_{i+1}=G_{i}-L(G_{i})$ for $i=1,2$, and $G_{3}=K_{1,1}$ is a star
of two vertices and diameter one, such that
$2+1=\left\lceil\frac{D(G_{1})}{2}\right\rceil=\left\lceil 2.5\right\rceil=3$.

(ii) Trees $T_{j+1}=T_{j}-L(T_{j})$ for $j=1,2$, and $T_{3}=K_{1,2}$ is a star
of three vertices and diameter two, such that
$2+1=\left\lceil\frac{D(T_{1})}{2}\right\rceil=\left\lceil 3\right\rceil=3$.

Figure 8:  (a) A tree $G_{1}$ with $D(G_{1})=5$; (b) a tree $G_{2}$ obtained
by removing all leaves of $G_{1}$; (c) a tree $G_{3}$ obtained by removing all
leaves of $G_{2}$; (d) a tree $T_{1}$ with $D(T_{1})=6$; (e) a tree $T_{2}$
obtained by removing all leaves of $T_{1}$; (f) a tree $T_{3}$ obtained by
removing all leaves of $T_{2}$.

##  2 Parameterized total colorings

###  2.1 Basic labelings and colorings

Acharya and Hegde, in [1], introduced $(k,d)$-arithmetic labeling as: Let $G$
be a graph with $q$ edges and let $k$ and $d$ be positive integers. A labeling
$f$ of $G$ is said to be $(k,d)$-arithmetic if the vertex labels are distinct
nonnegative integers and the edge labels induced by $f(x)+f(y)$ for each edge
$xy$ are $k,k+d,k+2d,\dots,k+(q-1)d$. Clearly, this graph $G$ must be
_bipartite_.

Notice that a $(k,d)$-arithmetic labeling can induce a _strongly c-elegant
labeling_ introduced by Chang, Hsu, and Rogers [4], and moreover a strongly
$c$-elegant labeling is felicitous too.

######  Definition 3.

[10] If there exists a constant $k\geq 0$, such that a $(p,q)$-graph $G$
admits a total labeling $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]$ true, we call
$f$ _edge-magic graceful labeling_ of $G$, and $k$ a _magic constant_.
Moreover, $f$ is called _super edge-magic graceful labeling_ if the vertex
color set $f(V(G))=[1,p]$. $\square$

######  Definition 4.

[6] For a $(p,q)$-graph $G$, if there is a total labeling $f$ such that the
vertex color set $f(V(G))\subseteq S_{b,0,0,d}\cup S_{q-1,k,0,d}$ and the edge
color set

$f(E(G))=\\{|f(u)-f(v)|;\ uv\in E(G)\\}=S_{q-1,k,0,d}$

then we call $f$ _$(k,d)$ -graceful labeling_ of $G$. $\square$

In Definition 4, as $d=1$, $f$ is called a _$k$ -graceful labeling_ of $G$; as
$(k,d)=(1,2)$, $f$ is called an _odd-graceful labeling_ of $G$.

######  Definition 5.

[1] For a $(p,q)$-graph $G$, if there is a total labeling $f$ such that the
vertex color set $f(V(G))\subseteq S_{b,0,0,d}\cup S_{q-1,k,0,d}$ and the edge
color set

$f(E(G))=\\{f(xy)=f(x)+f(y):xy\in E(G)\\}=S_{q-1,k,0,d}$

then we call $f$ $(k,d)$-_arithmetic labeling_ of $G$. $\square$

######  Definition 6.

[28] If a $(p,q)$-graph $G$ admits a mapping $h:V(G)\rightarrow
S_{b,0,0,d}\cup S_{q-1,k,0,d}$ with integers $k\geq 0$ and $d\geq 1$, such
that $f(x)\neq f(y)$ for any pair of vertices $x,y$ of $G$, and each edge
$uv\in E(G)$ is colored by $h(uv)=h(u)+h(v)~{}(\bmod^{*}~{}qd)$ defined as
$h(uv)-k=[h(u)+h(v)-k](\bmod~{}qd)$, and the edge color set

$h(E(G))=S_{q-1,k,0,d}=\\{k,k+d,\dots,k+(q-1)d\\}$

then we call $h$ _$(k,d)$ -harmonious labeling_ of $G$. $\square$

Motivated from the parameterized labelings: the $(k,d)$-arithmetic labeling,
the $(k,d)$-graceful labeling, the $(k,d)$-harmonious labeling and the new
$(k,d)$-type labelings introduced in [20], as well as the well-defined
parameterized labelings, we present the following parameterized total
colorings.

######  Definition 7.

[26, 36] Let $G$ be a bipartite and connected $(p,q)$-graph, so its vertex set
$V(G)=X\cup Y$ with $X\cap Y=\emptyset$ such that each edge $uv\in E(G)$ holds
$u\in X$ and $v\in Y$. If there is a total mapping

${\begin{split}&f:X\rightarrow S_{m,0,0,d}=\\{0,d,\dots,md\\}\\\ &f:Y\cup
E(G)\rightarrow S_{n,k,0,d}=\\{k,k+d,\dots,k+nd\\}\end{split}}$ (22)

here it is allowed $f(x)=f(y)$ for some distinct vertices $x,y\in V(G)$. Let
$c$ be a fixed non-negative integer.

  1. Ptol-1.

If $f(uv)=|f(u)-f(v)|$ for each edge $uv\in E(G)$, and the edge color set
$f(E(G))=S_{q-1,k,0,d}$, and the vertex color set

$f(V(G)\cup E(G))\subseteq S_{m,0,0,d}\cup S_{q-1,k,0,d}$

then $f$ is called a _graceful $(k,d)$-total coloring_; and moreover $f$ is
called a _strongly graceful $(k,d)$-total coloring_ if $f(x)+f(y)=k+(q-1)d$
for each matching edge $xy$ of a perfect matching $M$ of $G$.

  2. Ptol-2.

If $f(uv)=|f(u)-f(v)|$ for each edge $uv\in E(G)$, and the edge color set
$f(E(G))=O_{2q-1,k,d}$, and the vertex color set

$f(V(G)\cup E(G))\subseteq S_{m,0,0,d}\cup S_{2q-1,k,0,d}$

then $f$ is called an _odd-graceful $(k,d)$-total coloring_; and moreover $f$
is called a _strongly odd-graceful $(k,d)$-total coloring_ if
$f(x)+f(y)=k+(2q-1)d$ for each matching edge $xy$ of a perfect matching $M$ of
$G$.

  3. Ptol-3.

If the mixed color set

$\\{f(u)+f(uv)+f(v):uv\in E(G)\\}=\\{2k+2ad,2k+2(a+1)d,\dots,2k+2(a+q-1)d\\}$

with $a\geq 0$ and the total color set $f(V(G)\cup E(G))\subseteq
S_{m,0,0,d}\cup S_{2(a+q-1),k,a,d}$, then $f$ is called an _edge-antimagic
$(k,d)$-total coloring_.

  4. Ptol-4.

If $f(uv)=f(u)+f(v)~{}(\bmod^{*}qd)$ defined by
$f(uv)-k=[f(u)+f(v)-k](\bmod~{}qd)$ for each edge $uv\in E(G)$, and the edge
color set $f(E(G))=S_{q-1,k,0,d}$, then $f$ is called a _harmonious
$(k,d)$-total coloring_.

  5. Ptol-5.

If $f(uv)=f(u)+f(v)~{}(\bmod^{*}qd)$ defined by
$f(uv)-k=[f(u)+f(v)-k](\bmod~{}2qd)$ for each edge $uv\in E(G)$, and the edge
color set $f(E(G))=O_{2q-1,k,d}$, then $f$ is called an _odd-elegant
$(k,d)$-total coloring_.

——— Four $W$-magic types:

  6. Ptol-6.

If there are the edge-magic constraint

$f(u)+f(uv)+f(v)=c,~{}uv\in E(G)$ (23)

the edge color set $f(E(G))=S_{q-1,k,0,d}$ and the total color set
$f((V(G)\cup E(G))\subseteq S_{m,0,0,d}\cup S_{q-1,k,0,d}$, then $f$ is called
an _edge-magic $(k,d)$-total coloring_. And moreover, $f$ is called a _pseudo-
edge-magic $(k,d)$-total coloring_ if both $|f(E(G))|<q$ and Eq.(23) hold
true.

  7. Ptol-7.

If there are the edge-difference constraint

$f(uv)+|f(u)-f(v)|=c,~{}uv\in E(G)$ (24)

and the edge color set $f(E(G))=S_{q-1,k,0,d}$, then $f$ is called an _edge-
difference $(k,d)$-total coloring_. And moreover $f$ is called a _pseudo-edge-
difference $(k,d)$-total coloring_ if both $|f(E(G))|<q$ and Eq.(24) hold
true.

  8. Ptol-8.

If there are the graceful-difference constraint

$\big{|}|f(u)-f(v)|-f(uv)\big{|}=c,~{}uv\in E(G)$ (25)

and the edge color set $f(E(G))=S_{q-1,k,0,d}$, then we call $f$ _graceful-
difference $(k,d)$-total coloring_. And moreover $f$ is called a _pseudo-
graceful-difference $(k,d)$-total coloring_ if both $|f(E(G))|<q$ and Eq.(25)
hold true.

  9. Ptol-9.

If there are the felicitous-difference constraint

$|f(u)+f(v)-f(uv)|=c,~{}uv\in E(G)$ (26)

and the edge color set $f(E(G))=S_{q-1,k,0,d}$, then we call $f$ _felicitous-
difference $(k,d)$-total coloring_. And moreover $f$ is called a _pseudo-
felicitous-difference $(k,d)$-total coloring_ if both $|f(E(G))|<q$ and
Eq.(26) hold true. $\square$

######  Definition 8.

[34] Let $G$ be a bipartite and connected $(p,q)$-graph with vertex set
$V(G)=X\cup Y$, and $X\cap Y=\emptyset$. There is a total coloring

${\begin{split}&h:X\rightarrow S_{m,0,0,d}\\\ &h:Y\cup E(G)\rightarrow
S_{n,k,0,d}\cup O_{2q-1,k,d}\end{split}}$

with integers $k\geq 0$ and $d\geq 1$. Let $c$ be an non-negative integer.

(i) If there are the edge-magic constraint $h(u)+h(uv)+h(v)=c$ for each edge
$uv\in E(G)$ and the edge color set $h(E(G))=O_{2q-1,k,d}$, then $h$ is called
an _odd-edge edge-magic $(k,d)$-total labeling_ when $|h(V(G))|=p$; and
moreover $h$ is called an _odd-edge edge-magic $(k,d)$-total coloring_ when
the vertex color set cardinality $|h(V(G))|<p$.

(ii) If there are the edge-difference constraint $h(uv)+|h(u)-h(v)|=c$ for
each edge $uv\in E(G)$ and the edge color set $h(E(G))=O_{2q-1,k,d}$, then $h$
is called an _odd-edge edge-difference $(k,d)$-total labeling_ when
$|h(V(G))|=p$; and furthermore $h$ is called an _odd-edge edge-difference
$(k,d)$-total coloring_ when the vertex color set cardinality $|h(V(G))|<p$.

(iii) If there are the felicitous-difference constraint $|h(u)+h(v)-h(uv)|=c$
for each edge $uv\in E(G)$ and the edge color set $h(E(G))=O_{2q-1,k,d}$, then
$h$ is called an _odd-edge felicitous-difference $(k,d)$-total labeling_ when
$|h(V(G))|=p$; and moreover $h$ is called an _odd-edge felicitous-difference
$(k,d)$-total coloring_ when the vertex color set cardinality $|h(V(G))|<p$.

(vi) If there are the graceful-difference constraint
$\big{|}|h(u)-h(v)|-h(uv)\big{|}=c$ for each edge $uv\in E(G)$ and the edge
color set $h(E(G))=O_{2q-1,k,d}$, then $h$ is called an _odd-edge graceful-
difference $(k,d)$-total labeling_ when $|h(V(G))|=p$; and furthermore $h$ is
called an _odd-edge graceful-difference $(k,d)$-total coloring_ when the
vertex color set cardinality $|h(V(G))|<p$. $\square$

######  Remark 4.

In general, we call $f$ _$W$ -constraint $(k,d)$-total coloring_ if the
$W$-constraint $f(uv)=W\langle f(u),f(v)\rangle$ holds true, and the edge
color set $f(E(G))$ hold one of the well-defined total colorings defined in
Definition 7 and Definition 8.

  1. (1)

There are new parameters of graphs based on Definition 7 and Definition 8. For
a graph $G$, we have two $W$-constraint $(k,d)$-total colorings $g_{\min}$ and
$g_{\max}$ of $G$ such that

$|g_{\min}(V(G))|\leq|g(V(G))|\leq|g_{\max}(V(G))|$

for each $W$-constraint $(k,d)$-total coloring $g$ of $G$.

As this $W$-constraint $(k,d)$-total coloring is a graceful $(1,1)$-total
coloring $g_{\max}$ of a tree $T$ means that the maximal number
$|g_{\max}(V(T))|$ is close to a graceful labeling of $T$. Graceful Tree
Conjecture [11, 4] says $|g_{\max}(V(T))|=|V(T)|$.

As this $W$-constraint $(k,d)$-total coloring is the graceful $(k,d)$-total
coloring, then a graceful $(1,2)$-total coloring $g_{\max}$ of a tree $T$
means that the maximal number $|g_{\max}(V(T))|$ is close to an odd-graceful
labeling of $T$. Gnanajothi proposed Odd-graceful Tree Conjecture [5] as
$|g_{\max}(V(T))|=|V(T)|$.

As this $W$-constraint $(k,d)$-total coloring is a strongly graceful coloring,
Wang and Yao, in [45], have proven that two conjectures Graceful Tree
Conjecture and Strongly Graceful Tree Conjecture are equivalent from each
other.

As this $W$-constraint $(k,d)$-total coloring is an edge-magic $(k,d)$-total
labeling: In 1970, Anton Kotzig and Alex Rosa defined an _edge-magic total
labeling_ of a $(p,q)$-graph $G$ as a bijective mapping $f$ from $V(G)\cup
E(G)$ to $[1,p+q]$ such that for any edge $uv$, $f(u)+f(v)+f(uv)=c$, where $c$
is a fixed constant. Moreover, they conjectured: _Every tree admits an edge-
magic total labeling_.

  2. (2)

A $W$-constraint $(k,d)$-total coloring $f$ defined in Definition 7 is
_proper_ if $f(u)\neq f(v)$ for each edge $uv\in E(G)$, and $f(uv)\neq f(uw)$
for any two adjacent edges $uv,uw\in E(G)$. So we call $f$ a _$W$ -constraint
proper $(k,d)$-total coloring_ of $G$. Investigating various $W$-constraint
proper $(k,d)$-total colorings of graphs is interesting and challenging.

  3. (3)

In practical application, we may reduce the restrictions of some
$W$-constraint $(k,d)$-total colorings of graphs, such as a $W$-constraint
$(k,d)$-total coloring $g$ of a bipartite graph $G$ with vertex bipartition
$(X,Y)$ holds

$g:X\rightarrow\\{-md,-(m-1)d,\dots,-2d,-d\\}\cup\\{0,d,\dots,md\\}$

and

${\begin{split}g:Y\cup
E(G)\rightarrow&\\{-k,-k-d,\dots,-k-nd\\}\cup\\{-k+d,-k+2d,\dots,-k+nd\\}\\\
&\cup\\{k-d,k-2d,\dots,k-nd\\}\cup\\{k,k+d,\dots,k+nd\\}\end{split}}$

where integers $m,n,k$ and $d$ are non-negative integers. $\parallel$

######  Definition 9.

∗ A $(p,q)$-graph $G$ admits a _$W$ -constraint $(k,d)$-total
$(vd$-$ek)$-coloring_ $f$ defined as

${\begin{split}&f:V(G)\rightarrow S_{m,0,0,d}=\\{0,d,\dots,md\\}\\\
&f:E(G)\rightarrow S_{n,k,0,d}=\\{k,k+d,\dots,k+nd\\}\end{split}}$ (27)

and each edge $uv\in E(G)$ holds the $W$-constraint $f(uv)=W\langle
f(u),f(v)\rangle$ for integers $k\geq 0$ and $d\geq 1$. Moreover, $f$ is
called a _$W$ -constraint $(k,d)$-total $(vd$-$ek)$-all-labeling_ if the
vertex color set $f(V(G))=S_{p-1,0,0,d}$, the edge color set
$f(E(G))=S_{p-1,k,0,d}$, and each edge $uv\in E(G)$ holds the $W$-constraint
$f(uv)=W\langle f(u),f(v)\rangle$ for integers $k\geq 0$ and $d\geq 1$.
$\square$

######  Definition 10.

∗ A $(p,q)$-graph $G$ admits a _$W$ -constraint $(k,d)$-total
$(vk$-$ed)$-coloring_ $g$ defined as

${\begin{split}&g:V(G)\rightarrow S_{n,k,0,d}=\\{k,k+d,\dots,k+nd\\}\\\
&g:E(G)\rightarrow S_{m,0,0,d}=\\{0,d,\dots,md\\}\end{split}}$ (28)

and each edge $uv\in E(G)$ holds the $W$-constraint $g(uv)=W\langle
g(u),g(v)\rangle$ for integers $k\geq 0$ and $d\geq 1$. Especially, $g$ is
called a _$W$ -constraint $(k,d)$-total $(vk$-$ed)$-all-labeling_ if the
vertex color set $f(V(G))=S_{p-1,k,0,d}$, the edge color set
$f(E(G))=S_{p-1,0,0,d}$, and each edge $uv\in E(G)$ holds the $W$-constraint
$f(uv)=W\langle f(u),f(v)\rangle$ for integers $k\geq 0$ and $d\geq 1$.
$\square$

######  Definition 11.

∗ For integers $k\geq 0$ and $d\geq 1$, a $(p,q)$-graph $G$ admits a _graceful
$(k,d)$-total model-coloring_ $h$ is defined as

$h:V(G)\cup E(G)\rightarrow S_{m,0,0,d}\cup
S_{q-1,k,0,d}=\\{0,d,\dots,md\\}\cup\\{k,k+d,\dots,k+(q-1)d\\}$ (29)

such that each edge $uv\in E(G)$ holds $h(uv)=|h(u)-h(v)~{}(\bmod^{*}~{}qd)|$,
and the edge color set

$h(E(G))=S_{p-1,k,0,d}=\\{k,k+d,\dots,k+(q-1)d\\}$

where

$h(u)-h(v)~{}(\bmod^{*}~{}qd)=k+(q-r)d$

if $h(u)-h(v)=k-rd$ (or $h(u)-h(v)=-k+rd$) for $r\geq 2$. $\square$

######  Example 1.

In Fig.9 (a) and (b), a tree $G_{1}$ admits a graceful-difference
$(k,d)$-total labeling $h_{1}$ holding the graceful-difference constraint

$\big{|}|h_{1}(u)-h_{1}(v)|-h_{1}(uv)\big{|}=d,~{}uv\in E(G_{1})$

and the edge color set $h_{1}(E(G_{1}))=S_{5,k,0,d}$; and a tree $G_{2}$
admits a graceful $(k,d)$-total model-coloring $h_{2}$ holding
$h_{2}(uv)=|h_{2}(u)-h_{2}(v)~{}(\bmod^{*}~{}6d)|$ for each edge $uv\in
E(G_{2})$ and the edge color set $h_{2}(E(G_{2}))=S_{5,k,0,d}$, refer to
Definition 11. Since $h_{1}(x)+h_{2}(x)=k+6d$ for each vertex $x\in
V(G_{1})=V(G_{2})$, we say that $h_{i}$ is the _totally vertex-dual coloring_
of $h_{3-i}$ for $i=1,2$.

A colored tree $G_{3}$ shown in Fig.9 (c) admits an edge-difference
$(k,d)$-total $(vd$-$ek)$-all-labeling $h_{3}$ holding the edge-difference
constraint

$h_{3}(uv)+|h_{3}(u)-h_{3}(v)|=k+7d,~{}uv\in E(G_{3})$

according to Definition 9. By Definition 10, another colored tree $G_{4}$
shown in Fig.9 (d) admits a graceful-difference $(k,d)$-total $(vk$-$ed)$-all-
labeling $h_{4}$ holding the graceful-difference constraint

$\big{|}|h_{4}(u)-h_{4}(v)|-h_{4}(uv)\big{|}=0,~{}uv\in E(G_{4})$

Notice that $|h_{3}(v)-h_{4}(v)|=k$ for each vertex $v\in V(G_{3})=V(G_{4})$,
since $G_{3}\cong G_{4}$. So, $h_{j}$ is the _totally vertex-dual coloring_ of
$h_{7-j}$ for $j=3,4$. Moreover, we have $h_{3}(xy)+h_{4}(xy)=k+7d$ for each
edge $xy\in E(G_{3})=E(G_{4})$, then $h_{j}$ is the _totally edge-dual
coloring_ of $h_{7-j}$ for $j=3,4$. Totally, $h_{j}$ is the _total-dual
coloring_ of $h_{7-j}$ for $j=3,4$. $\square$

Figure 9: (a) and (b) are two totally vertex-dual colorings holding
$g_{1}(u)+g_{2}(u)=k+6d$; (b), (c) and (d) are three new $(k,d)$-total
colorings/labelings defined in Definition 9, Definition 10 and Definition 11.

For the topological authentication, we present the following three
definitions: Definition 12, Definition 13 and Definition 14.

######  Definition 12.

∗ For integers $k\geq 0$ and $d\geq 1$, a $(p,q)$-graph $G$ (as a _public-
key_) admits a $W_{i}$-constraint $(k,d)$-total coloring $f$, and another
$(p,q\,^{\prime})$-graph $H$ (as a _private-key_) admits a $W_{j}$-constraint
$(k,d)$-total coloring $g$, and there is a bijection $\theta:V(G)\rightarrow
V(H)$. If there are integers $a,r\geq 1$, such that $f(x)+g[\theta(x)]=a\cdot
k+r\cdot d$ for each vertex $x\in V(G)$, then we call $f$ (resp. $g$) _vertex-
dual $(k,d)$-total coloring_ of $g$ (resp. $f$). $\square$

######  Definition 13.

∗ For integers $k\geq 0$ and $d\geq 1$, a $(p,q)$-graph $G$ (as a _public-
key_) admits a $W_{i}$-constraint $(k,d)$-total coloring $f$, and another
$(p\,^{\prime},q)$-graph $H$ (as a _private-key_) admits a $W_{j}$-constraint
$(k,d)$-total coloring $g$, and there is an edge bijection
$\pi:E(G)\rightarrow E(H)$. If there are integers $b,r\geq 1$, such that
$f(xy)+g[\pi(xy)]=b\cdot k+r\cdot d$ for each edge $xy\in E(G)$, then we call
$f$ (resp. $g$) _edge-dual $(k,d)$-total coloring_ of $g$ (resp. $f$).
$\square$

######  Definition 14.

∗ For integers $k\geq 0$ and $d\geq 1$, a $(p,q)$-graph $G$ (as a _public-
key_) admits a $W_{i}$-constraint $(k,d)$-total coloring $f$, and another
$(p\,^{\prime},q)$-graph $H$ (as a _private-key_) admits a $W_{j}$-constraint
$(k,d)$-total coloring $g$, and there are a bijection $\theta:V(G)\rightarrow
V(H)$ and an edge bijection $\phi:E(G)\rightarrow E(H)$. If there are integers
$a,b,r,s\geq 1$, such that

$f(x)+g[\theta(x)]=a\cdot k+r\cdot d$ for each vertex $x\in V(G)$ and

$f(xy)+g[\phi(xy)]=b\cdot k+s\cdot d$ for each edge $xy\in E(G)$,
then $f$ is called (resp. $g$) _$(v,e)$ -dual $(k,d)$-total coloring_ of $g$
(resp. $f$). $\square$

######  Example 2.

In Fig.10, we can see the following facts:

  1. Ex-1.

Two trees $H_{r}\not\cong H_{s}$ for $r\neq s$ and $r,s\in[1,4]$.

  2. Ex-2.

Each tree $H_{l}$ for $l\in[1,3]$ admits a graceful $(k,d)$-total coloring
$h_{l}$ holding $h_{l}(uv)=|h_{l}(u)-h_{l}(v)|$ for each edge $uv\in
E(H_{l})$.

  3. Ex-3.

Each tree $H_{t}$ for $t=4,5$ admits an edge-difference $(k,d)$-total coloring
$h_{t}$ holding the edge-difference constraint

$h_{t}(uv)+|h_{t}(u)-h_{t}(v)|=2k+5d,\quad uv\in E(H_{t})$

  4. Ex-4.

There is a bijection $\theta_{1,i}:V(H_{1})\rightarrow V(H_{i})$ for
$i\in[2,5]$, such that each vertex $x_{j}\in V(H_{1})$ holds
$\theta_{1,i}(x_{j})=A_{j}$ for $j\in[1,7]$ and $A\in\\{y,u,v,w\\}$. Moreover,
we get

$h_{1}(x_{j})+h_{i}[\theta_{1,i}(x_{j})]=k+6d,~{}i\in[2,5],~{}j\in[1,7],~{}A\in\\{y,u,v,w\\}$

and claim that each coloring $h_{i}$ is a _vertex-dual $(k,d)$-total coloring_
of the graceful $(k,d)$-total coloring $h_{1}$ by Definition 12.

  5. Ex-5.

About two trees $H_{1}$ and $H_{2}$, we have an edge bijection
$\varepsilon_{1,2}:E(H_{1})\rightarrow E(H_{2})$, where
$\varepsilon_{1,2}(x_{1}x_{2})=y_{4}y_{7}$,
$\varepsilon_{1,2}(x_{2}x_{3})=y_{4}y_{5}$,
$\varepsilon_{1,2}(x_{2}x_{6})=y_{6}y_{5}$,
$\varepsilon_{1,2}(x_{5}x_{6})=y_{2}y_{6}$,
$\varepsilon_{1,2}(x_{6}x_{7})=y_{2}y_{3}$,
$\varepsilon_{1,2}(x_{4}x_{7})=y_{1}y_{2}$, such that each edge $x_{i}x_{j}\in
E(H_{1})$ holds

$h_{1}(x_{i}x_{j})+h_{2}[\varphi_{1,2}(x_{i}x_{j})]=2k+5d$

Thereby, the coloring $h_{2}$ is an _edge-dual $(k,d)$-total coloring_ of
$h_{1}$ according to Definition 13. Moreover, the coloring $h_{2}$ is an
_$(v,e)$ -dual $(k,d)$-total coloring_ of $h_{1}$ in term of Definition 14.
$\square$

Figure 10: Examples for illustrating Definition 12, Definition 13 and
Definition 14.

######  Problem 6.

For a given $(p,q)$-graph $G$ (as a _public-key_) admitting a
$W_{i}$-constraint $(k,d)$-total coloring $f$, determine another
$(p,q\,^{\prime})$-graph $H$ (as a _private-key_) admitting a
$W_{j}$-constraint $(k,d)$-total coloring $g$, such that $f$ (resp. $g$) is a
_vertex-dual $(k,d)$-total coloring_ of $g$ (resp. $f$) defined in Definition
12. Do the same works according to Definition 13 and Definition 14,
respectively.

######  Remark 5.

About Problem 6, if $G=H$ is a tree admitting a set-ordered graceful labeling,
then we can find the vertex-dual $(k,d)$-total coloring, the edge-dual
$(k,d)$-total coloring and the $(v,e)$-dual $(k,d)$-total coloring. However,
finding these colorings for $G\not\cong H$, or $G$ and $H$ being not trees in
Problem 6 is important and difficult in the real application of information
security. $\parallel$

###  2.2 Labelings and results on disconnected graphs

######  Theorem 7.

[39] Let $G_{1},G_{2},\dots,G_{m}$ be disjoint connected graphs, and $E^{*}$
be an edge set such that each edge $uv$ of $E^{*}$ has one end $u$ in some
$G_{i}$ and another end $v$ is in some $G_{j}$ with $i\neq j$, and $E^{*}$
joins $G_{1},G_{2},\dots,G_{m}$ together to form a connected graph $H$,
denoted as $H=G+E^{*}$, where $G=\bigcup^{m}_{i=1}G_{i}$. We say
$G=\bigcup^{m}_{i=1}G_{i}$ to be a disconnected $(p,q)$-graph with

$p=|V(H)|=\sum^{m}_{i=1}|V(G_{i})|,\quad
q=|E(H)|-|E^{*}|=\left(\sum^{m}_{i=1}|E(G_{i})|\right)-|E^{*}|$

If $H$ admits an $\alpha$-labeling shown in the following:

  1. _Flawed_ -1.

$\alpha$ is a graceful labeling, or a set-ordered graceful labeling, or
graceful-intersection total set-labeling, or a graceful group-labeling.

  2. _Flawed_ -2.

$\alpha$ is an odd-graceful labeling, or a set-ordered odd-graceful labeling,
or an edge-odd-graceful total labeling, or an odd-graceful-intersection total
set-labeling, or an odd-graceful group-labeling, or a perfect odd-graceful
labeling.

  3. _Flawed_ -3.

$\alpha$ is an elegant labeling, or an odd-elegant labeling.

  4. _Flawed_ -4.

$\alpha$ is an edge-magic total labeling, or a super edge-magic total
labeling, or super set-ordered edge-magic total labeling, or an edge-magic
total graceful labeling.

  5. _Flawed_ -5.

$\alpha$ is an edge-antimagic $(k,d)$-total labeling, or a $(k,d)$-arithmetic.

  6. _Flawed_ -6.

$\alpha$ is a relaxed edge-magic total labeling.

  7. _Flawed_ -7.

$\alpha$ is an odd-edge-magic matching labeling, or an ee-difference odd-edge-
magic matching labeling.

  8. _Flawed_ -8.

$\alpha$ is a 6C-labeling, or an odd-6C-labeling.

  9. _Flawed_ -9.

$\alpha$ is an ee-difference graceful-magic matching labeling.

  10. _Flawed_ -10.

$\alpha$ is a difference-sum labeling, or a felicitous-sum labeling.

  11. _Flawed_ -11.

$\alpha$ is a multiple edge-meaning vertex labeling.

  12. _Flawed_ -12.

$\alpha$ is a perfect $\varepsilon$-labeling.

  13. _Flawed_ -13.

$\alpha$ is an image-labeling, or a $(k,d)$-harmonious image-labeling.

  14. _Flawed_ -14.

$\alpha$ is a twin $(k,d)$-labeling, or a twin Fibonacci-type graph-labeling,
or a twin odd-graceful labeling.

Then $G$ admits a _flawed $\alpha$-labeling_ too. $\square$

######  Theorem 8.

[39] Let $G=\bigcup^{m}_{i=1}G_{i}$ be a forest with components
$G_{1},G_{2},\dots,G_{m}$, where each $G_{i}$ is a $(p_{i},p_{i}-1)$-tree with
vertex partition $(X_{i},Y_{i})$ and admits a set-ordered graceful labeling
$f_{i}$ holding $\max f_{i}(X_{i})<\min f_{i}(Y_{i})$ true for $i\in[1,m]$.
Then $G$ admits a flawed set-ordered graceful labeling.

###### Proof.

Suppose that the vertex partitions $(X_{i},Y_{i})$ consists of
$X_{i}=\\{x_{i,j}:~{}j\in[1,s_{i}]\\}$ and
$Y_{i}=\\{y_{i,j}:~{}j\in[1,t_{i}]\\}$ with $i\in[1,m]$. Let
$M=\sum^{m}_{k=1}s_{k}$ and $N=\sum^{m}_{k=1}t_{k}$. Furthermore,

$0\leq\max f_{i}(X_{i})<\min f_{i}(x_{i,j+1})\leq s_{i}-1,~{}j\in[1,s_{i}]$

and

$s_{i}\leq f_{i}(y_{i,j})<f_{i}(y_{i,j+1})\leq
s_{i}+t_{i}-1=p_{i}-1,~{}j\in[1,t_{i}],~{}i\in[1,m]$

We defined a new labeling $g$ for the forest $G$ as follows:

(1) $g(x_{1,j})=f_{1}(x_{1,j})$ with $j\in[1,s_{1}]$.

(2) $g(x_{i,j})=f_{i}(x_{i,j})+\sum^{i-1}_{k=1}s_{k}$ for $j\in[1,s_{i}]$ and
$i\in[2,m]$.

(3) $g(y_{m,j})=f_{m}(y_{m,j})+M-s_{m}$ with $j\in[1,t_{m}]$.

(4) $g(y_{\ell,j})=f_{\ell}(y_{\ell,j})+M+\sum^{m-\ell}_{k=1}t_{k}$ for
$j\in[1,t_{\ell}]$ and $\ell\in[1,m-1]$.

Clearly,

$0=g(x_{1,1})\leq g(u)<g(v)\leq g(y_{1,t_{1}})=M+N-1$ (30)

for $u\in\bigcup^{m}_{i=1}X_{i}$ and $v\in\bigcup^{m}_{i=1}Y_{i}$.

Notice that each edge color set

$f_{i}(E(G_{i}))=[1,p_{i}-1]=\\{f_{i}(y_{i,a})-f_{i}(x_{i,b}):~{}x_{i,b}y_{i,a}\in
E(G_{i})\\}$

We compute edge labels $g(x_{i,b}y_{i,a})=g(y_{i,a})-g(x_{i,b})$ as follows:
For each edge $x_{m,b}y_{m,a}\in E(G_{m})$, we have

${\begin{split}g(x_{m,b}y_{m,a})&=g(y_{m,a})-g(x_{m,b})=[f_{m}(y_{m,a})+M-s_{m}]-\left[f_{m}(x_{m,b})+\sum^{m-1}_{k=1}s_{k}\right]\\\
&=f_{m}(y_{m,a})-f_{m}(x_{m,b}),\end{split}}$ (31)

so the edge color set $g(E(G_{m}))=[1,p_{m}-1]$. Next, for each edge
$x_{i,b}y_{i,a}\in E(G_{i})$ with $i\in[1,m-1]$, we can compute

${\begin{split}g(x_{i,b}y_{i,a})&=g(y_{i,a})-g(x_{i,b})=\left[f_{i}(y_{i,j})+M+\sum^{m-i}_{k=1}t_{k}\right]-\left[f_{i}(x_{i,j})+\sum^{i-1}_{k=1}s_{k}\right]\\\
&=f_{i}(y_{i,j})-f_{i}(x_{i,j})+\sum^{m}_{k=i}s_{k}+\sum^{m-i}_{k=1}t_{k}\end{split}}$
(32)

So, we obtain the edge color set

${\begin{split}&\quad g(E(G_{i}))=[1+M_{i},p_{i}-1+M_{i}]\end{split}}$ (33)

where $M_{i}=\sum^{m}_{k=i}s_{k}+\sum^{m-i}_{k=1}t_{k}$. Finally, we get the
whole edge color set

$g(E(G))=\bigcup^{m}_{i=1}g(E(G_{i}))=\left[1,\bigcup^{m}_{i=1}(p_{i}-1)\right]\setminus
g(E^{*})$ (34)

We claim that $g$ is a flawed set-ordered graceful labeling of the forest $G$.
∎

######  Corollary 9.

[39] Let $G$ be a disconnected graph with components
$H_{1},H_{2},\dots,H_{m}$, where each $H_{i}$ is a connected bipartite
$(p_{i},q_{i})$-graph with vertex bipartition $(X_{i},Y_{i})$ and admits a
set-ordered graceful labeling $f_{i}$ holding $\max f_{i}(X_{i})<\min
f_{i}(Y_{i})$ with $i\in[1,m]$. Then $G$ admits a flawed set-ordered graceful
labeling.

In [29], the authors have proven the following mutually equivalent labelings:

######  Theorem 10.

[29] Let $T$ be a tree on $p$ vertices, and let $(X,Y)$ be its bipartition of
vertex set $V(T)$. For all values of integers $k\geq 1$ and $d\geq 1$, the
following assertions are mutually equivalent:

$(1)$ $T$ admits a set-ordered graceful labeling $f$ with $\max f(X)<\min
f(Y)$.

$(2)$ $T$ admits a super felicitous labeling $\alpha$ with
$\max\alpha(X)<\min\alpha(Y)$.

$(3)$ $T$ admits a $(k,d)$-graceful labeling $\beta$ with
$\beta(x)<\beta(y)-k+d$ for all $x\in X$ and $y\in Y$.

$(4)$ $T$ admits a super edge-magic total labeling $\gamma$ with
$\max\gamma(X)<\min\gamma(Y)$ and a magic constant $|X|+2p+1$.

$(5)$ $T$ admits a super $(|X|+p+3,2)$-edge antimagic total labeling $\theta$
with $\max\theta(X)<\min\theta(Y)$.

$(6)$ $T$ admits an odd-elegant labeling $\eta$ with $\eta(x)+\eta(y)\leq
2p-3$ for every edge $xy\in E(T)$.

$(7)$ $T$ admits a $(k,d)$-arithmetic labeling $\psi$ with
$\max\psi(x)<\min\psi(y)-k+d\cdot|X|$ for all $x\in X$ and $y\in Y$.

$(8)$ $T$ admits a harmonious labeling $\varphi$ with
$\max\varphi(X)<\min\varphi(Y\setminus\\{y_{0}\\})$ and $\varphi(y_{0})=0$.

We have some results similarly with that in Theorem 10 about flawed graph
labelings as follows:

######  Theorem 11.

[39] Suppose that $T=\bigcup^{m}_{i=1}T_{i}$ is a forest having disjoint trees
$T_{1},T_{2},\dots,T_{m}$, and $(X,Y)$ be its vertex bipartition. For all
values of integers $k\geq 1$ and $d\geq 1$, the following assertions are
mutually equivalent:

  1. F-1.

$T$ admits a flawed set-ordered graceful labeling $f$ with $\max f(X)<\min
f(Y)$;

  2. F-2.

$T$ admits a flawed set-ordered odd-graceful labeling $f$ with $\max f(X)<\min
f(Y)$;

  3. F-3.

$T$ admits a flawed set-ordered elegant labeling $f$ with $\max f(X)<\min
f(Y)$;

  4. F-4.

$T$ admits a flawed odd-elegant labeling $\eta$ with $\eta(x)+\eta(y)\leq
2p-3$ for each edge $xy\in E(T)$.

  5. F-5.

$T$ admits a super flawed felicitous labeling $\alpha$ with
$\max\alpha(X)<\min\alpha(Y)$.

  6. F-6.

$T$ admits a super flawed edge-magic total labeling $\gamma$ with
$\max\gamma(X)<\min\gamma(Y)$ and a magic constant $|X|+2p+1$.

  7. F-7.

$T$ admits a super flawed $(|X|+p+3,2)$-edge antimagic total labeling $\theta$
with $\max\theta(X)<\min\theta(Y)$.

  8. F-8.

$T$ admits a flawed harmonious labeling $\varphi$ with
$\max\varphi(X)<\min\varphi(Y\setminus\\{y_{0}\\})$ and $\varphi(y_{0})=0$.

We present some equivalent definitions with parameters $k,d$ for flawed
$(k,d)$-labelings.

######  Theorem 12.

[39] Let $T=\bigcup^{m}_{i=1}T_{i}$ be a forest having disjoint trees
$T_{1},T_{2},\dots,T_{m}$, and $V(T)=X\cup Y$. For all values of two integers
$k\geq 1$ and $d\geq 1$, the following assertions are mutually equivalent:

  1. Flawl-1.

$T$ admits a flawed set-ordered graceful labeling $f$ with $\max f(X)<\min
f(Y)$.

  2. Flawl-2.

$T$ admits a flawed $(k,d)$-graceful labeling $\beta$ with
$\max\beta(x)<\min\beta(y)-k+d$ for all $x\in X$ and $y\in Y$.

  3. Flawl-3.

$T$ admits a flawed $(k,d)$-arithmetic labeling $\psi$ with
$\max\psi(x)<\min\psi(y)-k+d\cdot|X|$ for all $x\in X$ and $y\in Y$.

  4. Flawl-4.

$T$ admits a flawed $(k,d)$-harmonious labeling $\varphi$ with
$\max\varphi(X)<\min\varphi(Y\setminus\\{y_{0}\\})$ and $\varphi(y_{0})=0$.

######  Problem 7.

It is meaningful to find out $(k,d)$-type colorings/labelings based on those
colorings/labelings mentioned in Theorem 7, since there are over 30 flawed
graph labelings introduced in Theorem 7.

Clearly, the operation $G+E^{*}$ produces two or more connected graphs by the
different ways of joining $G_{1},G_{2},\dots,G_{m}$ together, so we get a
graph set $S_{et}(G[\ominus]\\{G_{i}\\}^{m}_{i=1})$ such that each graph
$H=G+E^{*}\in S_{et}(G[\ominus]\\{G_{i}\\}^{m}_{i=1})$ is connected and admits
a $W$-constraint labeling mentioned in Theorem 7 when each $G_{i}$ of disjoint
graphs $G_{1},G_{2},\dots,G_{m}$ is a connected bipartite
$(p_{i},q_{i})$-graph with vertex bipartition $(X_{i},Y_{i})$ and admits a
set-ordered graceful labeling $f_{i}$ holding $\max f_{i}(X_{i})<\min
f_{i}(Y_{i})$ with $i\in[1,m]$, according to Theorem 8, Corollary 9, and
Theorem 10. Show the topological structure and mathematical properties of this
graph set $S_{et}(G[\ominus]\\{G_{i}\\}^{m}_{i=1})$.

######  Remark 6.

A group of colored Hanzi-graphs $H_{1643}$, $H_{3907}$, $H_{3279}$,
$H_{3423}$, $H_{2645}$, $H_{5238}$ is shown in Fig.11, and they admit set-
ordered graceful labelings/colorings. Hanzi-graphs are natural graphs and
admit many $W$-constraint labelings/colorings mentioned in Theorem 7, Theorem
8, Corollary 9, Theorem 10, Theorem 11 and Theorem 12.

Suppose that each Hanzi-graph $H_{i}$ of disjoint Hanzi-graphs $H_{1}$,
$H_{2}$, $\dots$, $H_{n}$ is a connected bipartite $(p_{i},q_{i})$-graph with
vertex bipartition $(X_{i},Y_{i})$ and admits a group of colorings $g_{i,j}$
with $j\in[1,a_{i}]$ and $i\in[1,n]$, corresponding to a group of Topcode-
matrices $T_{code}(H_{i},g_{i,1})$, $T_{code}(H_{i},g_{i,2})$, $\dots$,
$T_{code}(H_{i},g_{i,a_{i}})$, where each Topcode-matrix
$T_{code}(H_{i},g_{i,1})$ is $3\times q_{i}$ and produces $(3q_{i})!$ number-
based strings, we put them into a _string set_ $S_{tring}(H_{i},g_{i,j})$ with
$j\in[1,a_{i}]$ and $i\in[1,n]$.

The complex analysis. We take randomly take a number-based string
$s(r_{i,j})\in S_{tring}(H_{i},g_{i,j})$ with $r_{i,j}\in[1,(3q_{i})!]$, and
make a large scale of number-based string as follows

$S(\\{H_{i}\\}^{n}_{i=1},\\{r_{i,j_{t}}\\}^{n}_{i=1})=s(r_{1,j_{1}})s(r_{2,j_{2}})\cdots
s(r_{n,j_{n}})$ (35)

for $j_{t}\in[1,a_{t}]$, $r_{i,j_{t}}\in[1,(3q_{t})!]$ and $t\in[1,n]$. If we
do not think about the permutations on the strings
$s(r_{1,j_{1}}),s(r_{2,j_{2}}),\dots,s(r_{n,j_{n}})$ and Hanzi-graphs $H_{1}$,
$H_{2}$, $\dots$, $H_{n}$, we get
$\prod^{n}_{i=1}(a_{i})!\prod^{n}_{i=1}(q_{i})!$ different number-based
strings like $S(\\{H_{i}\\}^{n}_{i=1},\\{r_{i,j_{t}}\\}^{n}_{i=1})$ shown in
Eq.(35). Otherwise, we have at least

$n_{string}(\\{H_{i}\\}^{n}_{i=1})=(n!)^{2}\prod^{n}_{i=1}(a_{i})!\prod^{n}_{i=1}(q_{i})!$
(36)

different number-based strings
$S(\\{H_{i}\\}^{n}_{i=1},\\{r_{i,j_{t}}\\}^{n}_{i=1})$ define in Eq.(35).

A Chinese sentence
$H_{1643}$$H_{3907}$$H_{3279}$$H_{3423}$$H_{2645}$$H_{5238}$ consists of
disjoint connected Hanzi-graphs $H_{1}$, $H_{2}$, $\dots$, $H_{13}$ with the
edge numbers $q_{1}=$2, $q_{2}=$2, $q_{3}=$6, $q_{4}=$18, $q_{5}=$4,
$q_{6}=$7, $q_{7}=$6, $q_{8}=$4, $q_{9}=$7, $q_{10}=$1, $q_{11}=$4,
$q_{12}=$1, $q_{13}=$7\. This group of connected Hanzi-graphs provide us

$n_{string}(\\{H_{i}\\}^{13}_{i=1})=(13!)^{2}\prod^{13}_{i=1}(a_{i})!\prod^{13}_{i=1}(q_{i})!$

different number-based strings, where each $a_{i}\geq 30$ by Theorem 7,
Theorem 8, Corollary 9, Theorem 10, Theorem 11 and Theorem 12.

The above work illustrates the fact that Chinese speakers can generate their
own passwords made by long byte number-based strings through speaking and
writing their own easy-to-remember Chinese sentences, in response to
cryptographic security in the age of supercomputers and quantum computers.
$\parallel$

Figure 11: A sentence
$H_{1643}$$H_{3907}$$H_{3279}$$H_{3423}$$H_{2645}$$H_{5238}$ in Chinese [14].

##  3 Graphs admitting parameterized total colorings

###  3.1 Graphs admitting $W$-constraint $(k,d)$-total colorings

######  Example 3.

It is not hard to find a graceful $(k,d)$-total coloring of a _complete
bipartite graph_ $K_{m,n}$. Let $V(K_{m,n})=X\cup Y$ with
$X=\\{x_{j}:j\in[1,m]\\}$ and $Y=\\{y_{i}:i\in[1,n]\\}$ be the vertex sets of
$K_{m,n}$, and $E(K_{m,n})=\\{x_{j}y_{i}:j\in[1,m],i\in[1,n]\\}$ be the edge
set of $K_{m,n}$.

We define a $(k,d)$-total coloring $f$ for $K_{m,n}$ in the following way:

(i) $f(x_{j})=(j-1)d$ with $j\in[1,m]$;

(ii) $f(y_{i})=k+(m-1)d+m(i-1)d$ with $i\in[1,n]$; and

(iii) $f(x_{j}y_{i})=f(y_{i})-f(x_{j})=k+(mi-j)d$ with $j\in[1,m]$.
Clearly, the edge color set $f(E(K_{m,n}))=S_{mn-1,k,0,d}$, so we claim that
$f$ is a graceful $(k,d)$-total coloring of $K_{m,n}$.

See examples shown in Fig.12, where $K_{2,3}=G_{1}$, $K_{2,4}=G_{4}$,
$K_{2,2}=G_{5}$, and $K_{2,1}=G_{6}$. $\square$

Figure 12: Two $W$-constraint colored $\\{T_{i}\\}^{m}_{1}$-books: (d)
$G=(G_{1}\odot_{2}G_{2})\odot_{2}G_{3}$; (h)
$H=[(G_{1}\odot_{2}G_{4})\odot_{2}G_{5}]\odot_{2}G_{6}$.

######  Example 4.

The regular graph-books. A bipartite and connected $(p,q)$-graph $G$ admits a
graceful $(k,d)$-total coloring $f$ such that the $X$-vertex color set
$f(X)\subseteq S_{m,k,0,d}$, the $Y$-vertex color set $f(Y)\subseteq
S_{q-1,k,0,d}$ and the edge color set $f(E(G))=S_{q-1,k,0,d}$, where $(X,Y)$
is the bipartition of $V(G)$, $X=\\{x_{i}:i\in[1,s]\\}$ and
$Y=\\{y_{j}:j\in[1,t]\\}$ holding $s+t=p$.

Each copy $G_{j}$ of $G$ has its own bipartition $(X_{j},Y_{j})$, such that
$X_{j}=\\{x_{j,i}:i\in[1,s]\\}$ and $Y_{j}=\\{y_{j,i}:i\in[1,t]\\}$ with
$j\in[1,n]$. We define a total coloring $f_{j}$ of $G_{j}$ as:

(1) $f_{j}(x_{j,i})=f(x_{i})$ for $x_{i}\in X$ and $x_{j,i}\in X_{j}$ with
$i\in[1,s]$;

(2) $f_{j}(y_{j,i})=f(y_{i})+(j-1)qd$ for $y_{i}\in Y$ and $y_{j,i}\in Y_{j}$
with $i\in[1,t]$;

(3) The edge $x_{r}y_{i}\in E(G)$ and the edge $x_{j,r}y_{j,i}\in E(G_{j})$
hold

$f_{j}(x_{j,r}y_{j,i})=f_{j}(y_{j,i})-f_{j}(x_{j,i})=f(y_{i})+(j-1)qd-f(x_{r})$

Obviously, we have edge colors

$f_{j}(x_{j,r}y_{j,i})\in\\{k+(j-1)qd,k+[(j-1)q+1]d,\dots,k+(jq-1)d\\},~{}j\in[1,n]$

Then, we vertex-coincide these vertices $x_{i},x_{1,i},x_{2,i},\dots,x_{n,i}$
into one vertex

$x_{i}=x_{1,i}\odot x_{2,i}\odot\cdots\odot
x_{n,i}=x_{1}\odot\left([\odot]^{n}_{j=1}x_{j,i}\right)\in X$

The resulting graph is called _regular graph-book_ , denoted as

$R_{book}=[\odot_{X}]^{n}_{j=1}G_{j}$ (37)

the vertex set $X$ of $G$ is called _spine_ , and each colored graph $G_{i}$
is called _book-page_.

Thereby, this regular graph-book admits a graceful $(k,d)$-total coloring $F$
defined by the compound of the colorings $f_{1},f_{2},\dots,f_{n}$. See a
regular graph-book $G$ shown in Fig.12 (d), where $G$ admits a graceful
$(k,d)$-total coloring. $\square$

######  Example 5.

The general graph-books. Suppose that each bipartite and connected
$(p_{j},q_{j})$-graph $H_{j}$ for $j\in[1,n]$ has its own vertex bipartition
$(X_{j},Y_{j})$ as

$X_{j}=\\{u_{j,i}:i\in[1,s_{j}]\\},~{}Y_{j}=\\{v_{j,r}:r\in[1,t_{j}]\\},~{}p_{j}=s_{j}+t_{j}$

and admits a $W$-constraint $(k,d)$-total coloring $g_{j}$ defined by

${\begin{split}&g_{j}:X_{j}\rightarrow
S_{m_{j},0,0,d}=\\{0,d,\dots,m_{j}d\\}\\\ &g_{j}:Y_{j}\cup E(G_{j})\rightarrow
S_{n_{j},k,0,d}=\\{k,k+d,\dots,k+n_{j}d\\}\end{split}}$ (38)

and holding the $W$-constraint $g_{j}(u_{j,i}v_{j,r})=W\langle
g_{j}(u_{j,i}),g_{j}(v_{j,r})\rangle$ for each edge $u_{j,i}v_{j,r}\in
E(H_{j})$.

For constructing general graph-books, we set $s=s_{j}$ for $j\in[1,n]$ and
$g_{a}(u_{a,i})=g_{b}(u_{b,i})$ for $i\in[1,s]$ and $a,b\in[1,n]$. We vertex-
coincide the vertices $u_{1,i},u_{2,i},\dots,u_{n,i}$ into one vertex

$w_{i}=u_{1,i}\odot u_{2,i}\odot\cdots\odot u_{n,i}=[\odot]^{n}_{j=1}u_{j,i}$
(39)

with $i\in[1,s]$, the resultant graph is just a _general graph-book_ denoted
as

$G_{book}=H_{1}\odot_{s}H_{2}\odot_{s}\cdots\odot_{s}H_{n}=[\odot_{s}]^{n}_{j=1}H_{j}$
(40)

Now, we define a $(k,d)$-total coloring $F$ for the general graph-book
$G_{book}$ by the following algorithm:

Step 1. $F(w_{i})=g_{1}(u_{1,i})$ for $i\in[1,s]$, where $u_{1,i}\in
X_{1}\subset V(H_{1})$ and $w_{i}\in V(G_{book})$.

Step 2. Each vertex $v_{1,r}\in Y_{1}\subset V(H_{1})$ is colored as
$F(v_{1,r})=g_{1}(v_{1,r})$ for $r\in[1,t_{1}]$, and each edge
$u_{1,i}v_{1,r}\in E(H_{1})$ is colored by
$F(u_{1,i}v_{1,r})=g_{1}(u_{1,i}v_{1,r})$.

Step 3. Each vertex $v_{j,r}\in Y_{j}\subset V(H_{j})$ with $j\in[2,n]$ is
colored as

$F(v_{j,r})=g_{j}(v_{j,r})+\sum^{j-1}_{i=1}q_{i}\cdot d,~{}r\in[1,t_{j}]$ (41)

By Eq.(39), we have each edge $w_{i}v_{j,r}=u_{j,i}v_{j,r}\in E(H_{j})\subset
E(G_{book})$, so the edge color is

$F(w_{i}v_{j,r})=F(u_{j,i}v_{j,r})=g_{j}(u_{j,i}v_{j,r})+\sum^{j-1}_{i=1}q_{i}\cdot
d$ (42)

Step 3. The coloring $F$ holds the $W$-constraint $F(xy)=W\langle
F(x),F(y)\rangle$ for $xy\in E(G_{book})$.

Step 4. Return the $W$-constraint $(k,d)$-total coloring $F$ of the general
graph-book $G_{book}$.

See a general graph-book $H$ shown in Fig.12 (h). $\square$

######  Definition 15.

∗ We write a general graph-book $G_{book}=B\langle
S_{X},W,\\{H_{j}\\}^{M}_{j=1}\rangle$ for the convenience of further study,
such that

(i) $S_{X}$ is the _spine_ ;

(ii) each _book-page_ $H_{j}$ is a bipartite and connected graph with its
vertex bipartition $V(H_{j})=(S_{X},Y_{j})$ for $j\in[1,M]$;

(iii) edge number $q_{j}=|E(H_{j})|$ od each book-page $H_{j}$ is a _book-page
weight_ , and the sum $\sum^{M}_{j=1}q_{j}$ is the _volume_ of the general
graph-book;

(iv) two book-pages $H_{i}$ and $H_{j}$ hold $V(H_{i})\cap V(H_{j})=S_{X}$ for
$i\neq j$. $\square$

######  Remark 7.

We say that the general graph-book $B\langle
S_{X},W,\\{H_{j}\\}^{M}_{j=1}\rangle$ defined in Definition 15 to be
_Fibonacci graph-book_ if the _book-page weight sequence_
$\\{q_{j}\\}^{M}_{j=1}$ is the _Fibonacci sequence_. And moreover, a general
graph-book $B\langle S_{X},W,\\{H_{j}\\}^{M}_{j=1}\rangle$ is called _$Q$
-graph-book_ if $\\{q_{j}\\}^{M}_{j=1}$ is a _$Q$ -sequence_, in general.

In the topological authentication of view, a general graph-book $B\langle
S_{X},W,\\{H_{j}\\}^{M}_{j=1}\rangle$ is just a topological authentication,
such that each book-page $H_{j}$ is just a _private-key_. $\parallel$

Graph-book lattices. In a _base_ $\textbf{{T}}=(T_{1},T_{2},\dots,T_{n})$,
suppose that each bipartite and connected $(p_{j},q_{j})$-graph
$T_{j}\in\textbf{{T}}$ for $j\in[1,n]$ admits a $W$-constraint total coloring
(or $(k,d)$-total coloring) $g_{j}$ defined in Eq.(38). The vertex bipartition
$(X_{i},Y_{i})=V(T_{i})$ of each graph $T_{i}$ holds $X_{i}=S_{X}$ true for
$i\in[1,n]$ according to Definition 15. Let $H_{1},H_{2},\dots,H_{M}$ in a
general graph-book $B\langle S_{X},W,\\{H_{j}\\}^{M}_{j=1}\rangle$ defined in
Definition 15 be a permutation of graphs $a_{1}T_{1}$, $a_{2}T_{2}$, $\dots$,
$a_{n}T_{n}$ with $M=\sum^{n}_{k=1}a_{k}\geq 1$, so we rewrite this general
graph-book as

$B\langle S_{X},W,\\{H_{j}\\}^{M}_{j=1}\rangle=B\langle
S_{X},W,[\odot_{X}]^{n}_{k=1}a_{k}T_{k}\rangle$

Notice that there are $M!$ permutations, in total. We get a general
uniform-$W$-constraint graph-book lattice

$\textbf{{L}}(Z^{0}[\odot_{X}]\textbf{{T}},W)=\big{\\{}B\langle
S_{X},W,[\odot_{X}]^{n}_{k=1}a_{k}T_{k}\rangle:~{}a_{k}\in
Z^{0},T_{k}\in\textbf{{T}}\big{\\}}$ (43)

under the base $\textbf{{T}}=(T_{1},T_{2},\dots,T_{n})$.

If each bipartite and connected $(p_{j},q_{j})$-graph $T_{j}$ of the base
$\textbf{{T}}=(T_{1},T_{2},\dots,T_{n})$ admits a $W_{t}$-constraint total
coloring (or $(k,d)$-total coloring) $f_{j,t}$ for $t\in[1,A]$, then we get a
group of general uniform-$W_{t}$-constraint graph-book lattices
$\textbf{{L}}(Z^{0}[\odot_{X}]\textbf{{T}},W_{t})$ for each $t\in[1,A]$.

######  Problem 8.

Does there exist a general graph-book lattice
$\textbf{{L}}(Z^{0}[\odot_{X}]\textbf{{T}},\\{W_{t}\\}^{A}_{i=1})$ as each
bipartite and connected $(p_{j},q_{j})$-graph $T_{j}\in\textbf{{T}}$ admitting
a $W_{j}$-constraint total coloring (or $(k,d)$-total coloring) $g_{j}$ for
$j\in[1,n]$, and $W_{j}\neq W_{i}$ for some $j\neq i$ and $1\leq j,i\leq A$?

###  3.2 Graphs admitting graceful $(k,d)$-total colorings

######  Theorem 13.

[24] Suppose that a bipartite and connected $(p,q)$-graph $G$ admits a
graceful $(k,d)$-total coloring defined in Definition 7, adding randomly
leaves to $G$ produces a bipartite and connected
$(p\,^{\prime},q\,^{\prime})$-graph admitting a graceful $(k,d)$-total
coloring.

###### Proof.

Let $G$ be a bipartite and connected $(p,q)$-graph with its vertex set
$V(G)=X\cup Y$ with $X\cap Y=\emptyset$, and $X=\\{x_{i}:i\in[1,s]\\}$ and
$Y=\\{y_{j}:j\in[1,t]\\}$ holding $s+t=p$, as well as the edge set
$E(G)=\\{e_{i}:i\in[1,q]\\}$.

Suppose that $G$ admits a graceful $(k,d)$-total coloring $f$ defined in
Definition 7, so we have

$f:X\rightarrow S_{m,0,0,d},~{}f:Y\cup E(G)\rightarrow S_{q-1,k,0,d},~{}k\geq
1$

and moreover $0=f(x_{1})\leq f(x_{i})\leq f(x_{i+1})$ for $i\in[1,s-1]$ and

$f(y_{j})\leq f(y_{j+1})\leq f(y_{t})=k+(q-1)d,~{}j\in[1,t-1]$

as well as the edge color set $f(E(G))=S_{q-1,k,0,d}$.

Adding randomly leaves to the vertices $x_{i}$ and $y_{j}$ of $G$ produces
leaf sets

$L_{eaf}(x_{i})=\\{x_{i,1},x_{i,2},\dots,x_{i,a_{i}}\\},~{}i\in[1,s]\textrm{
and }L_{eaf}(y_{j})=\\{y_{j,1},y_{j,2},\dots,y_{j,b_{j}}\\},~{}j\in[1,t]$

Here, it is allowed that $L_{eaf}(x_{i})=\emptyset$ (or
$L_{eaf}(y_{j})=\emptyset$) if some vertex $x_{i}$ (or some vertex $y_{j}$) is
not joined with any new added vertex. So, the leaf-added graph $G+L_{eaf}(w)$
has its own vertex set

$V(G+L_{eaf}(w))=X\,^{\prime}\cup
Y\,^{\prime},~{}X\,^{\prime}=X\bigcup\left(\bigcup^{t}_{j=1}L_{eaf}(y_{j})\right),~{}Y\,^{\prime}=Y\bigcup\left(\bigcup^{s}_{i=1}L_{eaf}(x_{i})\right)$

and the new leaf set

$L_{eaf}(w)=\left(\bigcup^{s}_{i=1}L_{eaf}(x_{i})\right)\bigcup\left(\bigcup^{t}_{j=1}L_{eaf}(y_{j})\right)$

Let $A=\sum^{s}_{k=1}a_{k}$ and $B=\sum^{t}_{k=1}b_{k}$. Thereby,

${\begin{split}|V(G+L_{eaf}(w))|&=|V(G)|+|L_{eaf}(w)|=|V(G)|+A+B\\\
|E(G+L_{eaf}(w))|&=|E(G)|+|L_{eaf}(w)|=|E(G)|+A+B\end{split}}$

We define a total coloring $g$ for the connected graph $G+L_{eaf}(w)$ in the
following steps:

Step 1. Color the edges $x_{i}x_{i,r}$ made by the leaves of $L_{eaf}(x_{i})$
joined with the vertices $x_{i}$ of $X$ as:

$g(x_{i}x_{i,r})=k+d\cdot\left(r-1+\sum^{i-1}_{k=1}a_{k}\right)$

for $r\in[1,a_{i}]$ and $i\in[1,s]$, here, $\sum^{0}_{k=1}a_{k}=0$.

Step 2. Color the edges $y_{j}y_{j,r}$ made by the leaves of $L_{eaf}(y_{j})$
joined with the vertices $y_{j}$ of $Y$ as:

$g(y_{t}y_{t,r})=k+d\cdot(A+r-1),~{}r\in[1,b_{t}]$

and

$g(y_{t-j}y_{t-j,r})=k+d\cdot\left(A+r-1+\sum^{j}_{k=1}b_{t-k+1}\right),~{}r\in[1,b_{t-j}],~{}j\in[1,t-1]$

Step 3. Color the vertices $x_{i}\in X\,^{\prime}$ by $g(x_{i})=f(x_{i})$ with
$i\in[1,s]$, and set $g(x_{i,r})=f(x_{i})+g(x_{i}x_{i,r})$ for each leaf
$x_{i,r}\in L_{eaf}(x_{i})\subset Y\,^{\prime}$.

Step 4. Color the vertices $y_{j}\in Y\,^{\prime}$ by
$g(y_{j})=f(y_{j})+(A+B)d$ with $j\in[1,t]$, and each leaf $y_{j,r}\in
L_{eaf}(y_{j})\subset Y\,^{\prime}$ is colored with

$g(y_{j,r})=g(y_{j})-g(y_{j}y_{j,r})=f(y_{j})+(A+B)d-\left[k+d\cdot\left(A+r-1+\sum^{t-j}_{k=1}b_{t-k+1}\right)\right]$

for $j\in[1,t]$, where $\sum^{0}_{k=1}b_{t-k+1}=0$.

Step 5. Color each edge $x_{i}y_{j}\in E(G)\subset E(G+L_{eaf}(w))$ by

$g(x_{i}y_{j})=g(y_{j})-g(x_{i})=f(y_{j})+(A+B)d-f(x_{i})=f(x_{i}y_{j})+(A+B)d$

with $x_{i}y_{j}\in E(G+L_{eaf}(w))$. Thereby, we have the edge color set

${\begin{split}g(E(G+L_{eaf}(w)))=&\\{k,k+d,\dots,k+(A+B-1)d\\}\cup\\\
&\cup\\{f(x_{i}y_{j})+(A+B)d:x_{i}y_{j}\in E(G+L_{eaf}(w))\\}\\\
=&\\{k,k+d,\dots,k+(A+B-1)d,k+(A+B)d,\dots,k+(q+A+B-1)d\\}\\\
=&S_{q+A+B-1,k,d}\end{split}}$

and the smallest vertex color is $\min g(V(G+L_{eaf}(w)))=g(x_{1})=0$, and the
largest vertex color is

$\max g(V(G+L_{eaf}(w)))=g(y_{t})=k+(q-1+A+B)d=k+(|E(G+L_{eaf}(w))|-1)d$

as well as the vertex color sets $g(X\,^{\prime})\subset S_{n,0,d}$ and
$g(Y\,^{\prime})\subset S_{A+B+q,k,d}$. Finally, we claim that $g$ is a
graceful $(k,d)$-total coloring of the leaf-added graph $G+L_{eaf}(w)$.

The proof of the theorem is complete. ∎

Figure 13: The processes for adding leaves: (a) A graph $G$ admitting a
graceful $(k,d)$-total coloring; (b) adding randomly leaves to $G$; (c)
coloring new added edges by the Leaf-adding $x$SL$y$LS-graceful algorithm; (d)
coloring added leaves; (e) coloring new added edges by the Leaf-adding
$x$LS$y$SL-graceful algorithm and coloring added leaves. Figure 14: Four Leaf-
adding $W$-graceful algorithms with $W=$$x$SL$y$SL, $x$LS$y$LS, $y$SL$x$SL and
$y$LS$x$LS based on $G_{2}$ shown in Fig.13. Figure 15: An example for
understanding the Leaf-adding $x$SL$y$LS-graceful algorithm by the positive
order of coloring the new added edges, where two vertices are colored with
$3d$, two vertices are colored with $9d$, two vertices colored with $k+20d$,
and two vertices are colored with $k+22d$.

######  Remark 8.

We call the process of showing the graceful $(k,d)$-total coloring $g$ of the
leaf-added graph $G+L_{eaf}(w)$ obtained by “adding-leaf operation” in the
proof of Theorem 13 as _Leaf-adding $x$SL$y$LS-graceful algorithm_ hereafter,
since we have colored new added edges from the leaves of $x_{1}$ to the leaves
of $x_{s}$ (from small to large, $x$SL) and then from the leaves of $y_{t}$ to
the leaves of $y_{1}$ (from large to small, $y$LS). The coloring technique in
the proof of Theorem 13 is as the same as that in [50]. See examples shown in
Fig.13 and Fig.15 for illustrating the Leaf-adding $x$SL$y$LS-graceful
algorithm, where $G_{3}$ is obtained by adding randomly leaves to $G$.

Conversely, we have a Leaf-adding $x$LS$y$SL-graceful algorithm when we color
new added edges from the leaves of $x_{s}$ to the leaves of $x_{1}$ and then
from the leaves of $y_{1}$ to the leaves of $y_{t}$ in the proof of Theorem
13. See an example shown in Fig.16 for knowing the Leaf-adding $x$LS$y$SL-
graceful algorithm. $\parallel$

Figure 16: An example for illustrating the Leaf-adding $x$LS$y$SL-graceful
algorithm by the reverse order of coloring the new added edges, where two
vertices are colored with $9d$, three vertices are colored with $10d$, two
vertices are colored with $17d$, two vertices are colored with $18d$, two
vertices are colored with $k+10d$, three vertices are colored with $k+13d$,
and five vertices are colored with $k+14d$.

######  Theorem 14.

∗ Any tree $T$ with diameter $D(T)\geq 3$ admits at least $2^{m}$ different
graceful $(k,d)$-total colorings for
$m+1=\left\lceil\frac{D(T)}{2}\right\rceil$.

###### Proof.

Let $D(T_{1})$ be the diameter of a tree $T_{1}$ with $D(T_{1})\geq 3$, and
let $L_{eaf}(T_{1})$ be the set of leaves of $T_{1}$. We get another tree
$T_{2}=T_{1}-L_{eaf}(T_{1})$ after removing the leaves of $L_{eaf}(T_{1})$. Go
on in this way, we have trees $T_{i+1}=T_{i}-L_{eaf}(T_{i})$ with $i\in[1,m]$,
and $T_{m+1}$ is just a star with vertex set
$V(T_{m+1})=\\{x\\}\cup\\{x_{j}:j\in[1,n]\\}$ and edge set
$E(T_{m+1})=\\{xx_{j}:j\in[1,n]\\}$.

We define a graceful $(k,d)$-total coloring $f_{m+1}$ for the star $T_{m+1}$
as:

(i) $f_{m+1}(x)=0$, $f_{m+1}(x_{j})=k+(j-1)d$ and

(ii) $f_{m+1}(xx_{j})=f_{m+1}(x_{j})-f_{m+1}(x)$ with $j\in[1,n]$.
Thereby, each tree $T_{i}$ is obtained by adding the leaves of
$L_{eaf}(T_{i})$ to the tree $T_{i+1}$, that is,
$T_{i}=T_{i+1}+L_{eaf}(T_{i})$ is a _leaf-added tree_. Moreover, $T_{i}$
admits a graceful $(k,d)$-total coloring $f_{i}$ obtained from the graceful
$(k,d)$-total coloring $f_{i+1}$ of $T_{i+1}$ according to one of the Leaf-
adding $x$SL$y$LS-graceful algorithm and the Leaf-adding $x$LS$y$SL-graceful
algorithm. By the induction, the tree $T_{1}$ admits a graceful $(k,d)$-total
coloring $f_{1}$ obtained from the graceful $(k,d)$-total coloring $f_{2}$ of
$T_{2}$.

Notice that there are two ways from choosing one of the Leaf-adding
$x$SL$y$LS-graceful algorithm and the Leaf-adding $x$LS$y$SL-graceful
algorithm, since each tree has at least two leaves, that is,
$|L_{eaf}(T_{i})|\geq 2$ with $i\in[1,m]$.

Then the tree $T_{1}$ admits at least $2^{m}$ different graceful $(k,d)$-total
colorings as desired. ∎

###  3.3 Graphs admitting harmonious $(k,d)$-total colorings

######  Theorem 15.

∗ Each tree admits a harmonious $(k,d)$-total coloring.

###### Proof.

Let $L_{eaf}(T_{i})$ be the leaf set of a tree $T_{i}$, and let
$T_{i+1}=T_{i}-L_{eaf}(T_{i})$ with $i\in[1,m]$. Suppose that
$T_{m+1}=T_{m}-L_{eaf}(T_{m})$ is a star with vertex set
$V(T_{m+1})=\\{u_{0}\\}\cup L_{eaf}(T_{m+1})$ and the edge set
$E(T_{m+1})=\\{u_{0}v_{j}:j\in[1,n]\\}$, where
$L_{eaf}(T_{m+1})=\\{v_{1},v_{2},\dots,v_{n}\\}$ is the leaf set of the star
$T_{m+1}$.

Initialization. We define a harmonious $(k,d)$-total coloring $f_{m+1}$ for
the star $T_{m+1}$ as follows: $f_{m+1}(u_{0})=0$, $f_{m+1}(v_{j})=k+jd$ with
$k\geq 0$ and $d\geq 1$, and color each edge $u_{0}u_{j}$ with

$f_{m+1}(u_{0}u_{j})=f_{m+1}(v_{j})+f_{m+1}(u_{0})=k+jd,~{}j\in[1,n]$

So, $f_{m+1}$ is a harmonious $(k,d)$-total coloring of $T_{m+1}$, since

$f_{m+1}(u_{0}u_{j})=f_{m+1}(v_{j})+f_{m+1}(u_{0})=k+jd~{}(\bmod^{*}~{}q_{m}d),~{}q_{m}=|E(T_{m+1})|=n$

where the operation “$\bmod^{*}q_{m}d$” means
$f_{m+1}(u_{0}u_{j})-k~{}(\bmod~{}q_{m}d)$.

Iteration. Suppose that a tree $T_{i+1}=T_{i}-L_{eaf}(T_{i})$ admits a
harmonious $(k,d)$-total coloring $f_{i+1}$, and $V(T_{i+1})=X_{i+1}\cup
Y_{i+1}$ with $X_{i+1}=\\{u_{i+1,r}:r\in[1,c_{i+1}]\\}$ and
$Y_{i+1}=\\{v_{i+1,j}:j\in[1,b_{i+1}]\\}$ for some $i\in[1,m]$. Thereby, the
$X$-vertex set

$f_{i+1}(X_{i+1})\subseteq S_{l,0,0,d}=\\{0,d,\dots,ld\\}$

and the $Y$-vertex set

$f_{i+1}(Y_{i+1})\subseteq
S_{q_{i+1}-1,k,0,d}=\\{k,k+d,\dots,k+(q_{i+1}-1)d\\}$

Since the edge color set $f_{i+1}(E(T_{i+1}))=S_{q_{i+1}-1,k,0,d}$, so we have
$E(T_{i+1})=E_{\textrm{non}}\cup E_{\textrm{mod}}$ such that the edge color
set

$f_{i+1}(E(T_{i+1}))=f_{i+1}(E_{non})\cup f_{i+1}(E_{\textrm{mod}})$

where $f_{i+1}(uv)~{}(\bmod^{*}~{}q_{i+1}d)=f_{i+1}(u)+f_{i+1}(v)$ for each
edge $uv\in E_{non}$, and

$f_{i+1}(xy)~{}(\bmod^{*}~{}q_{i+1}d)=f_{i+1}(x)+f_{i+1}(y)-k~{}(\bmod~{}q_{i+1}d),~{}xy\in
E_{\textrm{mod}}$

Clearly, two edge color sets
$f_{i+1}(E_{\textrm{non}})=\\{k,k+d,\dots,k+\alpha d\\}$ and

$f_{i+1}(E_{\textrm{mod}})=\\{k+(\alpha+1)d,k+(\alpha+2)d,\dots,k+(q_{i+1}-1)d\\},~{}\alpha\geq
0$

Without loss of generality, we have

$0=f_{i+1}(u_{i,1})\leq f_{i+1}(u_{i+1,r})\leq
f_{i+1}(u_{i,r+1}),~{}r\in[1,c_{i+1}-1]$

and

$k\leq f_{i+1}(v_{i+1,j})\leq f_{i+1}(v_{i,j+1})\leq
f_{i+1}(v_{i,b_{i+1}})=k+(q_{i+1}-1)d,~{}j\in[1,b_{i+1}-1]$

Adding the leaves of the leaf set $L_{eaf}(T_{i})$ to the tree $T_{i+1}$
produces the tree $T_{i}$, and each vertex $u_{i+1,r}$ of $X_{i+1}$ has its
own leaf set

$L_{eaf}(u_{i+1,r})=\\{u\,^{\prime}_{i+1,r,j}:j\in[1,c_{i+1,r}]\\}\textrm{
with }|L_{eaf}(u_{i+1,r})|=c_{i+1,r},~{}r\in[1,c_{i+1}]$

and each vertex $v_{i+1,s}$ of $Y_{i+1}$ has its own leaf set

$L_{eaf}(v_{i+1,s})=\\{v\,^{\prime}_{i+1,s,j}:j\in[1,b_{i+1,s}]\\}\textrm{
with }|L_{eaf}(v_{i+1,s})|=b_{i+1,s},~{}s\in[1,b_{i+1}]$

Thereby, we have the leaf set

$L_{eaf}(T_{i})=\left(\bigcup^{c_{i+1}}_{r=1}L_{eaf}(u_{i,r})\right)\bigcup\left(\bigcup^{b_{i+1}}_{s=1}L_{eaf}(v_{i+1,s})\right)$

and $A=|L_{eaf}(T_{i})|=M_{X}+M_{Y}$, where
$M_{X}=\sum^{c_{i+1}}_{r=1}|L_{eaf}(u_{i,r})|$ and
$M_{Y}=\sum^{b_{i+1}}_{s=1}|L_{eaf}(v_{i,s})|$.

We, now, define a total coloring $f_{i}$ for $T_{i}$ with $i\in[1,m]$ in the
following steps:

Step 1. $f_{i}(v_{i+1,s})=d\cdot A+f_{i+1}(v_{i+1,s})$ for $v_{i+1,s}\in
Y_{i+1}\subset Y_{i}\subset V(T_{i})$;

Step 2. $f_{i}(u_{i+1,r})=f_{i+1}(u_{i+1,r})$ for $u_{i+1,r}\in X_{i+1}\subset
Y_{i}\subset V(T_{i})$;

Step 3. $f_{i}(xy)=f_{i+1}(xy)$ for each edge $xy\in E_{\textrm{mod}}\subset
E(T_{i+1})\subset E(T_{i})$;

Step 4. $f_{i}(uv)=f_{i}(u)+f_{i}(v)=d\cdot A+f_{i+1}(u)+f_{i+1}(v)$ for each
edge $uv\in E_{\textrm{non}}\subset E(T_{i+1})\subset E(T_{i})$ holding $u\in
Y_{i+1}$ and $v\in X_{i+1}$;

Step 5. For the new added leaves to $T_{i+1}$, we, first, color new edges as:

$f_{i}(v_{i+1,b_{i+1}}v\,^{\prime}_{i+1,b_{i+1},j})=k+(\alpha+j)d,~{}v\,^{\prime}_{i+1,b_{i+1},j}\in
L_{eaf}(v_{i+1,b_{i+1}})$

in general,

$f_{i}(v_{i+1,s}v\,^{\prime}_{i+1,s,j})=jd+k+\alpha
d+d\sum^{b_{i+1}-s}_{k=1}b_{i+1,b_{i+1}-k+1}$ (44)

for $v\,^{\prime}_{i+1,s,j}\in L_{eaf}(v_{i+1,s})$ with $s\in[1,b_{i+1}-1]$,
where $\sum^{0}_{k=1}b_{i+1,b_{i+1}-k+1}=0$; and moreover

$f_{i}(v_{i+1,1}v\,^{\prime}_{i+1,1,b_{i+1,1}})=d\cdot b_{i+1,1}+k+\alpha
d+d\sum^{b_{i+1}-1}_{k=1}b_{i+1,b_{i+1}-k+1}=k+(\alpha+M_{Y})d.$

We color the leaves
$v\,^{\prime}_{i+1,s,j}\in\bigcup^{b_{i+1}}_{s=1}L_{eaf}(v_{i+1,s})$ by

$f_{i}(v\,^{\prime}_{i+1,s,j})=d\cdot(A+q_{i+1})+f_{i}(v_{i+1,s}v\,^{\prime}_{i+1,s,j})-f_{i}(v_{i+1,s})$

so $f_{i}(v\,^{\prime}_{i+1,s,j})\in S_{q_{i}-1,k,0,d}$, and
$f_{i}(v_{i+1,s}v\,^{\prime}_{i+1,s,j})\in S_{q_{i}-1,k,0,d}$.

Step 6. Let $N_{Y}=k+(\alpha+M_{Y})d$. We, first, color edges
$u_{i+1,c_{i+1}}u\,^{\prime}_{i+1,c_{i+1},j}$ by

$f_{i}(u_{i+1,c_{i+1}}u\,^{\prime}_{i+1,c_{i+1},j})=jd+N_{Y}$

with $j\in[1,c_{i+1,c_{i+1}}]$ for $u\,^{\prime}_{i+1,c_{i+1},j}\in
L_{eaf}(u_{i+1,c_{i+1}})$. In general, we color edges
$u_{i+1,r}u\,^{\prime}_{i+1,r,j}$ by

$f_{i}(u_{i+1,r}u\,^{\prime}_{i+1,r,j})=jd+N_{Y}+d\sum^{c_{i+1}-r}_{k=1}c_{i+1,c_{i+1}-k+1}$
(45)

with $j\in[1,c_{i+1,r}]$ for $u\,^{\prime}_{i+1,r,j}\in L_{eaf}(u_{i+1,r})$
and $r\in[1,c_{i+1}]$. The last edge $u_{i+1,1}u\,^{\prime}_{i+1,1,c_{i+1,1}}$
is colored with

$f_{i}(u_{i+1,1}u\,^{\prime}_{i+1,1,c_{i+1,1}})=c_{i+1,1}d+N_{Y}+d\sum^{c_{i+1}-1}_{k=1}c_{i+1,c_{i+1}-k+1}=N_{Y}+N_{X}$

where $N_{X}=\sum^{c_{i+1}}_{k=1}c_{i+1,c_{i+1}-k+1}$.

Now, we color the leaves of the leaf set
$\bigcup^{c_{i+1}}_{r=1}L_{eaf}(u_{i,r})$ by

$f_{i}(u\,^{\prime}_{i+1,r,j})=f_{i}(u_{i+1,r}u\,^{\prime}_{i+1,r,j})-f_{i}(u_{i+1,r}),~{}j\in[1,c_{i+1,r}]$

for $u\,^{\prime}_{i+1,r,j}\in L_{eaf}(u_{i+1,r})$ and $r\in[1,c_{i+1}]$.
Clearly,

$f_{i}(u\,^{\prime}_{i+1,r,j})\in S_{m,0,0,d},\quad
f_{i}(u_{i+1,r}u\,^{\prime}_{i+1,r,j})\in S_{q_{i}-1,k,0,d}$

Thereby, there are the vertex color set $f_{i}(V(T_{i}))\subseteq
S_{m,0,0,d}\cup S_{q_{i}-1,k,0,d}$ and the edge color set
$f_{i}(E(T_{i}))=S_{q_{i}-1,k,0,d}$ with $i\in[1,m]$, then we claim that the
coloring $f_{i}$ is a harmonious $(k,d)$-total coloring of $T_{i}$ with
$i\in[1,m]$.

The theorem follows the induction on adding leaves. ∎

The algorithm in the proof of Theorem 15 is called _Leaf-adding LS-harmonious
algorithm_ , conversely, we can color the edges
$u_{i+1,1}u\,^{\prime}_{i+1,1,j}$ for $u\,^{\prime}_{i+1,1,j}\in
L_{eaf}(u_{i+1,1})$ first, and then color the edges
$u_{i+1,2}u\,^{\prime}_{i+1,2,j}$ for $u\,^{\prime}_{i+1,2,j}\in
L_{eaf}(u_{i+1,2})$, go on in this way, to the last edges
$v_{i+1,b_{i+1}}v\,^{\prime}_{i+1,b_{i+1},j}$ for
$u\,^{\prime}_{i+1,b_{i+1},j}\in L_{eaf}(u_{i+1,b_{i+1}})$. This process is
called _Leaf-adding SL-harmonious algorithm_. So, we have the following
result:

######  Theorem 16.

∗ Each tree $T_{1}$ admits at least $2^{m}$ different harmonious $(k,d)$-total
colorings, where each tree $T_{i+1}=T_{i}-L_{eaf}(T_{i})$ with $i\in[1,m]$,
each $L_{eaf}(T_{i})$ is the leaf set of the tree $T_{i+1}$, and $T_{m+1}$ is
a star such that $T_{m+1}-L_{eaf}(T_{m+1})$ is a graph having one vertex only.

See examples shown in Fig.17, Fig.18 and Fig.19 for understanding the proof of
Theorem 15, and the Leaf-adding LS-harmonious algorithm and the Leaf-adding
SL-harmonious algorithm, respectively.

Figure 17: An example for illustrating the proof of Theorem 15. Figure 18: An
example for illustrating Leaf-adding LS-harmonious algorithm differing from
Leaf-adding SL-harmonious algorithm. Figure 19: An example for illustrating
Leaf-adding SL-harmonious algorithm differing from Leaf-adding LS-harmonious
algorithm.

###  3.4 Connections between parameterized total colorings

######  Definition 16.

∗ Let $G$ be a bipartite and connected $(p,q)$-graph with vertex bipartition
$V(G)=X\cup Y$ with $X\cap Y=\emptyset$, where

$X=\\{x_{i}:i\in[1,s]\\},~{}Y=\\{y_{j}:j\in[1,t]\\},~{}s+t=p$

and $E(G)=\\{e_{i}:i\in[1,q]\\}$. Suppose that $G$ admits a $W$-constraint
$(k,d)$-total coloring $f$ holding

(i) $f:X\rightarrow S_{m,0,0,d}$ and $f:Y\cup E(G)\rightarrow S_{q-1,k,a,d}$;

(ii) $f(x_{i})\leq f(x_{i+1})$ for $i\in[1,s-1]$ and $f(y_{j})\leq f(y_{j+1})$
for $j\in[1,t-1]$;

(iii) $f(e_{i})\leq f(e_{i+1})$ with $i\in[1,q-1]$.

We have the following transformations $g$:

  1. Tra-1.

$g(u)=f(u)$ for $u\in V(G)$;

  2. Tra-2.

$g(x_{i})=f(x_{i})$ for $x_{i}\in X$;

  3. Tra-3.

$g(y_{j})=f(y_{j})$ for $y_{j}\in Y$;

  4. Tra-4.

$g(e_{i})=f(e_{i})$ for each edge $e_{i}\in E(G)$;

  5. Tra-5.

(totally vertex-image) $g(w)=[f(y_{t})+f(x_{1})]-f(w)$ for $w\in V(G)$;

  6. Tra-6.

(totally edge-image) $g(e_{i})=[f(e_{q})+f(e_{1})]-f(e_{i})$ for each edge
$e_{i}\in E(G)$;

  7. Tra-7.

(partly X-image) $g(x_{i})=[f(x_{s})+f(x_{1})]-f(x_{i})$ for $x_{i}\in X$;

  8. Tra-8.

(partly Y-image) $g(y_{j})=[f(y_{t})+f(y_{1})]-f(y_{j})$ for $y_{j}\in Y$;

  9. Tra-9.

(edge-reciprocal) $g(e_{i})=f(e_{q-i+1})$ for each edge $e_{i}\in E(G)$;

  10. Tra-10.

(X-vertex-reciprocal) $g(x_{i})=f(x_{s-i+1})$ for $x_{i}\in X$;

  11. Tra-11.

(Y-vertex-reciprocal) $g(y_{j})=f(y_{t-j+1})$ for $y_{j}\in Y$;

We call $g$:

  1. Col-1.

a _totally vertex-image $(k,d)$-total coloring_ if Tra-4 and Tra-5 hold true;

  2. Col-2.

a _totally edge-image $(k,d)$-total coloring_ if Tra-1 and Tra-6 hold true;

  3. Col-3.

a _partly X-image totally-e-image $(k,d)$-total coloring_ if Tra-3, Tra-6 and
Tra-7 hold true;

  4. Col-4.

a _partly Y-image totally-e-image $(k,d)$-total coloring_ if Tra-2, Tra-6 and
Tra-8 hold true;

  5. Col-5.

a _totally ve-image $(k,d)$-total coloring_ if Tra-5 and Tra-6 hold true;

  6. Col-6.

a _partly XY-image $(k,d)$-total coloring_ if Tra-4, Tra-7 and Tra-8 hold
true;

  7. Col-7.

a _partly XY-image totally-e-image $(k,d)$-total coloring_ if Tra-6, Tra-7 and
Tra-8 hold true;

  8. Col-8.

a _partly X-image e-reciprocal $(k,d)$-total coloring_ if Tra-3, Tra-7 and
Tra-9 hold true;

  9. Col-9.

a _partly Y-image e-reciprocal $(k,d)$-total coloring_ if Tra-2, Tra-8 and
Tra-9 hold true;

  10. Col-10.

an _e-reciprocal $(k,d)$-total coloring_ if Tra-9 hold true;

  11. Col-11.

an _X-reciprocal $(k,d)$-total coloring_ if Tra-3, Tra-4 and Tra-10 hold true;

  12. Col-12.

a _Y-reciprocal $(k,d)$-total coloring_ if Tra-2, Tra-4 and Tra-11 hold true;

  13. Col-13.

an _X-e-reciprocal $(k,d)$-total coloring_ if Tra-3, Tra-9 and Tra-10 hold
true;

  14. Col-14.

a _Y-e-reciprocal $(k,d)$-total coloring_ if Tra-2, Tra-9 and Tra-11 hold
true;

  15. Col-15.

an _XY-reciprocal $(k,d)$-total coloring_ if Tra-4, Tra-10 and Tra-11 hold
true;

  16. Col-16.

a _ve-reciprocally $(k,d)$-total coloring_ if Tra-9, Tra-10 and Tra-11 hold
true. $\square$

Figure 20: A scheme for illustrating Definition 16. Figure 21: Another scheme
for illustrating Definition 16.

Definition 16 enables us to get the following result:

######  Theorem 17.

∗ A bipartite and connected $(p,q)$-graph $G$ admits a graceful $(k,d)$-total
coloring if and only if $G$ admits each one of edge-magic $(k,d)$-total
coloring, graceful-difference $(k,d)$-total coloring, edge-difference
$(k,d)$-total coloring (also, 3C-$(k,d)$-total coloring), felicitous-
difference $(k,d)$-total coloring, harmonious $(k,d)$-total coloring and edge-
antimagic $(k,d)$-total coloring.

###### Proof.

Let $G$ be a bipartite and connected $(p,q)$-graph with its vertex set
$V(G)=X\cup Y$ with $X\cap Y=\emptyset$, and

$X=\\{x_{i}:i\in[1,s]\\},~{}Y=\\{y_{r}:j\in[1,t]\\},~{}s+t=p$

and its edge set $E(G)=\\{e_{i}:i\in[1,q]\\}$.

Suppose that $G$ admits a graceful $(k,d)$-total coloring $f$ defined in
Definition 7, without loss of generality, we have $0=f(x_{1})\leq f(x_{i})\leq
f(x_{i+1})$ for $i\in[1,s-1]$ and

$f(y_{r})\leq f(y_{j+1})\leq f(y_{t})=k+(q-1)d,~{}j\in[1,t-1]$

as well as

$k=f(e_{1})<f(e_{2})<\cdots<f(e_{q})=k+(q-1)d$

holding $f(uv)=|f(u)-f(v)|$ for each edge $uv\in E(G)$ and the edge color set
$f(E(T))=S_{q-1,k,0,d}$. Notice that each edge $e_{r}=x_{r}y_{r}\in E(G)$
holds $f(e_{r})=|f(x_{r})-f(y_{r})|=f(y_{r})-f(x_{r})$ true. We show that the
above graceful $(k,d)$-total coloring $f$ can induce the following
$W$-constraint $(k,d)$-total colorings:

  1. Wtype-1.

By Definition 16, the coloring $g$ is a _partly X-image totally-e-image
$(k,d)$-total coloring_ holding $g(e_{r})=[f(e_{q})+f(e_{1})]-f(e_{r})$ for
each edge $e_{r}\in E(G)$, $g(x_{r})=[f(x_{s})+f(x_{1})]-f(x_{r})$ for
$x_{r}\in X$ and $g(y_{r})=f(y_{r})$ for $y_{r}\in Y$. Then, for each edge
$e_{r}=x_{r}y_{r}\in E(G)$, we have the edge-magic constraint

${\begin{split}g(x_{r})+g(y_{r})+g(x_{r}y_{r})=&[f(x_{s})+f(x_{1})]-f(x_{r})+f(y_{r})+[f(e_{q})+f(e_{1})]-f(e_{r})\\\
=&[f(x_{s})+f(x_{1})]+[f(e_{q})+f(e_{1})]\\\
=&2k+(q-1)d+f(x_{s}),~{}x_{r}y_{r}\in E(G)\end{split}}$

to be a constant. So, $g$ is an _edge-magic $(k,d)$-total coloring_ defined in
Definition 7. If $f(x_{r})=(r-1)d$ for $r\in[1,s]$, we can use
$g(x_{r})=f(x_{s-r+1})$ for $x_{r}\in X$, so $f(x_{r})+f(x_{s-r+1})=(s-1)d$,
and moreover we have the edge-magic constraint

${\begin{split}g(x_{r})+g(y_{r})+g(x_{r}y_{r})&=f(x_{s-r+1})+f(y_{r})+[f(e_{q})+f(e_{1})]-f(e_{r})\\\
&=f(x_{s-r+1})+f(y_{r})+2k+(q-1)d-[f(y_{r})-f(x_{r})]\\\
&=2k+(q-1)d+(s-1)d\end{split}}$

holds true for each edge $x_{r}y_{r}\in E(G)$.

  2. Wtype-2.

Since each edge $e_{r}=x_{r}y_{r}\in E(G)$ holds
$f(e_{r})=|f(x_{r})-f(y_{r})|=f(y_{r})-f(x_{r})$ true, then the coloring $g$
is a _graceful-difference $(k,d)$-total coloring_.

  3. Wtype-3.

According to Definition 16, the coloring $g$ is a _totally edge-image
$(k,d)$-total coloring_ holding $g(u)=f(u)$ for $u\in V(G)$ and
$g(e_{r})=[f(e_{q})+f(e_{1})]-f(e_{r})$ for each edge $e_{r}\in E(G)$. For
each edge $e_{r}=x_{r}y_{r}\in E(G)$, we have
$f(e_{r})=|f(x_{r})-f(y_{r})|=f(y_{r})-f(x_{r})$, and moreover the edge-
difference constraint

${\begin{split}g(e_{r})+|g(y_{r})-g(x_{r})|&=[f(e_{q})+f(e_{1})]-f(e_{r})+|f(y_{r})-f(x_{r})|\\\
&=f(e_{q})+f(e_{1})=2k+(q-1)d\end{split}}$

is equal to a constant for each edge $e_{r}=x_{r}y_{r}\in E(G)$; there exists
an edge $u_{x}u_{y}$ such that

$f(u_{x}u_{y})=[f(e_{q})+f(e_{1})]-f(e_{r}),~{}g(e_{r})=f(u_{x}u_{y})=|f(u_{y})-f(u_{x})|=|g(u_{y})-g(u_{x})|$

we get $g(e_{r})=|g(u_{y})-g(u_{x})|$; and

${\begin{split}s(e_{r})&=|g(y_{r})-g(x_{r})|-g(e_{r})=|f(y_{r})-f(x_{r})|-[f(e_{q})+f(e_{1})]+f(e_{r})\\\
&=|f(y_{r})-f(x_{r})|-f(u_{x}u_{y})\end{split}}$

and

$s(u_{x}u_{y})=|g(u_{y})-g(u_{x})|-g(u_{x}u_{y})=|f(u_{y})-f(u_{x})|-[f(e_{q})+f(e_{1})]+f(e_{r})$

so $s(e_{r})+s(u_{x}u_{y})=f(e_{q})+f(e_{1})$ is a constant.

We claim that $g$ is a _3C- $(k,d)$-total coloring_, also, an _edge-difference
$(k,d)$-total coloring_ defined in Definition 7.

  4. Wtype-4.

By Definition 16, the coloring $g$ is a _partly Y-image totally-e-image
$(k,d)$-total coloring_ holding $g(e_{r})=[f(e_{q})+f(e_{1})]-f(e_{r})$ for
each edge $e_{r}\in E(G)$, $g(x_{r})=f(x_{r})$ for $x_{r}\in X$ and
$g(y_{r})=[f(y_{t})+f(y_{1})]-f(y_{r})$ for $y_{r}\in Y$. For each edge
$e_{r}=x_{r}y_{r}\in E(G)$, we compute the felicitous-difference constraint

${\begin{split}|g(x_{r})+g(y_{r})-g(e_{r})|&=f(x_{r})+[f(y_{t})+f(y_{1})]-f(y_{r})-\\{[f(e_{q})+f(e_{1})]-f(e_{r})\\}\\\
&=f(y_{t})+f(y_{1})-[f(e_{q})+f(e_{1})]\\\ &=f(y_{1})-k\end{split}}$

which enables us to claim that $g$ is a _felicitous-difference $(k,d)$-total
coloring_.

  5. Wtype-5.

We defined a transformation $g$ as:

(i) $g(x_{r})=f(x_{r})$ for $x_{r}\in X$;

(ii) $g(y_{r})=[f(y_{t})+f(y_{1})]-f(y_{r})$ for $y_{r}\in Y$; and

(iii) $g(e_{r})=g(x_{r})+g(y_{r})~{}(\bmod^{*}qd)$ by
$g(uv)-k=[g(u)+g(v)-k](\bmod~{}qd)$ for each edge $uv\in E(G)$.

And furthermore we have

${\begin{split}g(e_{r})-k&=g(x_{r})+g(y_{r})-k~{}(\bmod~{}qd)=f(x_{r})+[f(y_{t})+f(y_{1})]-f(y_{r})-k~{}(\bmod~{}qd)\\\
&=2k+(q-1)d-f(e_{r})-k~{}(\bmod~{}qd)\\\ &=k+(q-1)d-f(e_{r})\in
S_{q-1,0,0,d}\end{split}}$

so the edge color set $g(E(G))=S_{q-1,k,0,d}$, which means that $g$ is a
_harmonious $(k,d)$-total coloring_ defined in Definition 7.

  6. Wtype-6.

By Definition 16, a _partly Y-image e-reciprocal $(k,d)$-total coloring_ $g$
holds:

(i) $g(x_{r})=f(x_{r})$ for $x_{r}\in X$;

(ii) $g(y_{r})=[f(y_{t})+f(y_{1})]-f(y_{r})$ for $y_{r}\in Y$; and

(iii) $g(e_{i})=f(e_{q-i+1})$ for each edge $e_{i}\in E(G)$.

We have the edge-antimagic constraint

${\begin{split}g(x_{r})+g(e_{r})+g(y_{r})&=f(x_{r})+f(e_{q-r+1})+[f(y_{t})+f(y_{1})]-f(y_{r})\\\
&=[f(y_{t})+f(y_{1})]-2f(e_{r})+f(e_{q-r+1})+f(e_{r})\\\
&=2k+(q-1)d+2k+(q-1)d-2f(e_{r})\\\
&=4k+2(q-1)d-2f(e_{r})\in\\{2k,2k+2d,2k+4d,\dots,2k+2(q-1)d\\}\end{split}}$

Thereby, the coloring $g$ is an _edge-antimagic $(k,d)$-total coloring_
defined in Definition 7.

The proof of the theorem is complete. ∎

######  Theorem 18.

∗ A connected graph $G$ admits a graceful $(k,d)$-total coloring if and only
if there exists a tree $T$ obtained from $G$ by the vertex-splitting tree-
operation and $T$ admits a graceful $(k,d)$-total coloring, such that $T$
admits a colored graph homomorphism to $G$, that is, $T\rightarrow G$.

###  3.5 Trees admitting magic-constraint total colorings

For dealing with issues based on magic-constraint total colorings we introduce
the Leaf-adding $(k,d)$-magic-constraint algorithms, “SL” means “From Small to
Large”, and “LS” means “From Large to Small” in the following algorithms: (1)
Leaf-adding LS-edge-difference (SL-edge-difference) algorithm; (2) Leaf-adding
LS-graceful-difference (SL-graceful-difference) algorithm.

######  Definition 17.

∗ Leaf-added trees based on the adding leaves operation. Let $(X,Y)$ be the
bipartition of a tree $H$, where $X=\\{x_{1},x_{2},\dots,x_{s}\\}$ and
$Y=\\{y_{1},y_{2},\dots,y_{t}\\}$ with

$s+t=p=|V(H)|=1+|E(H)|$

We add new leaves to $H$ as: Each vertex $x_{i}\in X$ is added the leaves
$x_{i,1},x_{i,2},\dots,x_{i,a_{i}}$ of a leaf set $L_{eaf}(x_{i})$ with
$i\in[1,s]$, and each vertex $y_{j}\in Y$ is added the leaves
$y_{j,1},y_{j,2},\dots,y_{j,b_{j}}$ of a leaf set $L_{eaf}(y_{j})$ with
$j\in[1,t]$. The resultant tree is denoted as $H_{L}$, called _leaf-added
tree_. So, the leaf-added tree $H_{L}$ has its own bipartition
$(X\,^{\prime},Y\,^{\prime})$, where

$X\,^{\prime}=X\bigcup\left(\bigcup^{t}_{k=1}L_{eaf}(y_{k})\right),~{}Y\,^{\prime}=Y\bigcup\left(\bigcup^{s}_{k=1}L_{eaf}(x_{k})\right)$

Let $A=\sum^{s}_{k=1}a_{k}$ and $B=\sum^{t}_{k=1}b_{k}$.

######  Theorem 19.

∗ Each tree $T$ with diameter $D(T)\geq 3$ admits at least $2^{m}$ different
edge-difference $(k,d)$-total colorings with
$m+1=\left\lceil\frac{D(T)}{2}\right\rceil$.

###### Proof.

Use the notation and terminology of defining a leaf-added tree $H_{L}$
obtained from a tree $H$ in Definition 17. Suppose that this tree $H$ admits
an edge-difference $(k,d)$-total coloring $f$ with

$f(x_{i}y_{j})+|f(y_{j})-f(x_{i})|=f(x_{i}y_{j})+f(y_{j})-f(x_{i})=2k+\alpha\cdot
d$

for each edge $x_{i}y_{j}\in E(H)$, and the edge color set
$f(E(H))=S_{p-2,k,0,d}$. Without loss of generality, we have

$f(x_{1})\leq f(x_{2})\leq\cdots\leq f(x_{s}),\quad f(y_{1})\leq
f(y_{2})\leq\cdots\leq f(y_{t})$

We define a total coloring $g$ of the leaf-added tree $H_{L}$ by the following
algorithms.

1\. Leaf-adding LS-edge-difference algorithm.

LSed-1. Vertex colors are $g(x_{i})=f(x_{i})$ for $x_{i}\in X\subset
X\,^{\prime}$ and $g(y_{j})=f(y_{j})+(A+B)d$ for $y_{j}\in Y\subset
Y\,^{\prime}$.

LSed-2. Edge $x_{i}y_{j}$ are colored with $g(x_{i}y_{j})=f(x_{i}y_{j})$ for
each edge $x_{i}y_{j}\in E(H)\subset E(H_{L})$, so
$g(x_{i}y_{j})=f(x_{i}y_{j})\leq e^{*}=k+(p-2)d$, and we have the edge-
difference constraints

$g(x_{i}y_{j})+|g(y_{j})-g(x_{i})|=f(x_{i}y_{j})+f(y_{j})+(A+B)d-f(x_{i})=t^{*},~{}x_{i}y_{j}\in
E(H)\subset E(H_{L})$

where $t^{*}=2k+(\alpha+A+B)d$.

LSed-3. From Large to Small. Set $g(y_{t}y_{t,i})=id+e^{*}$ for
$i\in[1,b_{t}]$, and moreover

$g(y_{t-r}y_{t-r,i})=id+e^{*}+\sum^{r}_{k=1}b_{t-k+1},~{}i\in[1,b_{t-r}],~{}r\in[1,t-1]$
(46)

Clearly, $g(y_{1}y_{1,b_{1}})=e^{*}+B$. And set
$g(y_{j,i})=g(y_{j}y_{j,i})+g(y_{j})-t^{*}$ for each edge $y_{j}y_{j,i}\in
E(H_{L})$.

LSed-4. From Large to Small. Set $g(x_{s}x_{s,i})=id+e^{*}+B$ for
$i\in[1,a_{s}]$, in general, we have edge colors

$g(x_{s-r}x_{s-r,i})=id+e^{*}+B+\sum^{r}_{k=1}a_{s-k+1},~{}i\in[1,a_{s-r}],~{}r\in[1,s-1]$
(47)

and $g(x_{1}x_{1,a_{1}})=e^{*}+A+B$. And we set
$g(x_{j,i})=t^{*}+g(x_{j})-g(x_{j}x_{j,i})$ for each edge $x_{j}x_{j,i}\in
E(H_{L})$.

Thereby, we get the edge-difference constraint $g(uv)+|g(u)-g(v)|=t^{*}$ for
each edge $uv\in E(H_{L})$ such that the edge color set

$g(E(H_{L}))=S_{p-2,k,0,d}\cup\\{e^{*}+d,e^{*}+2d,\dots,e^{*}+A+B\\}=S_{p-2+A+B,k,0,d}$

so the Leaf-adding LS-edge-difference algorithm determines an edge-difference
$(k,d)$-total coloring $g$ of the leaf-added tree $H_{L}$.

We show another algorithm for determining another edge-difference
$(k,d)$-total coloring $h$ of the leaf-added tree $H_{L}$ as follows:

2\. Leaf-adding SL-edge-difference algorithm.

SLed-1. Each vertex $x_{i}\in X\subset X\,^{\prime}$ is colored by
$h(x_{i})=f(x_{i})$, and each vertex $y_{j}\in Y\subset Y\,^{\prime}$ is cored
by $h(y_{j})=f(y_{j})+(A+B)d$.

SLed-2. Edge colors are $h(x_{i}y_{j})=f(x_{i}y_{j})$ for each edge
$x_{i}y_{j}\in E(H)\subset E(H_{L})$, so $h(x_{i}y_{j})=f(x_{i}y_{j})\leq
e^{*}=k+(p-2)d$, and there are edge-difference constraints

$h(x_{i}y_{j})+|h(y_{j})-h(x_{i})|=f(x_{i}y_{j})+f(y_{j})+(A+B)d-f(x_{i})=t^{*},~{}x_{i}y_{j}\in
E(H)\subset E(H_{L})$

where $t^{*}=2k+(\alpha+A+B)d$.

SLed-3. From Small to Large. Set $h(x_{1}x_{1,i})=id+e^{*}$ for
$i\in[1,a_{1}]$, in general, there is

$h(x_{r}x_{r,i})=id+e^{*}+\sum^{r-1}_{k=1}a_{k},~{}i\in[1,a_{r}],~{}r\in[2,s]$
(48)

and $h(x_{s}x_{s,a_{s}})=e^{*}+A$. And we color vertex $x_{j,i}$ with
$h(x_{j,i})=t^{*}+h(x_{j})-h(x_{j}x_{j,i})$ for each edge $x_{j}x_{j,i}\in
E(H_{L})$.

SLed-4. From Small to Large. Set $h(y_{1}y_{1,i})=id+e^{*}+A$ for
$i\in[1,b_{1}]$, and moreover

$h(y_{r}y_{r,i})=id+e^{*}+A+\sum^{r-1}_{k=1}b_{k},~{}i\in[1,b_{r}],~{}r\in[2,t]$
(49)

so, $h(y_{t}y_{t,b_{t}})=e^{*}+A+B$. We set
$h(y_{j,i})=h(y_{j}y_{j,i})+h(y_{j})-t^{*}$ for each edge $y_{j}y_{j,i}\in
E(H_{L})$.

Clearly, the edge-difference constraint $h(uv)+|h(u)-h(v)|=t^{*}$ holds for
each edge $uv\in E(H_{L})$, and the edge color set

$h(E(H_{L}))=S_{p-2+A+B,k,0,d}$

that is the Leaf-adding LS-edge-difference algorithm determines another edge-
difference $(k,d)$-total coloring $h$ of the leaf-added tree $H_{L}$.

Let $T_{1}$ be a tree being not a star, and let $L_{eaf}(T_{1})$ be the set of
all leaves of $T_{1}$. Furthermore, we have trees
$T_{i+1}=T_{i}-L_{eaf}(T_{i})$ with $i\in[1,m]$, and each tree $T_{i}$ has its
own leaf set $L_{eaf}(T_{i})$, $T_{m+1}$ is a star. Since the star $T_{m+1}$
admits an edge-difference $(k,d)$-total coloring, we apply two algorithms
introduced above to each tree $T_{i+1}$ for determining two different edge-
difference $(k,d)$-total colorings of the leaf-added tree
$T_{i}=T_{i+1}+L_{eaf}(T_{i})$, since each number $|L_{eaf}(T_{i})|\geq 2$
according to each tree having at least two leaves.

In the above each step, we have two ways to realize edge-difference
$(k,d)$-total colorings, so $T_{1}$ admits at least $2^{m}$ different edge-
difference $(k,d)$-total colorings.

This is the complete proof of the theorem. ∎

Figure 22: (a) $H_{1}$ admits an edge-difference $(k,d)$-total coloring
$f_{1}$ holding the edge-difference constraint
$f_{1}(uv)+|f_{1}(u)-f_{1}(v)|=2k+6d$; (b) $H_{2}$ admits an edge-difference
$(k,d)$-total coloring $f_{2}$ holding the edge-difference constraint
$f_{2}(uv)+|f_{2}(u)-f_{2}(v)|=2k+14d$ from Large to Small; (c) $H_{3}$ admits
an edge-difference $(k,d)$-total coloring $f_{3}$ holding the edge-difference
constraint $f_{3}(uv)+|f_{3}(u)-f_{3}(v)|=2k+14d$ from Small to Large.

######  Theorem 20.

∗ Each tree $T$ with diameter $D(T)\geq 3$ admits at least $2^{m}$ different
graceful-difference $(k,d)$-total colorings with
$m+1=\left\lceil\frac{D(T)}{2}\right\rceil$.

###### Proof.

Use the notation and terminology of defining a leaf-added tree $H_{L}$
obtained from a tree $H$ in Definition 17. Suppose that this tree $H$ admits a
graceful-difference $(k,d)$-total coloring $f$ with the graceful-difference
constraint

$\big{|}|f(u)-f(v)|-f(uv)\big{|}=\beta\cdot d,~{}uv\in E(H)$

and the edge color set $f(E(H))=S_{p-2,k,0,d}$, and let $e^{*}=k+(p-2)d$.
Without loss of generality, there are vertex color inequalities

$f(x_{1})\leq f(x_{2})\leq\cdots\leq f(x_{s}),~{}f(y_{1})\leq
f(y_{2})\leq\cdots\leq f(y_{t})$

We define a total coloring $g$ for the leaf-added tree $H_{L}$ by the
following algorithm.

1\. Leaf-adding SL-graceful-difference algorithm.

SLgd-1. Set vertex colors $g(x_{i})=f(x_{i})+(A+B)d$ for $x_{i}\in X\subset
X\,^{\prime}$, and edge colors $g(y_{j})=f(y_{j})+(A+B)d$ for $y_{j}\in
Y\subset Y\,^{\prime}$, and $g(x_{i}y_{j})=f(x_{i}y_{j})+(A+B)d$ for each edge
$x_{i}y_{j}\in E(H)$. Thus, each edge $uv\in E(H)\subset E(H_{L})$ holds the
graceful-difference constraint

$\big{|}|g(u)-g(v)|-g(uv)\big{|}=\big{|}|f(u)-f(v)|-f(uv)-(A+B)d\big{|}=(\beta+A+B)d$

and let $t^{*}=(\beta+A+B)d$.

SLgd-2. From Small to Large. Set edge colors $g(x_{1}x_{1,i})=id+e^{*}$ for
$i\in[1,a_{1}]$, in general, we get

$g(x_{r}x_{r,i})=id+e^{*}+\sum^{r-1}_{k=1}a_{k},~{}i\in[1,a_{r}],~{}r\in[2,s]$
(50)

and $g(x_{s}x_{s,a_{s}})=e^{*}+A$. And we set
$g(x_{j,i})=g(x_{j}x_{j,i})+g(x_{j})-t^{*}$ for each edge $x_{j}x_{j,i}\in
E(H_{L})$.

SLgd-3. From Small to Large. Set edge colors $g(y_{1}y_{1,i})=id+e^{*}+A$ for
$i\in[1,b_{1}]$, and moreover

$g(y_{r}y_{r,i})=id+e^{*}+A+\sum^{r-1}_{k=1}b_{k},~{}i\in[1,b_{r}],~{}r\in[2,t]$
(51)

so, $g(y_{t}y_{t,b_{t}})=e^{*}+A+B$. We color $y_{j,i}$ with
$g(y_{j,i})=g(y_{j})-g(y_{j}y_{j,i})-t^{*}$, or
$g(y_{j,i})=g(y_{j})+t^{*}-g(y_{j}y_{j,i})$ for each edge $y_{j}y_{j,i}\in
E(H_{L})$. Thereby, we get the following graceful-difference constraints

1\. $\big{|}|g(x_{j})-g(x_{j,i})|-g(x_{j}x_{j,i})\big{|}=t^{*}$ for each edge
$x_{j}x_{j,i}\in E(H_{L})$, and

2\. $\big{|}|g(y_{j})-g(y_{j,i})|-g(y_{j}y_{j,i})\big{|}=t^{*}$ for each edge
$y_{j}y_{j,i}\in E(H_{L})$.
So, $g$ is a graceful-difference $(k,d)$-total coloring of the leaf-added tree
$H_{L}$.

We show another algorithm for defining another graceful-difference
$(k,d)$-total coloring $h$ of the leaf-added tree $H_{L}$ as follows:

2\. Leaf-adding LS-graceful-difference algorithm.

LSgd-1. Set vertex colors $h(x_{i})=f(x_{i})+(A+B)d$ for $x_{i}\in X\subset
X\,^{\prime}$, and $h(y_{j})=f(y_{j})+(A+B)d$ for $y_{j}\in Y\subset
Y\,^{\prime}$, and edge colors are $h(x_{i}y_{j})=f(x_{i}y_{j})+(A+B)d$ for
each edge $x_{i}y_{j}\in E(H)$. So, each edge $uv\in E(H)\subset E(H_{L})$
holds the graceful-difference constraint

$\big{|}|h(u)-h(v)|-h(uv)\big{|}=\big{|}|f(u)-f(v)|-f(uv)-(A+B)d\big{|}=(\beta+A+B)d$

and let $t^{*}=(\beta+A+B)d$.

LSgd-2. From Large to Small. Set edge colors $h(y_{t}y_{t,i})=id+e^{*}$ for
$i\in[1,b_{t}]$, and moreover

$h(y_{t-r}y_{t-r,i})=id+e^{*}+\sum^{r}_{k=1}b_{t-k+1},~{}i\in[1,b_{t-r}],~{}r\in[1,t-1]$
(52)

Clearly, $h(y_{1}y_{1,b_{1}})=e^{*}+B$. And we set
$h(y_{j,i})=h(y_{j})-h(y_{j}y_{j,i})-t^{*}$ for each edge $y_{j}y_{j,i}\in
E(H_{L})$, also, the graceful-difference constraint

$\big{|}|h(y_{j,i})-h(y_{j})|-h(y_{j}y_{j,i})\big{|}=t^{*},~{}y_{j}y_{j,i}\in
E(H_{L})$

holds true.

LSgd-3. From Large to Small. Set edge colors $h(x_{s}x_{s,i})=id+e^{*}+B$ for
$i\in[1,a_{s}]$, in general, we have

$h(x_{s-r}x_{s-r,i})=id+e^{*}+B+\sum^{r}_{k=1}a_{s-k+1},~{}i\in[1,a_{s-r}],~{}r\in[1,s-1]$
(53)

and $h(x_{1}x_{1,a_{1}})=e^{*}+A+B$. And we set
$h(x_{j,i})=h(x_{j})+h(x_{j}x_{j,i})-t^{*}$ for each edge $x_{j}x_{j,i}\in
E(H_{L})$, that is the graceful-difference constraint

$\big{|}|h(x_{j,i})-h(x_{j})|-h(x_{j}x_{j,i})\big{|}=t^{*},~{}x_{j}x_{j,i}\in
E(H_{L})$

holds true.

Thereby, the leaf-added tree $H_{L}$ admits $h$ as its graceful-difference
$(k,d)$-total coloring.

Let $T_{1}$ be a tree being not a star, and let $L_{eaf}(T_{1})$ be the set of
all leaves of $T_{1}$. Furthermore, we have trees
$T_{i+1}=T_{i}-L_{eaf}(T_{i})$ with $i\in[1,m]$, and each tree $T_{i}$ has its
own leaf set $L_{eaf}(T_{i})$, $T_{m+1}$ is a star. Since the star $T_{m+1}$
admits an graceful-difference $(k,d)$-total coloring, we apply two algorithms
introduced above to each tree $T_{i+1}$ for determining two different
graceful-difference $(k,d)$-total colorings of the leaf-added tree
$T_{i}=T_{i+1}+L_{eaf}(T_{i})$, because of each number $|L_{eaf}(T_{i})|\geq
2$ from each tree having at least two leaves.

In the above each step, we have two ways to realize graceful-difference
$(k,d)$-total colorings, so $T_{1}$ admits at least $2^{m}$ different
graceful-difference $(k,d)$-total colorings.

This theorem is covered. ∎

Figure 23: (a) $H_{1}$ admits a graceful-difference $(k,d)$-total coloring
$g_{1}$ holding the graceful-difference constraint
$\big{|}|g_{1}(u)-g_{1}(v)|-g_{1}(uv)\big{|}=d$; (b) $H_{2}$ admits a
graceful-difference $(k,d)$-total coloring $g_{2}$ holding the graceful-
difference constraint $\big{|}|g_{2}(u)-g_{2}(v)|-g_{2}(uv)\big{|}=7d$ from
Small to Large; (c) $H_{3}$ admits a graceful-difference $(k,d)$-total
coloring $g_{3}$ holding the graceful-difference constraint
$\big{|}|g_{3}(u)-g_{3}(v)|-g_{3}(uv)\big{|}=7d$ from Large to Small.

By Theorem 14 and the transformation from a graceful $(k,d)$-total coloring to
a felicitous-difference $(k,d)$-total coloring, or to an edge-magic
$(k,d)$-total coloring in the proof of Theorem 17, we have the following two
results in Theorem 21 and Theorem 22:

######  Theorem 21.

∗ Each tree $T$ with diameter $D(T)\geq 3$ admits at least $2^{m}$ different
felicitous-difference $(k,d)$-total colorings for
$m+1=\left\lceil\frac{D(T)}{2}\right\rceil$.

See examples of trees admitting felicitous-difference $(k,d)$-total colorings
shown in Fig.24 and Fig.25.

Figure 24: A scheme for illustrating Theorem 21, where (a) $T_{1}$ admits a
felicitous-difference $(k,d)$-total coloring $f_{1}$ holding the felicitous-
difference constraint $|f_{1}(u)+f_{1}(v)-f_{1}(uv)|=2d$; (b) $T_{2}$ admits a
felicitous-difference $(k,d)$-total coloring $f_{2}$ holding the felicitous-
difference constraint $|f_{2}(u)+f_{2}(v)-f_{2}(uv)|=d$; (c) $T_{3}$ admits a
felicitous-difference $(k,d)$-total coloring $f_{3}$ holding the felicitous-
difference constraint $|f_{3}(u)+f_{3}(v)-f_{3}(uv)|=7d$. Figure 25: (a)
$G_{1}$ admits a felicitous-difference $(k,d)$-total coloring $h_{1}$ holding
the felicitous-difference constraint $|h_{1}(u)+h_{1}(v)-h_{1}(uv)|=4d$; (b)
$G_{2}$ admits a felicitous-difference $(k,d)$-total coloring $h_{2}$ holding
the felicitous-difference constraint $|h_{2}(u)+h_{2}(v)-h_{2}(uv)|=12d$ from
Small to Large; (c) $G_{3}$ admits a total coloring $h_{3}$ holding the
felicitous-difference constraint $|h_{3}(u)+h_{3}(v)-h_{3}(uv)|=12d$ from
Large to Small.

######  Theorem 22.

∗ Each tree $T$ with diameter $D(T)\geq 3$ admits at least $2^{m}$ different
edge-magic $(k,d)$-total colorings with
$m+1=\left\lceil\frac{D(T)}{2}\right\rceil$.

See examples shown in Fig.26 and Fig.27 for understanding Theorem 22.

Figure 26: (a) $I_{1}$ admits an edge-magic $(k,d)$-total coloring $s_{1}$
holding the edge-magic constraint $s_{1}(u)+s_{1}(uv)+s_{1}(v)=2k+8d$; (b)
$I_{2}$ admits an edge-magic $(k,d)$-total coloring $s_{2}$ holding the edge-
magic constraint $s_{2}(u)+s_{2}(uv)+s_{2}(v)=2k+31d$ from Small to Large; (c)
$I_{3}$ admits an edge-magic $(k,d)$-total coloring $s_{3}$ holding the edge-
magic constraint $s_{3}(u)+s_{3}(uv)+s_{3}(v)=2k+36d$ from Large to Small.
Figure 27: (a) $J_{1}$ admits an edge-magic $(k,d)$-total coloring $l_{1}$
holding the edge-magic constraint $l_{1}(u)+l_{1}(uv)+l_{1}(v)=2k+10d$; (b)
$J_{2}$ admits an edge-magic $(k,d)$-total coloring $l_{2}$ holding the edge-
magic constraint $l_{2}(u)+l_{2}(uv)+l_{2}(v)=2k+18d$ from Small to Large; (c)
$J_{3}$ admits an edge-magic $(k,d)$-total coloring $l_{3}$ holding the edge-
magic constraint $l_{3}(u)+l_{3}(uv)+l_{3}(v)=2k+18d$ from Large to Small.

##  4 Magic-constraint parameterized algorithms

In this subsection, the sentence “RANDOMLY-LEAF-adding algorithm” is
abbreviated as “RLA-algorithm”.

###  4.1 Parameterized graceful-difference total labelings/colorings

∗ RLA-algorithm-A for the graceful-difference $(k,d)$-total coloring.

Input: A connected bipartite $(p,q)$-graph $G$ admitting a set-ordered
graceful labeling $f$.

Output: A connected bipartite $(p+m,q+m)$-graph $G^{*}$ admitting a graceful-
difference $(k,d)$-total coloring, where $G^{*}$ is the result of adding
randomly $m$ leaves to $G$.

Step A-1. Initialization. Since a connected bipartite $(p,q)$-graph $G$
admitting a set-ordered graceful labeling $f$, we have the vertex set
$V(G)=X\cup Y$ with $X\cap Y=\emptyset$, where

$X=\\{x_{1},x_{2},\dots,x_{s}\\},~{}Y=\\{y_{1},y_{2},\dots,y_{t}\\},~{}s+t=p=|V(G)|$

such that

$0=f(x_{1})<f(x_{2})<\cdots<f(x_{s})<f(y_{1})<f(y_{2})<\cdots<f(y_{t})=q$

with the edge color set