Graph Set-colorings And Hypergraphs
In Topological Coding
Bing YAO, Fei MA
()

###### Contents

  1. 1 Introduction
    1. 1.1 Background of investigation
    2. 1.2 Terminology and notation
    3. 1.3 Graph operations
      1. 1.3.1 Operations of adding or removing vertices and edges
      2. 1.3.2 Vertex-splitting and Vertex-coinciding operations
      3. 1.3.3 Operations of graph homomorphisms
      4. 1.3.4 Edge-coinciding and edge-splitting operations
    4. 1.4 Basic graph labelings and colorings
  2. 2 Set-type colorings and labelings
    1. 2.1 Set-colorings
    2. 2.2 Set-labeling
    3. 2.3 Connection of traditional colorings and set-colorings
    4. 2.4 Researching topics of set-colorings and set-labelings
  3. 3 Set-colorings related with hypergraphs
    1. 3.1 Basic concepts of hypergraphs
    2. 3.2 Intersected-graphs of hypergraphs
    3. 3.3 Set-type Topcode-matrices
    4. 3.4 Subgraphs of intersected-graphs
  4. 4 Algorithms for producing set-colorings
    1. 4.1 PSCS-algorithms
    2. 4.2 Set-colorings with multiple intersections
  5. 5 Graph operations on intersected-graphs and hypergraphs
    1. 5.1 Set-increasing operation and set-decreasing operations
    2. 5.2 Splitting-type and coinciding-type operations
      1. 5.2.1 Edge-splitting and edge-coinciding operations of intersected-graphs
      2. 5.2.2 Vertex-splitting and vertex-coinciding operations of intersected-graphs
      3. 5.2.3 Set-cut-sets, Hypergraph connectivity
    3. 5.3 Miscellaneous set-type colorings
      1. 5.3.1 Pan-operation graphs
      2. 5.3.2 Colorings of hypergraphs
      3. 5.3.3 The set of hyperedge sets
      4. 5.3.4 Set-set-colorings, Compound hypergraphs
    4. 5.4 Set-colored graph homomorphisms, Hypergraph homomorphisms
    5. 5.5 Set-colored graphic groups
    6. 5.6 Preliminarily studying of hypernetworks
      1. 5.6.1 Dynamic hypernetworks
      2. 5.6.2 Scale-free intersected-networks
      3. 5.6.3 Intersected-network lattices
  6. 6 Conclusion

Graph Set-colorings And Hypergraphs
In Topological Coding
Bing Yao ${}^{a,~{}\dagger}$ Fei Ma ${}^{b,~{}\ddagger}$
a. College of Mathematics and Statistics, Northwest Normal University,
Lanzhou, 730070 CHINA

b. School of Electronics Engineering and Computer Science, Peking University,
Beijing, 100871, CHINA

†<EMAIL_ADDRESS>‡<EMAIL_ADDRESS>
()

> Abstract: In order to make more complex number-based strings from
> topological coding for defending against the intelligent attacks equipped
> with quantum computing and providing effective protection technology for the
> age of quantum computing, we will introduce set-colored graphs admitting
> set-colorings that has been considerable cryptanalytic significance, and
> especially related with hypergraphs. We use the set-coloring of graphs to
> reflect the intersection of elements, and add other constraint requirements
> to express more connections between sets (as hyperedges). Since we try to
> find some easy and effective techniques based on graph theory for practical
> application, we use intersected-graphs admitting set-colorings defined on
> hyperedge sets to observe topological structures of hypergraphs, string-type
> Topcode-matrix, set-type Topcode-matrix, graph-type Topcode-matrix,
> hypergraph-type Topcode-matrix, matrix-type Topcode-matrix _etc_. We will
> show that each connected graph is the intersected-graph of some hypergraph
> and investigate hypergraph’s connectivity, colorings of hypergraphs,
> hypergraph homomorphism, hypernetworks, scale-free network generator,
> compound hypergraphs having their intersected-graphs with vertices to be
> hypergraphs (for high-dimensional extension diagram). Naturally, we get
> various graphic lattices, such as edge-coincided intersected-graph lattice,
> vertex-coincided intersected-graph lattice, edge-hamiltonian graphic
> lattice, hypergraph lattice and intersected-network lattice. Many techniques
> in this article can be translated into polynomial algorithms, since we are
> aiming to apply hypergraphs and graph set-colorings to homomorphic
> encryption and asymmetric cryptograph.
> Mathematics Subject classification: 05C15, 05C65, 05C60, 06B30, 22A26, 81Q35
> Keywords: Hypergraph; graph coloring/labelling; set-coloring; graphic
> lattice; graph homomorphism; asymmetric cryptograph; hypernetwork;
> topological coding.

##  1 Introduction

As known, all things of high-dimensional data sets are interrelated and
interact on each other, we need to study the complex structures of high-
dimensional data sets, and the interaction between high-dimensional data sets,
one of research tools is hypergraph. Simplicial complex connects topology and
graph theory, and provides a visual angle to observe hypergraphs through
topological structure. Hypergraphs can tease out of big data sets proposed in
“ _How Big Data Carried Graph Theory Into New Dimensions_ ” by Stephen Ornes
[10]. And large data sets in practical application show that the impact of
groups often exceeds that of individuals, thereby, it is more and more
important to study hypergraphs.

###  1.1 Background of investigation

Since the hypergraph theory was proposed systematically by Claude Berge in
1973, more and more attention has been paid to the research of hypergraph
theory and its application. Some applications of _undirected hypergraphs_ are
mentioned as: Modeling such things as satisfiability problems, databases,
machine learning, and Steiner tree problems, hypergraphs have been extensively
used in machine learning tasks as the data model and classifier regularization
(mathematics), the applications include recommender system (communities as
hyperedges), image retrieval (correlations as hyperedges), and bioinformatics
(biochemical interactions as hyperedges). Representative hypergraph learning
techniques include hypergraph spectral clustering that extends the spectral
graph theory with hypergraph Laplacian, and hypergraph semi-supervised
learning that introduces extra hypergraph structural cost to restrict the
learning results. _Directed hypergraphs_ can be used to model things including
telephony applications, detecting money laundering, operations research, and
transportation planning, and can also be used to model Horn-satisfiability.

Tom Siegfried said: “Wolfram’s hypergraphs reproduce many of the consequences
of various physical theories, such as Einstein’s special theory of relativity.
Traveling rapidly slows down time (as special relativity says) because
_hypergraph structures_ corresponding to moving objects make an angle through
the hypergraph that extends the distance between updates (or time steps). The
speed of light is a maximum velocity, as relativity states, because it
represents the maximum rate that information can spread through the hypergraph
as it updates. And gravity described by Einstein’s general theory of
relativity emerges in the relationship between features in the hypergraph that
can be interpreted as matter particles. Particles would be small sets of
linked points that persist as the hypergraph updates, something like “little
lumps of space” with special properties [11].”

Graph set-type colorings have been investigated by many researchers. Bollobás
and Thomason [6] researched: An $r$-set coloring of a graph $G$ is an
assignment of $r$ distinct colors to each vertex of $G$ so that the sets of
colors assigned to adjacent vertices are disjoint. The _sumset-labelling_ was
discussed in [25]. Hegde [9] introduced another type of set-coloring: “A set
coloring of the graph $G$ is an assignment (function) of distinct subsets of a
finite set $X$ of colors to the vertices of the graph, where the colors of the
edges are obtained as the symmetric differences of the sets assigned to their
end vertices which are also distinct.” Balister, Győi and Schelp [1]
discussed: A graph $G$ is strongly set-colorable if $V(G)\cup E(G)$ can be
assigned distinct nonempty subsets of a set of order $n$, where
$|V(G)|+|E(G)|=2^{n}-1$, such that each edge is assigned the _symmetric
difference_ of its end vertices.

Set-colorings serve to make more complex number-based strings from topological
coding for defending against the intelligent attacks equipped with quantum
computing and providing effective protection technology for the age of quantum
computing, and we will show that set-coloring becomes a topological tool of
investigating hypergraphs.

As a subset system of a finite set, _hypergraph is the most general discrete
structure_ , which is widely used in information science, life science and
other fields. However, hypergraphs are more difficult to draw on paper than
graphs, there are methods for the visualization of hypergraphs, such as Venn
diagram, PAOH _etc_. Professor Wang, in his book tilted “Information
Hypergraph Theory” [12], has investigated the structure of intersected-graphs
of hypergraphs.

For considering “ _codes are related with graphs, conversely, graphs are as
codes_ ” proposed by many researchers of computer and information security, we
see examples shown in Fig.1, and get the following facts:

(1) Each graph $H_{i}$ is not isomorphic to others, also $H_{i}\not\cong
H_{j}$, if $i\neq j$ for $1\leq i,j\leq 5$.

(2) Each $H_{k}$ has its own Topcode-matrix $T_{code}$ shown in Eq.(2).

(3) The Topcode-matrix $T_{code}$ distributes us $(27)!$ number-based strings
in total, like $s_{1}(27)$, $s_{2}(27)$, $s_{3}(27)$ and $s_{4}(27)$ shown in
Eq.(1).

$\begin{array}[]{ccccccccc}s_{1}(27)=515524337542358760278980090&s_{2}(27)=415523235743055862077880099\\\
s_{3}(27)=000203234123456789987857555&s_{4}(27)=002002123334455555677788899\end{array}$
(1)

(4) Finding a graph to indicate a given number-based string is not a slight
work, although we can use colorings and labelings of graph theory. The
technique of Topcode-matrices (see $T_{code}$ shown in Eq.(2)) enables us to
obtain the following theorem:

######  Theorem 1.

Each simple graph can be translated into a number-based string.

Figure 1: (a) A $(8,9)$-graph $H_{1}$ admits a _set-ordered graceful labeling_
$f$; (b)-(e) each graph $H_{k}$ admits a _set-ordered graceful coloring_
$g_{k}$ for $k=2,3,4,5$.

$\centering{\begin{split}T_{code}&=\left(\begin{array}[]{ccccccccc}x_{4}&x_{3}&x_{2}&x_{3}&x_{1}&x_{2}&x_{1}&x_{1}&x_{1}\\\
x_{4}y_{1}&x_{3}y_{1}&x_{2}y_{1}&x_{3}y_{2}&x_{1}y_{1}&x_{2}y_{3}&x_{1}y_{2}&x_{1}y_{3}&x_{1}y_{4}\\\
y_{1}&y_{1}&y_{1}&y_{2}&y_{1}&y_{3}&y_{2}&y_{3}&y_{4}\end{array}\right)\\\
&=\left(\begin{array}[]{ccccccccc}4&3&2&3&0&2&0&0&0\\\ 1&2&3&4&5&6&7&8&9\\\
5&5&5&7&5&8&7&8&9\end{array}\right)\end{split}}\@add@centering$ (2)

(5) The above (1)-(4) belong to topological coding, a mathematical subbranch
consisted of graph theory, algebra, probability and combinatorics, _etc._ Some
techniques of topological coding can be used in asymmetric cryptography and
anti-quantum computing.

(6) Colored graphs can be quickly converted into graphs admitting set-
colorings, which will produce more complex number-based strings for serving
information security. See examples shown in Fig.2, we have observed:

(a) A connected $(8,9)$-graph $G_{1}$ admits a _graceful intersection set-
coloring_ $f_{1}:V(G_{1})\rightarrow\mathcal{E}_{1}$ subject to a restrictive
set $R^{1}_{est}(1)$, such that each edge $uv\in E(G_{1})$ is colored with an
induced edge color set $f_{1}(uv)=f_{1}(u)\cap f_{1}(v)\neq\emptyset$, where
$\mathcal{E}_{1}$ is a hyperedge set holding
$[1,9]=\bigcup_{e_{i}\in\mathcal{E}_{1}}e_{i}$ true, so $G_{1}$ is the
intersected-graph of a hypergraph
$\mathcal{H}_{yper}=([1,9],\mathcal{E}_{1})$. Moreover, this set-coloring
$f_{1}$ is obtained by the set-ordered graceful labeling $f$ of the
$(8,9)$-graph $H_{1}$ shown in Fig.1.

(b) A connected $(8,9)$-graph $G_{2}$ admits an _odd-graceful intersection
set-coloring_ $f_{2}:V(G_{2})\rightarrow\mathcal{E}_{2}$ subject to a
restrictive set $R^{2}_{est}(2)$, such that the set-coloring $f_{2}$ is the
result of implementing an encryption function to the graceful intersection
set-coloring $f_{1}$. Each edge $xy\in E(G_{2})$ is colored with an induced
edge color set $f_{2}(xy)\supset f_{2}(x)\cap f_{2}(y)\neq\emptyset$, and
$a_{xy}=|a_{x}-a_{y}|$ for some $a_{xy}\in f_{2}(xy)$, $a_{x}\in f_{2}(x)$ and
$a_{y}\in f_{2}(y)$.

(c) A connected $(8,9)$-graph $G_{3}$ admits an _edge-magic total intersection
set-coloring_ $f_{3}$ from $V(G_{3})$ to $\mathcal{E}_{3}$ subject to a
restrictive set $R^{3}_{est}(2)$. Each edge $uv\in E(G_{3})$ is colored with
an induced color set $f_{3}(uv)\supset f_{3}(u)\cap f_{3}(v)\neq\emptyset$,
and $b_{uv}=|b_{u}-b_{v}|$ for some $b_{uv}\in f_{3}(uv)$, $b_{u}\in f_{3}(u)$
and $b_{v}\in f_{3}(v)$.

(d) A connected $(8,9)$-graph $G_{4}$ admits an _edge-magic total intersection
set-coloring_ $f_{4}$ from $V(G_{4})$ to $\mathcal{E}_{4}$ subject to a
restrictive set $R^{4}_{est}(3)$, and the set-coloring $f_{4}$ is induced by
the set-coloring $f_{3}$ under an encryption function.

Figure 2: Four graphs admitting set-colorings.

In this article, we, in order to make more complex number-based strings from
topological codes, will introduce set-colored graphs admitting set-colorings,
especially related with hypergraphs. Our set-colored graphs can be regarded as
a non-direct or partial visualization of hypergraphs, and moreover our set-
type Topcode-matrix can be considered as an algebraic visualization of
hypergraphs. We will discuss: connecting traditional colorings and set-
colorings, intersected-graphs of hypergraphs, graph operations on intersected-
graphs and hypergraphs, hypernetworks, three-dimensional matrices, set-colored
graph homomorphisms, set-colored graphic groups and set-colored graphic
lattices, and so on.

###  1.2 Terminology and notation

Standard terminology and notation of graphs and digraphs used here are cited
from [3], [4] and [7]. All graphs mentioned here are _simple_ (no _multiple-
edges_ and _loops_), unless otherwise stated, and _colorings_ and _labelings_
appeared in this article are on graphs [7]. We will employ the following
notation and terminology:

  1. $\bullet$

All non-negative integers are collected in the set $Z^{0}$, and all integers
are in the set $Z$, so the positive integer set $Z^{+}=Z^{0}\setminus\\{0\\}$.

  2. $\bullet$

A $(p,q)$-graph $G$ is a _data structure_ having $p$ vertices and $q$ edges,
and $G$ has no multiple edge and directed-edge, such that its own vertex set
$V(G)$ holds the cardinality $|V(G)|=p$ and its own edge set $E(G)$ holds the
cardinality $|E(G)|=q$. And $\overline{G}$ is the _complementary graph_ of the
$(p,q)$-graph $G$.

  3. $\bullet$

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

  4. $\bullet$

A vertex $x$ is called a _leaf_ if its degree $\textrm{deg}_{G}(x)=1$.

  5. $\bullet$

A symbol $[a,b]$ stands for an integer set $\\{a,a+1,a+2,\dots,b\\}$ with two
integers $a,b$ subject to $a<b$, and $[a,b]^{o}$ denotes an _odd-set_
$\\{a,a+2,\dots,b\\}$ with odd integers $a,b$ holding $1\leq a<b$ true.

  6. $\bullet$

Let $\Lambda$ be a set. The set of all subsets of $\Lambda$ is denoted as
$\Lambda^{2}=\\{X:~{}X\subseteq\Lambda\\}$, called the _power set_ of
$\Lambda$, 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\\}$, $\\{a,b,c,d\\}$, $\\{a,b,c,e\\}$,
$\\{a,c,d,e\\}$, $\\{b,c,d,e\\}$ and $\Lambda$. 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{\\}}$, the number of subsets is
$2^{4}-1=15$ in total.

  7. $\bullet$

A _sequence_ $\textbf{{d}}=(m_{1},m_{2},\dots,m_{n})=(m_{k})^{n}_{k=1}$
consists of positive integers $m_{1},m_{2},\dots,m_{n}$. If a graph $G$ has
its _degree-sequence_ ${\textrm{deg}}(G)=\textbf{{d}}$, then d is _graphical_
(see Lemma 2), and we call d _degree-sequence_ , each $m_{i}$ _degree
component_ , and $n=L_{\textrm{ength}}(\textbf{{d}})$ _length_ of d.

  8. $\bullet$

A tree is a connected and acyclic graph. A _caterpillar_ $T$ is a tree, after
removing all of leaves from the caterpillar $T$, the remainder is just a
_path_ ; a _lobster_ is tree, and the deletion of all leaves of the lobster
produces a caterpillar.

  9. $\bullet$

An isomorphism $G\cong H$ is a configuration identity on two graphs $G$ and
$H$, it has nothing to do with the colorings of these two graphs.

######  Lemma 2.

[4] (Erdös-Galia Theorem) A sequence $\textbf{{d}}=(m_{k})^{n}_{k=1}$ with
$m_{i}\geq m_{i+1}\geq 0$ to be the _degree-sequence_ of a $(p,q)$-graph graph
$G$ if and only if the sum $\sum^{n}_{i=1}m_{i}=2q$ and

$\sum^{k}_{i=1}m_{i}\leq k(k-1)+\sum^{n}_{j=k+1}\min\\{k,m_{j}\\},~{}1\leq
k\leq n$ (3)

###  1.3 Graph operations

_Graph operations are the soul of topological structures of graphs_.

####  1.3.1 Operations of adding or removing vertices and edges

Removing an edge $uv$ from a graph $G$ produces an _edge-removed graph_ ,
denoted as $G-uv$; and adding a new edge $xy\not\in E(G)$ to $G$ makes an
_edge-added graph_ , written as $G+xy$. Similarly, $G-w$ is a _vertex-removed
graph_ after deleting the vertex $w$ from $G$, and removing those edges with
one end to be this vertex $w$.

A _ve-added graph_ $G+\\{y,x_{1}y,x_{2}y,\dots,x_{s}y\\}$ is obtained by
adding a new vertex $y$ to a graph $G$, and join $y$ with vertices
$x_{1},x_{2},\dots,x_{s}$ of $G$ by new edges $x_{1}y,x_{2}y,\dots,x_{s}y$,
respectively. By those edge-removed graph $G-uv$ and vertex-removed graph
$G-w$, we have a _vertex-set-removed graph_ $G-S$ for a vertex proper subset
$S\subset V(G)$, as well as an _edge-set-removed graph_ $G-E^{*}$ for an edge
subset $E^{*}\subset E(G)$.

Particularly, an _edge-set-added graph_ $G+E\,^{\prime}$ is obtained by adding
each edge of an edge set $E\,^{\prime}\subset E(\overline{G})$ to a graph $G$,
where $\overline{G}$ is the complement of $G$.

####  1.3.2 Vertex-splitting and Vertex-coinciding operations

######  Definition 1.

[34, 32] Vertex-splitting operation. We split a vertex $u$ of a graph $G$ with
$\textrm{deg}(u)\geq 2$ into two vertices $u\,^{\prime}$ and
$u\,^{\prime\prime}$, such that $N(u)=N(u\,^{\prime})\cup
N(u\,^{\prime\prime})$ with $|N(u\,^{\prime})|\geq 1$,
$|N(u\,^{\prime\prime})|\geq 1$ and $N(u\,^{\prime})\cap
N(u\,^{\prime\prime})=\emptyset$, the resultant graph is denoted as $G\wedge
u$ (see an example shown in Fig.3 (a)$\rightarrow$(b)). Moreover, we select
randomly a proper subset $S$ of $V(G)$, and implement the vertex-splitting
operation to each vertex of $S$, the resultant graph is denoted as $G\wedge
S$.

Vertex-coinciding operation. (Also, called the _non-common neighbor vertex-
coinciding operation_) A vertex-coinciding operation is the _inverse_ of a
vertex-splitting operation, and vice versa. If two vertices $u\,^{\prime}$ and
$u\,^{\prime\prime}$ of a graph $H$ holds $|N(u\,^{\prime})|\geq 1$,
$|N(u\,^{\prime\prime})|\geq 1$ and $N(u\,^{\prime})\cap
N(u\,^{\prime\prime})=\emptyset$ true, we vertex-coincide $u\,^{\prime}$ and
$u\,^{\prime\prime}$ into one vertex $u=u\,^{\prime}\odot u\,^{\prime\prime}$,
such that $N(u)=N(u\,^{\prime})\cup N(u\,^{\prime\prime})$, the resultant
graph is denoted as $G=H(u\,^{\prime}\odot u\,^{\prime\prime})$, see a scheme
Fig.3 (b)$\rightarrow$(a). $\square$

Figure 3: The vertex-coinciding and the vertex-splitting operations defined in
Definition 1.

If two vertex-disjoint colored graphs $G$ and $H$ have $k$ pairs of vertices
with each pair of vertices is colored with the same color, then we, by the
vertex-coinciding operation defined in Definition 1, vertex-coincide each pair
of vertices from $G$ and $H$ into one, the resultant graph is denoted as
$\odot_{k}\langle G,H\rangle$ (or $G[\odot_{k}]H$, called _vertex-coincided
graph_ hereafter), and moreover we have two cardinalities

$|V(\odot_{k}\langle G,H\rangle)|=|V(G)|+|V(H)|-k,~{}|E(\odot_{k}\langle
G,H\rangle)|=|E(G)|+|E(H)|$

for the vertex set and edge set of $\odot_{k}\langle G,H\rangle$,
respectively. Clearly, the vertex-coincided graph $\odot_{k}\langle
G,H\rangle$ holds for the case of two vertex-disjoint uncolored graphs $G$ and
$H$ too.

######  Theorem 3.

[29] 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 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)$ (4)

then $G$ is _isomorphic_ to $H$, that is, $G\cong H$.

####  1.3.3 Operations of graph homomorphisms

Homomorphic encryption is a cryptographic technique based on computational
complexity theory of mathematical puzzles in cloud computing, e-commerce,
Internet of Things, mobile code _etc_. The homomorphic encrypted data is
processed to get an output, and the output is decrypted to get the same output
as the unencrypted raw data processed in the same way, in other word,
homomorphic encryption is required to achieve data security.

######  Definition 2.

[4] A _graph homomorphism_ $G\rightarrow H$ from a graph $G$ into another
graph $H$ is a mapping $f:V(G)\rightarrow V(H)$ such that $f(u)f(v)\in E(H)$
for each edge $uv\in E(G)$. $\square$

In Fig.3, there are three graph homomorphisms
$L_{i}\rightarrow_{\textrm{v-coin}}L_{i+1}$ for $i\in[1,3]$ obtained by the
vertex-coinciding operation defined in Definition 1, and we have three graph
anti-homomorphisms $L_{k}\rightarrow_{\textrm{v-split}}L_{k-1}$ for
$k\in[2,4]$ obtained by the vertex-splitting operation defined in Definition
1.

######  Definition 3.

[8] A graph homomorphism $\varphi:G\rightarrow H$ is called _faithful_ if
$\varphi(G)$ is an induced subgraph of $H$, and called _full_ if $uv\in E(G)$
if and only if $\varphi(u)\varphi(v)\in E(H)$. $\square$

######  Theorem 4.

[8] A faithful bijective graph homomorphism is an isomorphism, that is $G\cong
H$.

####  1.3.4 Edge-coinciding and edge-splitting operations

######  Definition 4.

[32] Edge-splitting operation. For an edge $uv$ of a graph $G$ with
$\textrm{deg}(u)\geq 2$ and $\textrm{deg}(v)\geq 2$, remove the edge $uv$ from
$G$ first; next vertex-split, respectively, two end vertices $u$ and $v$ of
the edge $uv$ into vertices $u\,^{\prime}$ and $u\,^{\prime\prime}$,
$v\,^{\prime}$ and $v\,^{\prime\prime}$; and then add a new edge
$u\,^{\prime}v\,^{\prime}$ to join $u\,^{\prime}$ and $v\,^{\prime}$ together,
and add another new edge $u\,^{\prime\prime}v\,^{\prime\prime}$ to join
$u\,^{\prime\prime}$ and $v\,^{\prime\prime}$ together, respectively. The
resultant graph is denoted as $G\wedge uv$, see Fig.4 (a)$\rightarrow$(c).

Here, it is allowed that $|N(u\,^{\prime})|=1$ and
$|N(v\,^{\prime\prime})|=1$, see Fig.4(a)$\rightarrow$(b), in this case, we
call the process of obtaining $G\wedge uv$ a _leaf-splitting operation_ , or a
_train-hook splitting operation_ , they are _particular cases_ of the edge-
splitting operation. The _inverse_ of a train-hook splitting operation is
called a _train-hook coinciding operation_.

Figure 4: The edge-coinciding and the edge-splitting operations defined in
Definition 4.

Edge-coinciding operation. For two edges $u\,^{\prime}v\,^{\prime}$ and
$u\,^{\prime\prime}v\,^{\prime\prime}$ of a graph $H$, if $N(u\,^{\prime})\cap
N(u\,^{\prime\prime})=\emptyset$ and $N(v\,^{\prime})\cap
N(v\,^{\prime\prime})=\emptyset$, we edge-coincide two edges
$u\,^{\prime}v\,^{\prime}$ and $u\,^{\prime\prime}v\,^{\prime\prime}$ into one
edge $uv=u\,^{\prime}v\,^{\prime}\ominus u\,^{\prime\prime}v\,^{\prime\prime}$
with $u=u\,^{\prime}\odot u\,^{\prime\prime}$ and $v=v\,^{\prime}\odot
v\,^{\prime\prime}$. The resultant graph $H(u\,^{\prime}v\,^{\prime}\ominus
u\,^{\prime\prime}v\,^{\prime\prime})$ is the result of doing the _edge-
coinciding operation_ to $H$, see Fig.4(c)$\rightarrow$(a). Also,
$H(u\,^{\prime}v\,^{\prime}\ominus u\,^{\prime\prime}v\,^{\prime\prime})$ is
the result of doing the _leaf-coinciding operation_ to $H$ as
$|N(u\,^{\prime\prime})|=1$ and $|N(v\,^{\prime})|=1$ (see
Fig.4(b)$\rightarrow$(a)). $\square$

###  1.4 Basic graph labelings and colorings

######  Definition 5.

[24] Suppose that a $(p,q)$-graph $G$ admits a mapping
$f:V(G)\rightarrow[m,n]$ or $f:V(G)\cup E(G)\rightarrow[m,n]$, we denoted the
vertex color set of colored vertices of $G$ as

$f(V(G))=\\{f(x):x\in V(G)\\}$ (5)

the edge color set of colored edges of the graph $G$ as

$f(E(G))=\\{f(uv):uv\in E(G)\\}$ (6)

and $f(V(G)\cup E(G))=f(V(G))\cup f(E(G))$. If $|f(V(G))|=p$, then $f$ is
called a _vertex labeling_ of $G$; when as cardinality $|f(E(G))|=q$, $f$ is
called an _edge labeling_ of $G$; and when cardinality $|f(V(G)\cup
E(G))|=p+q$, we call $f$ a _total labeling_. $\square$

######  Definition 6.

[7, 33, 39] Suppose that a connected $(p,q)$-graph $G$ admits a mapping
$\theta:V(G)\rightarrow\\{0,1,2,\dots\\}$. For each edge $xy\in E(G)$, the
induced edge color is defined as $\theta(xy)=|\theta(x)-\theta(y)|$. Write
vertex color set by $\theta(V(G))=\\{\theta(u):u\in V(G)\\}$, and edge color
set by $\theta(E(G))=\\{\theta(xy):xy\in E(G)\\}$. There are the following
constraint conditions:

B-1. $|\theta(V(G))|=p$;

B-2. $\theta(V(G))\subseteq[0,q]$, $\min\theta(V(G))=0$;

B-3. $\theta(V(G))\subset[0,2q-1]$, $\min\theta(V(G))=0$;

B-4. $\theta(E(G))=\\{\theta(xy):xy\in E(G)\\}=[1,q]$;

B-5. $\theta(E(G))=\\{\theta(xy):xy\in E(G)\\}=[1,2q-1]^{o}$;

B-6. $G$ is a bipartite graph with the bipartition $(X,Y)$ such that
$\max\\{\theta(x):x\in X\\}<\min\\{\theta(y):y\in Y\\}$
($\max\theta(X)<\min\theta(Y)$ for short);

B-7. $G$ is a tree having a perfect matching $M$ such that
$\theta(x)+\theta(y)=q$ for each matching edge $xy\in M$; and

B-8. $G$ is a tree having a perfect matching $M$ such that
$\theta(x)+\theta(y)=2q-1$ for each matching edge $xy\in M$.

Then:

  1. Blab-1.

A _graceful labeling_ $\theta$ satisfies B-1, B-2 and B-4 at the same time.

  2. Blab-2.

A _set-ordered graceful labeling_ $\theta$ holds B-1, B-2, B-4 and B-6 true.

  3. Blab-3.

A _strongly graceful labeling_ $\theta$ holds B-1, B-2, B-4 and B-7 true.

  4. Blab-4.

A _set-ordered strongly graceful labeling_ $\theta$ holds B-1, B-2, B-4, B-6
and B-7 true.

  5. Blab-5.

An _odd-graceful labeling_ $\theta$ holds B-1, B-3 and B-5 true.

  6. Blab-6.

A _set-ordered odd-graceful labeling_ $\theta$ abides B-1, B-3, B-5 and B-6.

  7. Blab-7.

A _strongly odd-graceful labeling_ $\theta$ holds B-1, B-3, B-5 and B-8,
simultaneously.

  8. Blab-8.

A _set-ordered strongly odd-graceful labeling_ $\theta$ holds B-1, B-3, B-5,
B-6 and B-8 true. $\square$

######  Definition 7.

[28] Suppose that a connected $(p,q)$-graph $G$ ($\neq K_{p}$) admits a total
coloring $f:V(G)\cup E(G)\rightarrow[1,M]$, and it is allowed $f(x)=f(y)$ for
some vertices $x,y\in V(G)$. If $|f(V(G))|<p$, and the edge color set

$f(E(G))=\\{f(uv)=|f(u)-f(v)|:uv\in E(G)\\}=[1,q]$

we call $f$ a _gracefully total coloring_. $\square$

######  Definition 8.

[26] Let $G$ be a bipartite and connected $(p,q)$-graph, then 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$. Let integers $a,k,m\geq 0$, $d\geq 1$ and $q\geq 1$. We
have two parameterized sets

$S_{m,k,a,d}=\\{k+ad,k+(a+1)d,\dots,k+(a+m)d\\},O_{2q-1,k,d}=\\{k+d,k+3d,\dots,k+(2q-1)d\\}$

with two _cardinalities_ $|S_{m,k,a,d}|=m+1$ and $|O_{2q-1,k,d}|=q$. If there
is a coloring

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

with integers $k\geq 0$ and $d\geq 1$, here it is allowed $f(x)=f(y)$ for some
distinct vertices $x,y\in V(G)$. Let $c$ be a non-negative integer.

  1. Ptol-1.

If $f(uv)=|f(u)-f(v)|$ for $uv\in E(G)$, $f(E(G))=S_{q-1,k,0,d}$ and
$f(V(G)\cup E(G))\subseteq S_{m,0,0,d}\cup S_{q-1,k,0,d}$, then $f$ is called
a _$(k,d)$ -gracefully total coloring_; and moreover $f$ is called a _$(k,d)$
-strongly gracefully total coloring_ if $f(x)+f(y)=k+(q-1)d$ for each matching
edge $xy$ of a matching $M$ of $G$.

  2. Ptol-2.

If $f(uv)=|f(u)-f(v)|$ for $uv\in E(G)$, $f(E(G))=O_{2q-1,k,d}$ and
$f(V(G)\cup E(G))\subseteq S_{m,0,0,d}\cup S_{2q-1,k,0,d}$, then $f$ is called
a _$(k,d)$ -odd-gracefully total coloring_; and moreover $f$ is called a
_strongly $(k,d)$-odd-gracefully total coloring_ if $f(x)+f(y)=k+(2q-1)d$ for
each matching edge $xy$ of a matching $M$ of $G$.

  3. Ptol-3.

If the 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 $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 a _$(k,d)$ -edge antimagic 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 $uv\in E(G)$, and
$f(E(G))=S_{q-1,k,0,d}$, then $f$ is called a _$(k,d)$ -harmonious 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~{}qd)$ for $uv\in E(G)$, and
$f(E(G))=O_{2q-1,k,d}$, then $f$ is called a _$(k,d)$ -odd-elegant total
coloring_.

  6. Ptol-6.

If $f(u)+f(uv)+f(v)=c$ for each edge $uv\in E(G)$, $f(E(G))=S_{q-1,k,0,d}$ and
$f(V(G))\subseteq S_{m,0,0,d}\cup S_{q-1,k,0,d}$, then $f$ is called a
_strongly edge-magic $(k,d)$-total coloring_; and moreover $f$ is called an
_edge-magic $(k,d)$-total coloring_ if $|f(E(G))|\leq q$ and
$f(u)+f(uv)+f(v)=c$ for $uv\in E(G)$.

  7. Ptol-7.

If $f(uv)+|f(u)-f(v)|=c$ for each edge $uv\in E(G)$ and
$f(E(G))=S_{q-1,k,0,d}$, then $f$ is called a _strongly edge-difference
$(k,d)$-total coloring_; and moreover $f$ is called an _edge-difference
$(k,d)$-total coloring_ if $|f(E(G))|\leq q$ and $f(uv)+|f(u)-f(v)|=c$ for
$uv\in E(G)$.

  8. Ptol-8.

If $|f(u)+f(v)-f(uv)|=c$ for each edge $uv\in E(G)$ and
$f(E(G))=S_{q-1,k,0,d}$, then $f$ is called a _strongly felicitous-difference
$(k,d)$-total coloring_; and moreover $f$ is called a _felicitous-difference
$(k,d)$-total coloring_ if $|f(E(G))|\leq q$ and $|f(u)+f(v)-f(uv)|=c$ for
$uv\in E(G)$.

  9. Ptol-9.

If $\big{|}|f(u)-f(v)|-f(uv)\big{|}=c$ for each edge $uv\in E(G)$ and
$f(E(G))=S_{q-1,k,0,d}$, then $f$ is called a _strongly graceful-difference
$(k,d)$-total coloring_; and $f$ is called a _graceful-difference
$(k,d)$-total coloring_ if $|f(E(G))|\leq q$ and
$\big{|}|f(u)-f(v)|-f(uv)\big{|}=c$ for $uv\in E(G)$. $\square$

######  Definition 9.

∗ If each $(p_{i},q_{i})$-graph $G_{i}$ admits a labeling $f_{i}$ such that
$f_{i}(x)\neq f_{i}(y)$ for distinct vertices $x,y\in V(G_{i})$, and each edge
color set

$f_{i}(E(G_{i}))=[1,2q_{i}-1]^{o}=\\{f_{i}(u_{j}v_{j})=|f_{i}(u_{j})-f_{i}(v_{j})|:~{}u_{j}v_{j}\in
E(G_{i})\\}$

and

$\bigcup^{m}_{i=1}f_{i}(V(G_{i}))=[0,M],~{}m\geq 2$

then we say that the _edge-odd-graceful graph base_
$\textbf{B}=(G_{1},G_{2},\dots,G_{m})$ admits an _edge-odd-graceful vertex-
matching labeling_ $F$ defined by $F=\uplus^{m}_{i=1}f_{i}$, and
$|f_{i}(V(G_{i}))|=p_{i}$ for $i\in[1,m]$, since each $f_{i}$ is a vertex
normal labeling (refer to Definition 5). $\square$

##  2 Set-type colorings and labelings

######  Definition 10.

[29] A _v-set e-proper $\varepsilon$-labeling_ (resp.
$\varepsilon$-_coloring_) of a $(p,q)$-graph $G$ is a mapping $f:V(G)\cup
E(G)\rightarrow\Omega$, where $\Omega$ consists of numbers and sets, such that
$f(u)$ is a set for each vertex $u\in V(G)$, $f(xy)$ is a number for each edge
$xy\in E(G)$, and the edge color set $f(E(G))$ satisfies a
$\varepsilon$-condition. $\square$

###  2.1 Set-colorings

######  Definition 11.

[33] Let $G$ be a $(p,q)$-graph, and $[0,p+q]^{2}$ be the set of subsets of
$[0,p+q]$.

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

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

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

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

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

######  Definition 12.

[29] Let $G$ be a $(p,q)$-graph, and let “$W$-type” be one of the existing
graph colorings and graph labelings of graph theory, and $[0,p+q]^{2}$ be the
set of subsets of $[0,p+q]$.

(i) A _$W$ -type ve-set-coloring_ $F$ of $G$ holds $F:V(G)\cup
E(G)\rightarrow[0,p+q]^{2}$ such that two sets $F(x)\neq F(y)$ for two
adjacent or incident elements $x,y\in V(G)\cup E(G)$.

(ii) A _$W$ -type v-set-coloring_ $F$ of $G$ holds
$F:V(G)\rightarrow[0,p+q]^{2}$ such that two sets $F(x)\neq F(y)$ for each
edge $xy\in E(G)$.

(iii) A _$W$ -type e-set-coloring_ $F$ of $G$ holds
$F:E(G)\rightarrow[0,p+q]^{2}$ such that two sets $F(uv)\neq F(uw)$ for two
adjacent edges $uv,uw\in E(G)$.

(iv) An _e-proper $W$-type v-set-coloring_ $(F,g)$ of $G$ is consisted of a
vertex set mapping $F:V(G)\rightarrow[0,p+q]^{2}$ and a proper edge mapping
$g:E(G)\rightarrow[a,b]$ such that two sets $F(x)\neq F(y)$ for each edge
$xy\in E(G)$ and two adjacent edge colors $g(uv)\neq g(uw)$ for two adjacent
edges $uv,uw\in E(G)$.

(v) A _v-proper $W$-type e-set-coloring_ $(F,f)$ of $G$ is consisted of an
edge set mapping $F:E(G)\rightarrow[0,p+q]^{2}$ and a proper vertex mapping
$f:V(G)\rightarrow[a,b]$ such that two sets $F(uv)\neq F(uw)$ for two adjacent
edges $uv,uw\in E(G)$ and two vertex colors $f(x)\neq f(y)$ for each edge
$xy\in E(G)$. $\square$

###  2.2 Set-labeling

######  Definition 13.

[32] A $(p,q)$-graph $G$ admits a set-labeling $F:V(G)\rightarrow[1,q]^{2}$
(resp. $[1,2q-1]^{2})$, and induces an edge set-color $F(uv)=F(u)\cap F(v)$
for each edge $uv\in E(G)$. If we select a _representative_ $a_{uv}\in F(uv)$
for each edge color set $F(uv)$ such that $\\{a_{uv}:~{}uv\in E(G)\\}=[1,q]$
(resp. $[1,2q-1]^{o}$), then $F$ is called a _graceful-intersection (resp. an
odd-graceful-intersection) total set-labeling_ of $G$. $\square$

######  Theorem 5.

[32] Each tree $T$ admits a _graceful-intersection (resp. an odd-graceful-
intersection) total set-labeling_ (see an example shown in Fig.5(a)).

######  Theorem 6.

[32] Each tree $T$ of $q$ edges admits a _regular rainbow intersection total
set-labeling_ based on a _regular rainbow set-sequence_
$\\{[1,k]\\}^{q}_{k=1}$ (see an example shown in Fig.5(b)).

Figure 5: Left tree admits a graceful-intersection total set-labeling for
illustrating Theorem 5; Right tree admits a regular rainbow intersection total
set-labeling for illustrating Theorem 6, cited from [32].

######  Definition 14.

[31] Let a $(p,q)$-graph $G$ with integers $q\geq p-1\geq 2$ admit a mapping
$F:X\rightarrow S$, where $X$ is a subset of $V(G)\cup E(G)$, $S$ is a subset
of power set $[0,pq]^{2}$, and let $R_{est}(m)=\\{c_{1},c_{2},\dots,c_{m}\\}$
be a constraint set. There are the following constraint conditions:

  1. (a)

$X=V(G)$;

  2. (b)

$X=E(G)$;

  3. (c)

$X=V(G)\cup E(G)$;

  4. (d)

$F(u)\not=F(v)$ if $uv\in E(G)$ (it may happen $F(u)\cap F(v)\neq\emptyset$);

  5. (e)

$F(uv)\not=F(uw)$ for any pair of adjacent edges $uv$ and $uw$ of $G$ (it may
happen $F(uv)\cap F(uw)\neq\emptyset$);

  6. (f)

$|F(V(G))|=p$, also, $F(x)\not=F(y)$ for any pair of vertices $x$ and $y$ of
$G$;

  7. (g)

$|F(E(G))|=q$, so $F(xy)\not=F(uv)$ for distinct edges $uv$ and $xy$ of $G$;

  8. (h)

A mapping $F\,^{\prime}:E(G)\rightarrow S$ is induced by $F$ subject to
$R_{est}(m)$, that is, each edge $uv\in E(G)$ is colored by the set
$F\,^{\prime}(uv)$ such that each $c\in F\,^{\prime}(uv)$ is generated by some
$a\in F(u)$, $b\in F(v)$ and one constraint or more constraints of
$R_{est}(m)$; and

  9. (i)

$|F\,^{\prime}(E(G))|=q$.

We call:

  1. (1)

$F$ a _strong vertex set-labeling_ of $G$ if both (a) and (f) hold true.

  2. (2)

$F$ a _strong edge-set-labeling_ of $G$ if both (b) and (g) hold true.

  3. (3)

$F\,^{\prime}$ a _strongly induced edge-set-labeling_ of $G$ if both (g) and
(h) hold true.

  4. (4)

$F$ a _strongly total set-labeling_ of $G$ if (c), (f) and (g) hold true.

  5. (5)

$(F,F\,^{\prime})$ a _strong set-coloring_ subject to $R_{est}(m)$ if (a),
(f), (h) and (i) hold true.

  1. (1’)

$F$ a _set-labeling_ of $G$ if it satisfies (a) and (d) simultaneously.

  2. (2’)

$F$ an _edge-set-labeling_ of $G$ if it satisfies (b) and (e) simultaneously.

  3. (3’)

$F$ a _total set-coloring_ of $G$ if it satisfies (c), (d) and (e)
simultaneously.

  4. (4’)

$(F,F\,^{\prime})$ a _set-coloring_ subject to $R_{est}(m)$ if (a), (d), (e)
and (h) are true simultaneously.

  1. (1”)

$F$ a _pseudo-vertex set-labeling_ of $G$ if it holds (a), but not (d).

  2. (2”)

$F$ a _pseudo-edge set-labeling_ of $G$ if it holds (b), but not (e).

  3. (3”)

$F$ a _pseudo-total set-coloring_ of $G$ if it holds (c), but not (d), or but
not (e), or not both (d) and (e). $\square$

Hereafter, we say “a set-coloring $(F,F\,^{\prime})$ s.t. $R_{est}(m)$”
defined in Definition 14, and say “a total set-coloring $\psi$ s.t.
$R_{est}(m)$” defined in Definition 14.

######  Definition 15.

∗ Let $v_{s}=\min\\{|F(x)|:x\in V(G)\\}$ and $v_{l}=\max\\{|F(y)|:y\in
V(G)\\}$ in Definition 14. $F$ is called an _$\alpha$ -uniformly vertex set-
labeling_ of $G$ if $v_{s}=v_{l}=\alpha$. Similarly, we have
$e_{s}=\min\\{|F\,^{\prime}(uv)|:~{}uv\in E(G)\\}$ and
$e_{l}=\max\\{|F\,^{\prime}(xy)|:~{}xy\in E(G)\\}$. $F\,^{\prime}$ is called a
_$\beta$ -uniformly edge set-labeling_ of $G$ if $e_{s}=e_{l}=\beta$. As
$\alpha=\beta=1$, $(F,F\,^{\prime})$ is just a popular labeling of graph
theory (Ref. [7]). For another group of parameters
$t_{s}=\min\\{|\psi(x)|:x\in V(G)\cup E(G)\\}$ and
$t_{l}=\max\\{|\psi(y)|:~{}y\in V(G)\cup E(G)\\}$ from Definition 14, and we
call $\psi$ a _$k$ -uniformly total set-coloring_ if $k=t_{s}=t_{l}$.
$\square$

######  Remark 1.

[29] For a (strongly) total set-labeling $\psi$ s.t. $R_{est}(m)$ defined in
Definition 14, we point out that three numbers $a\in\psi(u)$, $b\in\psi(v)$
and $c\in\psi(uv)$ satisfy a constraint $c_{i}\in R_{est}(m)$, by graph
colorings (resp. labelings), so $c_{i}$ holds one of the following constraint
conditions:

  1. (a)

$|a-b|=c$ induces _graceful labeling, or odd-graceful labeling, or odd-elegant
labeling, or vertex (distinguishing) coloring if $c\neq 0$_.

  2. (b)

$a+b+c=k$ induces _edge-magic total labeling_ for a constant $k$.

  3. (c)

$a+b=c$ ($\bmod~{}\eta$) induces _felicitous labeling, or harmonious
labeling_.

  4. (d)

$|a+b-c|=k$ induces _edge-magic graceful labeling_.

  5. (e)

$|a+b-\lambda c|=k$ induces _$(k,\lambda)$ -edge magic graceful labeling_, or
_$(k,\lambda)$ -odd-magic graceful labeling_.

  6. (f)

$a+b=k+\lambda c$ induces _$(k,\lambda)$ -magic total labeling_, or
_$(k,\lambda)$ -odd-magic total labeling_.

  7. (g)

$a\neq b$, $b\neq c$ and $c\neq a$ induce _total coloring, vertex
distinguishing total coloring, list-coloring_.

  8. (h)

$c\in\psi(uv)$ and $c\,^{\prime}\in\psi(uv^{\prime})$ hold $c\neq
c\,^{\prime}$ induces _edge coloring_.

  9. (i)

$a+b+c=k^{+}$, or $|a+b-c|=k^{-}$ induces _$(k^{+},k^{-})$ -couple edge-magic
total labeling_.

  10. (j)

$|a+b-c|=k_{1}$, or $|a+b-c|=k_{2}$ induces _$(k_{1},k_{2})$ -edge magic
graceful labeling_. $\parallel$

The _first example_ is about a _strong set-coloring_ $(F,F\,^{\prime})$ in
which the graphical structure is shown in Fig.6(a). We color each vertex $u$
with a set $F(u)$ such that $F(x)\not=F(y)$ for any pair of vertices $x,y$;
there are some $a\in F(u)$ and $b\in F(v)$ to hold the unique constraint
$|a-b|=c$ ($|R_{est}(m)|=1$) that induces the edge set $F\,^{\prime}(uv)$ with
$c\in F\,^{\prime}(uv)$ such that $F\,^{\prime}(uv)\not=F\,^{\prime}(xy)$ for
any pair of edges $uv$ and $xy$.

A _strongly total set-labeling_ $\psi$, as the _second example_ , is shown in
Fig.6(b) with $\psi(x)\not=\psi(y)$ for any two elements $x,y\in V(G)\cup
E(G)$, and for an edge $uv$, each $c\in\psi(uv)$ corresponds some
$a\in\psi(u)$ and $b\in\psi(v)$ such that at least one of two constraints
$|a-b|=c$ and $|a+b-c|=4$ holds true.

The _third example_ on a _strongly total set-labeling_ $\theta$ s.t.
$R^{*}_{est}(3)=\\{c_{1},c_{2},c_{3}\\}$ is shown in Fig.6(c), where

$c_{1}:~{}|a-b|=c$ for $c\in\theta(uv)$, $a\in\theta(u)$ and $b\in\theta(v)$;

$c_{2}:~{}|a\,^{\prime}+b\,^{\prime}-c\,^{\prime}|=4$ for
$c\,^{\prime}\in\theta(uv)$, $a\,^{\prime}\in\theta(u)$ and
$b\,^{\prime}\in\theta(v)$; and

$c_{3}:~{}a\,^{\prime\prime}+b\,^{\prime\prime}=c\,^{\prime\prime}~{}(\bmod~{}6)$
for $c\,^{\prime\prime}\in\theta(uv)$, $a\,^{\prime\prime}\in\theta(u)$ and
$b\,^{\prime\prime}\in\theta(v)$.

Thereby, each number $c\in\theta(uv)$ corresponds some numbers $a\in\theta(u)$
and $b\in\theta(v)$ such that they hold at least one of three constraints of
$R^{*}_{est}(3)$.

A _strongly total set-labeling_ $(\phi,\phi\,^{\prime})$ s.t. $R^{*}_{est}(3)$
shown in Fig.7 holds: $\theta(x)=\phi(x)$ for any $x\in V(G)$ and
$\theta(uv)\subseteq\phi\,^{\prime}(uv)$ for each edge $uv\in E(G)$, where
$\theta$ is defined in Fig.6(c). We say $(\phi,\phi\,^{\prime})$ to be the
_maximal strongly set-coloring_ s.t. $R^{*}_{est}(3)$.

Figure 6:  (a) A strong set-coloring $(F,F\,^{\prime})$; (b) a strongly total
set-labeling $\psi$; (c) another strongly total set-labeling $\theta$, cited
from [32].

######  Problem 1.

By Remark 1, suppose that a $(p,q)$-graph $G$ admits a set-labeling
$F:V(G)\rightarrow X$, so $F(V(G))=F(V_{=1})\cup F(V_{\geq 2})$ with
$V(G)=V_{=1}\cup V_{\geq 2}$ and $V_{=1}\cap V_{\geq 2}=\emptyset$, where

$F(V_{=1})=\\{|F(u)|=1:u\in V_{=1}\\},~{}F(V_{\geq 2})=\\{|F(w)|\geq 2:w\in
V_{\geq 2}\\}$

Find a $W$-type set-coloring $F$ for a graph $G$ holding
$|F(V_{=1})|\geq|g(V_{=1})|$ and $|F(V_{\geq 2})|\leq|g(V_{\geq 2})|$ for each
$W$-type set-labeling $g$ of the graph $G$, here $W$-type $\in\\{$graceful,
odd-graceful, elegant, odd-elegant, edge-magic total, _etc._ $\\}$.

Figure 7:  A strongly set-coloring $(\phi,\phi\,^{\prime})$ s.t.
$R^{*}_{est}(3)$, cited from [32].

Since each simple and connected $(p,q)$-graph $G$ can be vertex-split into a
tree of $q+1$ vertices, so we have:

######  Theorem 7.

[37] Each simple and connected $(p,q)$-graph $G$ can be vertex-split into a
tree $T$ of $q+1$ vertices by the vertex-splitting operation, and admits a _v-
set e-proper $W$-type coloring_ (refer to Definition 10 and Definition 11) if
$T$ admits a _$W$ -type coloring_.

######  Theorem 8.

[30] Every connected graph admits a _v-set e-proper graceful labeling_ defined
in Definition 11.

######  Theorem 9.

[27] Each simple and connected $(p,q)$-graph $G$ admits a _v-set e-proper
graceful coloring_ $f:V(G)\rightarrow[0,q]^{2}$ defined in Definition 10 and
Definition 11, such that each edge $uv$ is colored with an induced edge color
$f(uv)=|a_{u}-b_{v}|$ for some $a_{u}\in f(u)$ and $b_{v}\in f(v)$, and the
edge color set $f(E(G))$ $=\\{f(uv):uv\in E(G)\\}=[1,q]$.

######  Definition 16.

[27] A _strongly total set-labeling_ $\psi$ of a $(p,q)$-graph $G$ subject to
$Rs(m)$ is a mapping $\psi:V(G)\cup E(G)\rightarrow S$, where
$Rs(m)=\\{c_{1},c_{2},\dots,c_{m}\\}$ is a given constraint set and $S$ is a
set of subsets of the set $S\subseteq[0,pq]$, such that $\psi(x)\not=\psi(y)$
for any pair of elements $x,y\in V(G)\cup E(G)$, and each element of the label
set $\psi(uv)$ for $uv\in E(G)$ holds one constraint $c_{i}\in Rs(m)$.
$\square$

######  Theorem 10.

[27] Each simple, connected $(p,q)$-graph $G$ admits a strongly total set-
labeling $F$ such that

$\max\\{|F(x)|:~{}x\in V(G)\cup E(G)\\}=\Delta(G)+1$ (7)

and

$\max\\{c:~{}c\in F(x),x\in V(G)\cup E(G)\\}\in[1,p+q].$ (8)

######  Theorem 11.

[27] If a tree admits a super edge-magic total labeling, then it admits a
$2$-uniform strongly total set-coloring.

###  2.3 Connection of traditional colorings and set-colorings

Let $f$ be a proper edge coloring of a graph $G$, and $C_{ne}(x)=\\{f(xy):y\in
N(x)\\}$ be the set of colored edges indent with the vertex $x\in V(G)$. If
$C_{ne}(x)\neq C_{ne}(w)$ for any pair of distinct vertices $x,w\in V(G)$, we
then call $f$ _vertex distinguishing edge coloring_ of $G$.

######  Lemma 12.

[31] Each vertex distinguishing edge coloring of a graph $G$ induces a strong
set-labeling $F$ with

$\Delta(G)=\max\\{|F(x)|:~{}x\in V(G)\\},\quad\delta(G)=\min\\{|F(x)|:~{}x\in
V(G)\\}.$ (9)

######  Theorem 13.

[31] If a set-labeling $F$ of a graph $G$ holds:
$|F(x)|\geq\textrm{deg}_{G}(x)$ for each vertex $x\in V(G)$, and $|F(u)\cap
F(v)|=1$ for each edge $uv\in E(G)$, and $F(u)\cap F(v)\neq F(u)\cap F(w)$ for
two adjacent edges $uv,uw\in E(G)$, then $F$ induces a proper edge-coloring of
$G$.

######  Definition 17.

[31] An _adjacent $1$-common edge-coloring_ $f$ of $G$ satisfies: $f$ is a
proper edge-coloring,

$|\\{f(ux_{i}):x_{i}\in N(u)\\}\cap\\{f(vy_{j}):y_{j}\in N(v)\\}|=1$

for each edge $uv\in E(G)$, and

$\\{f(ux_{i}):x_{i}\in N(u)\\}\cap\\{f(vy_{j}):y_{j}\in
N(v)\\}\neq\\{f(ux_{i}):x_{i}\in N(u)\\}\cap\\{f(wz_{k}):z_{k}\in N(w)\\}$

for any pair of adjacent edges $uv,uw\in E(G)$. $\square$

By Theorem 13 we obtain the following result:

######  Theorem 14.

[31] A set-labeling $F$ of a graph $G$ holds: $|F(x)|\geq\textrm{deg}_{G}(x)$
for each vertex $x\in V(G)$, and $|F(u)\cap F(v)|=1$ for each edge $uv\in
E(G)$, and $F(u)\cap F(v)\neq F(u)\cap F(w)$ for any pair of adjacent edges
$uv,uw\in E(G)$, then $F$ induces an adjacent $1$-common edge-coloring of $G$.

We can define a new parameter
$\chi\,^{\prime}_{set}(G)=\min_{f}\max\\{f(uv):~{}uv\in E(G)\\}$ over all
adjacent $1$-common edge-colorings $f$ of $G$. It is not hard to show that
$\chi\,^{\prime}_{set}(K_{n})=\frac{1}{2}n(n-1)$, and

$\chi\,^{\prime}_{set}(G)=\max\\{\textrm{deg}_{G}(u)+\textrm{deg}_{G}(v)-1:~{}uv\in
E(G)\\}$

if $G$ is a tree.

A vertex $w$ of a graph $G_{k}$ admitting a set-labeling
$F_{k}:V(G_{k})\rightarrow S$, where $S$ is a set of subsets of $[1,M]$, has
the family of $F(w_{1}),F(w_{2}),\dots,F(w_{M(w)})$ with
$M(w)=\textrm{deg}_{G_{k}}(w)$ and $w_{i}\in N(w)$, which satisfies
$|X|\leq\big{|}\bigcup_{i\in X}F(w_{i})\big{|}$ for every subset
$X\subset[1,M(w)]$. Excellently, according to the famous Philip Hall’s theorem
(1935, see Bollobás’ book [5]), there exists a _system of distinct
representative_ $R_{ep}(w)=\\{z_{1},z_{2},\dots,z_{M(w)}\\}$ with pairwise
distinct $z_{j}\in F(w_{j})$ of the family for $j\in[1,M(w]$.

As an example, we take an integer set $X=[1,6]$, and let
$A_{1}=A_{2}=\\{1,2\\}$, $A_{3}=\\{2,3\\}$ and $A_{4}=\\{1,4,5,6\\}$. For
$\mathcal{A}=\\{A_{1},A_{2},A_{3},A_{4}\\}$, the set $[1,4]$ is a system of
distinct representative. If we have a new family $\mathcal{B}$ by adding
another set $A_{5}=\\{2,3\\}$ to $\mathcal{A}$, then it is impossible to find
a _transversal_ for the family $\mathcal{B}$. Notice that
$S=\\{1,2,3,5\\}\subset[1,5]$. But $|S|>\big{|}\bigcup_{i\in
S}A_{i}\big{|}=|\\{1,2,3\\}|=3$. We show a result:

######  Theorem 15.

[31] Suppose that a graph $G_{1}$ admits a set-labeling
$F_{1}:V(G_{1})\rightarrow S$, where $S$ is a set of subsets of $[1,M]$, and
$F_{1}(u)\cap F_{1}(v)\neq\emptyset$ for each edge $uv\in E(G_{1})$. And there
are graphs $G_{k}=G_{k-1}-u_{k-1}$ for $u_{k-1}\in V(G_{k-1})$ with $k\geq 2$,
and for each graph $G_{k}$ with $k\in[2,|G_{1}|-2]$, there exists a set-
labeling $F_{k}(x)=F_{k-1}(x)$ if $x\not\in N(u_{k-1})$, and
$F_{k}(y)=F_{k-1}(y)\setminus[F_{k-1}(y)\cap F_{k-1}(u_{k-1})]$ if $y\in
N(u_{k-1})$, as well as $F_{k}(u)\cap F_{k}(v)\neq\emptyset$ for each edge
$uv\in E(G_{k})$. If two _systems of distinct representatives_ for each edge
$uv\in E(G_{k})$ holds $|R_{ep}(u)\cap R_{ep}(v)|=1$ with $k\in[2,|G_{1}|-2]$,
then $F_{1}$ induces a proper edge-coloring of $G_{1}$.

######  Definition 18.

∗ A vertex set-labeling $F$ of a $(p,q)$-graph $G$ is a mapping
$F:V(G)\rightarrow S$ such that $F(u)\not=F(v)$ for any pair of vertices $u,v$
of $G$, where $S$ is a set of subsets of the set $[0,pq]$, and $F(x)\not=F(y)$
for any pair of vertices $x$ and $y$ of $G$. An edge set-labeling
$F\,^{\prime}$ induced by the vertex set-labeling $F$ is subjected to a
constraint set $Rs(m)=\\{c_{1},c_{2},\dots,c_{m}\\}$ based on $F$, such that
the edge set-labeling $F\,^{\prime}(uv)$ of each edge $uv\in E(G)$ holds
$Rs(m)$ true, and $F\,^{\prime}(xy)\not=F\,^{\prime}(uv)$ for any pair of
distinct edges $uv$ and $xy$ of $G$. We call $(F,F\,^{\prime})$ a _strong set-
coloring_ subject to $Rs(m)$, $F\,^{\prime}$ _induced edge-set-labeling_ over
$F$. $\square$

A connected $(p,q)$-graph $G$ can be vertex-split into trees
$T_{1},T_{2},\dots,T_{m}$ of $q+1$ vertices. Suppose that each tree $T_{i}$
admits different proper total colorings $f_{i,1},f_{i,2},\dots,f_{i,a_{i}}$
with $i\in[1,m]$, and let $T_{i,j}$ be the tree obtained by coloring totally
the vertices and edges of the each tree $T_{i}$ with the proper total coloring
$f_{i,j}$ with $j\in[1,a_{i}]$ and $i\in[1,m]$. So, vertex-coinciding each
colored tree $T_{i,j}$ produces the original connected $(p,q)$-graph $G$
admitting a total coloring $F_{i,j}$, there are the following cases:

(i) $F_{i,j}(uv)$ for each edge $uv\in E(G)$ is a number, however it may
happen $F_{i,j}(uv)=F_{i,j}(uw)$ for $v,w\in N(u)$ for some vertex $u\in
V(G)$;

(ii) $F_{i,j}(x)$ for each vertex $x\in V(G)$ is a set, since it may happen
that $x$ is the result of vertex-coinciding two or more vertices of the tree
$T_{i,j}$, that is, $x=x_{i,1}\odot x_{i,2}\odot\cdots\odot x_{i,b}$ for
$x_{i,s}\in V(T_{i,j})$.

(iii) Good-property: $F_{i,j}(V(G)\cup E(G))=[1,\chi\,^{\prime\prime}(G)]$,
where $\chi\,^{\prime\prime}(G)$ is the total chromatic number of the
connected $(p,q)$-graph $G$; $|F_{i,j}(y)|=1$ for each vertex $y\in V(G)$; and
$F_{i,j}(xy)\neq F_{i,j}(xz)$ for $y,z\in N(x)$ for each vertex $x\in V(G)$.

Let $V_{\textrm{sp-co}}(G)=\\{T_{i,j}:j\in[1,a_{i}],i\in[1,m]\\}$. Each
totally colored tree $T_{i,j}\in V_{\textrm{sp-co}}(G)$ is _colored graph
homomorphism_ to $G$, also, $T_{i,j}\rightarrow G$.

######  Problem 2.

Find totally colored trees $T_{i,j}$ from the set $V_{\textrm{sp-co}}(G)$,
such that $T_{i,j}$ is colored graph homomorphism to $G$ admitting a total
coloring $F_{i,j}$, which has the Good-property.

###  2.4 Researching topics of set-colorings and set-labelings

Various vertex distinguishing colorings of graph colorings of graph theory are
not difficult to induce some set-colorings and set-labelings defined here.
However, it seems to be not easy to induce graph colorings and graph labelings
by means of given set-colorings and set-labelings, although set-colorings and
set-labelings are useful in designing complex number-based strings for
asymmetric cryptography. We present the following topics:

  1. Topic 1\.

We change the condition in Definition 17 by the following one:

$\\{f(uu_{i}):u_{i}\in N(u)\\}\cap\\{f(vv_{j}):v_{j}\in
N(v)\\}\neq\\{f(xx_{i}):x_{i}\in N(x)\\}\cap\\{f(yy_{j}):y_{j}\in N(y)\\}$

for any two edges $uv,xy\in E(G)$ and keep other conditions in original, then
we obtain the _vertex 1-common-edge-coloring_ of a graph $G$. By the
distinguishing total colorings introduced in [35], we can define a _set-set-
coloring_ $F^{*}$ of a graph $G$ such that each vertex $u$ of $G$ is colored
by a set $F^{*}(u)$ consisted of sets $F_{i}(u)$ with $i\in[1,u_{k}]$.
Studying set-set-colorings of graphs is a new topic in hypergraphs.

  2. Topic 2\.

In [25], Sudev defined a set-coloring $(F,F\,^{\prime})$ of a graph $H$ such
that $F\,^{\prime}(uv)=F\,^{\prime}(xy)$ for any pair of edges $uv$ and $xy$
of $H$. It may be interesting to find graphs admitting the set-coloring
$(F,F\,^{\prime})$ mentioned above. Obviously, finding such graphs is a
challenge with many unknown parts.

  3. Topic 3\.

We focus on particular set-colorings and set-labelings of a graph $G$, such
as:

(i) No two edges $uv$ and $xy$ of $G$ hold
$|F\,^{\prime}(uv)|=|F\,^{\prime}(xy)|$ in a set-coloring $(F,F\,^{\prime})$
of $G$.

(ii) No two vertices $x$ and $y$ of $G$ hold $|F(x)|=|F(y)|$ in a set-labeling
$F$ of $G$.

(iii) No two elements $\alpha$ and $\beta$ of $V(G)\cup E(G)$ hold
$|F(\alpha)|=|F(\beta)|$ in a total set-coloring $F$.

(iv) A graph $G$ admits a set-coloring $(F,F\,^{\prime})$ subject to two
different constraint sets $Rs(m_{1})$ and $Rs(m_{2})$, respectively, or more
constraint sets. Conversely, $G$ admits two different set-colorings
$(F_{1},F\,^{\prime}_{1})$ and $(F_{2},F\,^{\prime}_{2})$ subject to a
constraint set $Rs(m)$ only.

  4. Topic 4\.

For a simple and connected graph $G$ admitting adjacent $1$-common edge-
colorings, determine $\chi\,^{\prime}_{set}(G)=\min_{f}\max\\{f(uv):~{}uv\in
E(G)\\}$ over all adjacent $1$-common edge-colorings of $G$ (refer to
Definition 17). It may be possible to consider $\chi\,^{\prime}_{set}(G)$ if
$G$ is a planar graph.

  5. Topic 5\.

The set-labelings and set-colorings defined in Definition 14 can be optimal in
this way: $S$ is the power set of an integer set
$\\{0,1,\dots,\chi_{\epsilon}(G)\\}=[0,\chi_{\epsilon}(G)]$ such that $G$
admits a set-labeling or a set-coloring defined in Definition 14, and but $S$
is not the power set of any integer set $[0,M]$ if $M<\chi_{\epsilon}(G)$,
where $\epsilon$ is a combinatoric of some conditions (a)-(i) stated in
Definition 14, and $\chi_{\epsilon}(G)$ is called an _$\epsilon$ -chromatic
number_ of $G$. For example, $\epsilon=\\{$(a), (d)$\\}$ if only about a _set-
labeling_ of $G$. So, we determine the $\epsilon$-chromatic number
$\chi_{\epsilon}(G)$ for a fixed $\epsilon$. As known, there are many long-
standing conjectures on graph coloring and graph labelings, so we believe
there are new open problems on the set-colorings and set-labelings defined in
Definition 14.

  6. Topic 6\.

We define mixed set-colorings and set-labelings of graphs in order to design
more complicated topological codes.

  7. Topic 7\.

Construction of lager scale of graphs admitting set-colorings and set-
labelings by smaller size of graphs admitting the same type of set-colorings
and set-labelings. Trees are first object for constructing such graphs.

  8. Topic 8\.

Notice that a new-type of matrices defined by set-colorings and set-labelings
of graphs goes into sight of our research, although we do not know more
properties about such matrices, called _set-matrices_. Thereby, we define a
set-matrix for a simple $(p,q)$-graph $G$ admitting an edge-set-labeling
$F\,^{\prime}$ as: $S_{e}(G)=(A_{ij})_{q\times q}$ such that

$A_{ij}=\left\\{\begin{array}[]{ll}F\,^{\prime}(u_{i}u_{j}),&u_{i}u_{j}\in
E(G);\\\ \emptyset,&\textrm{otherwise}.\end{array}\right.$

Suppose that a simple $(p,q)$-graph $G$ admits a set-labeling $F$ defined on
its vertex set $V(G)$; we define an operation “$(\bullet)$” on two sets, and
then define a set-matrix $S_{v}(G)=(B_{ij})_{q\times q}$ of $G$ based on the
set-labeling $F$ as:

$B_{ij}=\left\\{\begin{array}[]{ll}F(u_{i})(\bullet)F(u_{j}),&u_{i}u_{j}\in
E(G);\\\ \emptyset,&\textrm{otherwise}.\end{array}\right.$

where the result of $F(u_{i})(\bullet)F(u_{j})$ is still a set.

##  3 Set-colorings related with hypergraphs

As known, hypergraphs have been applied in many scientific areas, such as
privacy protection, information database _etc_. We, in this subsection, will
use some graph operations introduced in Section 1 for observing and describing
hypergraphs.

###  3.1 Basic concepts of hypergraphs

In the following discussion, “undirected hypergraph” is called “hypergraph”,
since our study is not related with directed hypergraphs.

######  Definition 19.

[12] A _hypergraph_ $\mathcal{E}$ is a family of distinct non-empty subsets
$e_{1},e_{2}$, $\dots$, $e_{n}$ of a finite set $\Lambda$, and satisfies:

(i) each element $e\in\mathcal{E}$ holds $e\neq\emptyset$ true, and is called
a _hyperedge_ ;

(ii) $\Lambda=\bigcup_{e\in\mathcal{E}}e$, where each element of $\Lambda$ is
called a _vertex_ , and the cardinality $|\Lambda|$ is the _order_ of the
hypergraph.

We use $\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$ to stand for a hypergraph
with its own _hyperedge set_ $\mathcal{E}$ defined on _vertex set_ $\Lambda$,
and the cardinality $|\mathcal{E}|$ is the _size_ of the hypergraph
$\mathcal{H}_{yper}$. $\square$

Fig.8 shows us a hypergraph $\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$ with
its own vertex set $\Lambda=[1,15]$ and its own hyperedge set
$\mathcal{E}=\\{e_{1},e_{2},e_{3},e_{4}\\}$. There are terminology and
notation of hypergraphs as follows:

  1. $\bullet$

[12] An _ear_ $e\in\mathcal{E}$ holds (i) $e\cap e\,^{\prime}=\emptyset$ for
any hyperedge $e\,^{\prime}\in\mathcal{E}\setminus\\{e\\}$; or (ii) there
exists another hyperedge $e^{*}\in\mathcal{E}$, such that each vertex of
$e\setminus e^{*}$ is not in any element of $\mathcal{E}\setminus\\{e\\}$. An
_isolated vertex_ $x\in\Lambda$ belongs to a unique hyperedge
$e_{i}\in\mathcal{E}$, such that $x\not\in e_{j}\in\mathcal{E}$ if $i\neq j$.

  2. $\bullet$

If each _hyperedge_ $e\in\mathcal{E}$ has its cardinality $|e|=r$, then we
call $\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$ _$r$ -uniform hypergraph_.

  3. $\bullet$

[12] A hyperedge set $\mathcal{E}$ is _irreducible_ if each hyperedge
$e\in\mathcal{E}$ does not hold $e\subseteq e\,^{\prime}$ for any hyperedge
$e\,^{\prime}\in\mathcal{E}$.

  4. $\bullet$

A _perfect hypermatching_ of a hypergraph $\mathcal{H}_{yper}$ is a collection
of hyperedges $M_{1},M_{2},\dots,M_{m}$ $\subseteq\mathcal{E}$ in a hypergraph
$\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$ such that $M_{i}\cap
M_{j}=\emptyset$ for $i\neq j$ and $\bigcup^{m}_{i=1}M_{i}=\Lambda$.

  5. $\bullet$

[12] A _partial hypergraph_ of a hypergraph
$\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$ has its own hyperedge set
$\mathcal{E}^{*}\subset\mathcal{E}$.

  6. $\bullet$

[12] If a hyperedge set $\mathcal{E}=\bigcup^{m}_{j=1}\mathcal{E}_{j}$ holds
$\mathcal{E}_{i}\cap\mathcal{E}_{j}=\emptyset$, and each hyperedge
$e\in\mathcal{E}$ belongs to one $\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 called a
_decomposition_ of $\mathcal{E}$.

  7. $\bullet$

[12] The _Graham reduction_ of a hyperedge set $\mathcal{E}$ is obtained by
doing repeatedly GR-1: delete a vertex $x$ if $x$ is an isolated vertex; GR-2:
delete $e_{i}$ if $e_{i}\subseteq e_{j}$ for $i\neq j$.

  8. $\bullet$

A hypergraph $\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$ is called a _reduced
hypergraph_ , or a _simple hypergraph_ if its hyperedge set $\mathcal{E}$ is a
result of Graham reduction.

  9. $\bullet$

Suppose that $x_{i_{1}},x_{i_{2}},\dots,x_{i_{n}}$ are a permutation of
vertices of a hypergraph $\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$, where
$x_{i_{j}}\in e_{j-1}\cap e_{j}$, $x_{i_{n-1}}\in e_{n-1}\cap e_{n}$ and
$x_{i_{n}}\in e_{n}\cap e_{1}$, then a _hyperpath_ is defined as
$\mathcal{P}=e_{1}e_{2}\cdots e_{n}$, and a _hypercycle_ is defined as
$\mathcal{C}=e_{1}e_{2}\cdots e_{n}e_{1}$, and moreover
$\mathcal{C}=e_{1}e_{2}\cdots e_{n}e_{1}$ is a _Hamilton hypercycle_ if
$n=|\Lambda|$.

###  3.2 Intersected-graphs of hypergraphs

######  Definition 20.

∗ Let $\mathcal{E}$ be a _hyperedge set_ defined on $\Lambda$ (refer to
Definition 19). Suppose that a $(p,q)$-graph $H$ admits a proper set-labeling
$F:V(H)\rightarrow\mathcal{E}$ with $F(x)\neq F(y)$ for each edge $xy\in
E(G)$, and $R_{est}(m+1)=\\{c_{0},c_{1},c_{2}$, $\dots$,
$c_{m}\\}=\\{c_{k}\\}^{m}_{k=1}$ with $m\geq 0$ is a _constraint set_ , such
that each edge $uv$ of $E(H)$ is colored with an induced edge color set
$F(uv)$ and

(i) $c_{0}$ holds $F(uv)\supseteq F(u)\cap F(v)\neq\emptyset$ true.

(ii) There is a function $\varphi_{k}$ for some $k\in[1,m]$, we have three
numbers $c_{uv}\in F(uv)$, $a_{u}\in F(u)$ and $b_{v}\in F(v)$ holding the
$k$th constraint $c_{k}:\varphi_{k}(a_{u},c_{uv},b_{v})=0$.

If each pair of hyperedges $e,e\,^{\prime}\in\mathcal{E}$ holding $|e\cap
e\,^{\prime}|\geq 1$ corresponds an edge $xy\in E(H)$, such that $F(x)=e$ and
$F(y)=e\,^{\prime}$, then $H$ is called _intersected-graph_ of the hypergraph
$\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$ s.t. $R_{est}(m+1)$. $\square$

Figure 8: An example from a $8$-uniform hypergraph $H_{yper}$ to an
intersected-graph $G$ admitting a set-coloring s.t.$R_{set}(1)$, where (a)
Venn’s four-set diagram using four ellipses.

Obviously, each one of path, cycle and Hamilton cycle in the intersected-graph
$H$ of a hypergraph $\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$ differs from
that of the hypergraph $\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$.

######  Definition 21.

∗ In the intersected-graph $H$ of a hypergraph
$\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$ defined in Definition 20, by means
of terminology of graphs, we define:

  1. Ter-1.

Each hyperedge $e\in\mathcal{E}$ has its own _hyperedge degree_
$\textrm{deg}_{\mathcal{E}}(e)=\textrm{deg}_{H}(x)$ if $F(x)=e$ for $x\in
V(H)$.

  2. Ter-2.

The _hyperedge degree sequence_
$\\{\textrm{deg}_{\mathcal{E}}(e_{1}),\textrm{deg}_{\mathcal{E}}(e_{2}),\dots,\textrm{deg}_{\mathcal{E}}(e_{n})\\}$
with $e_{i}\in\mathcal{E}$ satisfies Erdös-Galia Theorem. In fact, each
hyperedge degree

$\textrm{deg}_{\mathcal{E}}(e_{i})=|\\{e_{j}:e_{i}\cap
e_{j}\neq\emptyset,e_{j}\in\mathcal{E}\setminus\\{e_{i}\\}\\}|$ (10)

  3. Ter-3.

If each hyperedge $e\in\mathcal{E}$ has its own hyperedge degree to be even,
then $\mathcal{E}$ is called an _Euler’s hyperedge set_.

  4. Ter-4.

A _hyperedge path_ $\mathcal{P}$ in a hypergraph
$\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$ is

$\mathcal{P}(e_{1},e_{m})=e_{1}e_{2}\cdots e_{m}=e_{1}(e_{1}\cap
e_{2})e_{2}(e_{2}\cap e_{3})\cdots(e_{m-1}\cap e_{m})e_{m}$ (11)

with hyperedge intersections $e_{i}\cap e_{i+1}\neq\emptyset$ for
$i\in[1,m-1]$, and each hyperedge $e_{i}$ is not an ear for $i\in[2,m-1]$.
Moreover, the hyperedge path $\mathcal{P}$ is _pure_ if $e_{1}$ and $e_{m}$
are not ears of $\mathcal{E}$. If hyperedge intersections $|e_{i}\cap
e_{i+1}|\geq r$ for $i\in[1,m-1]$, we call $\mathcal{P}$ $r$-_uniform
hyperedge path_.

  5. Ter-5.

If each pair of hyperedges $e,e\,^{\prime}$ of $\mathcal{E}$ corresponds a
hyperedge path $\mathcal{P}(e,e\,^{\prime})$, then
$\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$ is a _hyperedge connected
hypergraph_ , correspondingly, and its intersected-graph is _hyperedge
connected_.

  6. Ter-6.

A _hyperedge cycle_ of a hypergraph $\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$
is

$\mathcal{C}_{m}=e_{1}e_{2}\cdots e_{m}e_{1}=e_{1}(e_{1}\cap
e_{2})e_{2}(e_{2}\cap e_{3})\cdots(e_{m-1}\cap e_{m})e_{m}(e_{m}\cap
e_{1})e_{1}$ (12)

with hyperedge intersections $e_{i}\cap e_{i+1}\neq\emptyset$ for
$i\in[1,m-1]$ and $e_{m}\cap e_{1}\neq\emptyset$, as well as each $e_{j}$ with
$j\in[1,m]$ is not an ear of $\mathcal{E}$. Furthermore, $\mathcal{C}_{m}$ is
called a _hyperedge Hamilton cycle_ if $m=|\mathcal{E}|$, and we call
$\mathcal{C}_{m}$ $r$-_uniform hyperedge cycle_ if $|e_{i}\cap e_{i+1}|\geq r$
for $i\in[1,m-1]$ and $|e_{m}\cap e_{1}|\geq r$. By the way, if
$\Lambda=\\{x_{1},x_{2},\dots,x_{m}\\}$, and $x_{i}\in e_{i}\cap e_{i+1}$ with
$i\in[1,m-1]$, $x_{m}\in e_{m}\cap e_{1}$, we call $\mathcal{C}_{m}$ a
_hypervertex Hamilton cycle_.

######  Theorem 16.

∗ If the intersected-graph $G$ of a hypergraph
$\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$ contains a Hamilton cycle, then the
hypergraph $\mathcal{H}_{yper}$ contains a _hyperedge Hamilton cycle_.

  7. Ter-7.

If the intersected-graph $H$ is bipartite, then we have the hyperedge set
$\mathcal{E}=X_{\mathcal{E}}\cup Y_{\mathcal{E}}$ with $X_{\mathcal{E}}\cap
Y_{\mathcal{E}}=\emptyset$, such that any two hyperedges $e,e\,^{\prime}\in
X_{\mathcal{E}}$ (resp. $e,e\,^{\prime}\in Y_{\mathcal{E}}$) satisfies $e\cap
e\,^{\prime}=\emptyset$.

  8. Ter-8.

A _spanning hypertree_ $\mathcal{T}$ of the intersected-graph $H$ holds that
each vertex color set $F(x)$ is not an ear of $\mathcal{E}$ if $x\not\in
L(\mathcal{T})$, where $L(\mathcal{T})$ is the set of all leaves of
$\mathcal{T}$, and $\mathcal{T}$ contains no hyperedge cycle.

  9. Ter-9.

The intersected-graph $H$ admits a proper vertex coloring
$\theta:V(H)\rightarrow[1,\chi(H)]$, then the hyperedge set $\mathcal{E}$
admits a proper hyperedge coloring $\theta:\mathcal{E}\rightarrow[1,\chi(H)]$
such that $\theta(e)$ differs from $\theta(e\,^{\prime})$ if $e\,^{\prime}\cap
e\neq\emptyset$ for any pair of sets $e,e\,^{\prime}\in\mathcal{E}$.

  10. Ter-10.

If the intersected-graph $H$ is connected and the hyperedge set $\mathcal{E}$
contains no ear, so the _diameter_ $D(H)$ of $H$ is defined by

$\max\\{d(x,y):d(x,y)\textrm{ is the length of a shortest path between $x$ and
$y$ in }H\\}$

then the _hyperdiameter_ $D(\mathcal{E})$ of the hyperedge set $\mathcal{E}$
is defined by $D(\mathcal{E})=D(H)$.

  11. Ter-11.

A _hyperedge dominating set_ $\mathcal{E}_{domi}$ is a proper subset of the
hyperedge set $\mathcal{E}$ and holds: Each hyperedge
$e\in\mathcal{E}\setminus\mathcal{E}_{domi}$ corresponds some hyperedge
$e^{*}\in\mathcal{E}_{domi}$ such that $e\cap e^{*}\neq\emptyset$.

  12. Ter-12.

The _dual_ $\mathcal{H}_{dual}$ of a hypergraph
$\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$ is also a hypergraph having its own
vertex set $\Lambda_{dual}=\mathcal{E}=\\{e_{1},e_{2},\dots,e_{n}\\}$ and its
own hyperedge set $\mathcal{E}_{dual}=\\{X_{j}\\}^{n}_{j=1}$ with
$X_{j}=\\{e_{i}:x_{j}\in e_{i}\\}$ and $n=|\mathcal{E}|$. Clearly, the dual of
the hypergraph $\mathcal{H}_{dual}$ is just the original hypergraph
$\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$. $\square$

######  Example 1.

In Fig.8, we can see:

(a) A $8$-uniform hypergraph $\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$ with
its vertex set $\Lambda=[1,15]$ and hyperedge set
$\mathcal{E}=\\{e_{1},e_{2},e_{3},e_{4}\\}$;

(b) the intersected-graph $G$ of the $8$-uniform hypergraph
$\mathcal{H}_{yper}$ in (a), where $G$ admits a set-coloring
$F:V(G)\rightarrow\mathcal{E}$ such that each edge $uv$ is colored with
$F(uv)$ holding $F(uv)\supseteq F(u)\cap F(v)\neq\emptyset$, and $|F(uv)|=4$
for each edge $uv\in E(G)$, as well as
$[1,15]=\Lambda=\bigcup_{e_{i}\in\mathcal{E}}e_{i}$.

We get a _$7$ -uniform adjacent hypergraph_
$\overline{\mathcal{H}}_{yper}=(\Lambda,\overline{\mathcal{E}})$ defined in
[12], where
$\overline{\mathcal{E}}=\\{\overline{e}_{1},\overline{e}_{2},\overline{e}_{3},\overline{e}_{4}\\}$
with $\overline{e}_{1}=\\{$3, 4, 5, 8, 10, 13, 14$\\}$,
$\overline{e}_{2}=\\{$1, 4, 8, 9, 12, 14, 15$\\}$, $\overline{e}_{3}=\\{$1, 2,
3, 7, 13, 14, 15$\\}$, $\overline{e}_{4}=\\{$1, 2, 3, ,4, 5, 6, 12$\\}$. Each
edge of the intersected-graph $\overline{H}$ of the adjacent hypergraph
$\overline{\mathcal{H}}_{yper}$ is colored with a set having cardinality 3.
Thereby, we call $\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$ and
$\overline{\mathcal{H}}_{yper}=(\Lambda,\overline{\mathcal{E}})$ _ve-double
uniform hypergraphs_. $\square$

######  Problem 3.

For a finite set $\Lambda$, how many hyperedge sets defined on $\Lambda$ are
there?

######  Example 2.

We have the _dual hypergraph_
$\mathcal{H}_{dual}=(\Lambda_{dual},\mathcal{E}_{dual})$ of a $8$-uniform
hypergraph $\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$ shown in Fig.8 (a) with
its vertex set $\Lambda_{dual}=\mathcal{E}=\\{e_{1},e_{2},e_{3},e_{4}\\}$, and
its hyperedge set
$\mathcal{E}_{dual}=\\{X_{j}\\}^{15}_{j=1}=\big{\\{}\\{e_{i}:x_{j}\in
e_{i}\in\mathcal{E}\\}\big{\\}}^{15}_{j=1}$, where $X_{1}=\\{e_{1}\\}$,
$X_{2}=\\{e_{1},e_{2}\\}$, $X_{3}=\\{e_{2}\\}$, $X_{4}=\\{e_{3}\\}$,
$X_{5}=\\{e_{2},e_{3}\\}$, $X_{6}=\\{e_{1},e_{2},e_{3}\\}$,
$X_{7}=\\{e_{1},e_{2},e_{4}\\}$, $X_{8}=\\{e_{3},e_{4}\\}$,
$X_{9}=\\{e_{1},e_{3},e_{4}\\}$, $X_{10}=\\{e_{2},e_{3},e_{4}\\}$,
$X_{11}=\\{e_{1},e_{2},e_{3},e_{4}\\}$, $X_{12}=\\{e_{1},e_{3}\\}$,
$X_{13}=\\{e_{2},e_{4}\\}$, $X_{14}=\\{e_{4}\\}$ and
$X_{15}=\\{e_{1},e_{4}\\}$.

In the above dual hypergraph $\mathcal{H}_{dual}$, we have the hyperedge
degree $\textrm{deg}(e_{i})=8$ with $i\in[1,4]$, so the hyperedge degree
sequence
$\\{\textrm{deg}(e_{1}),\textrm{deg}(e_{2}),\textrm{deg}(e_{3}),\textrm{deg}(e_{4})\\}$
satisfies the Erdös-Galia Theorem. The intersected-graph $G_{dual}$ of the
dual hypergraph $\mathcal{H}_{dual}$ admits a set-coloring
$F_{dual}:V(G_{dual})\rightarrow\mathcal{E}_{dual}$, such that each induced
edge color

$F_{dual}(u_{i}v_{j})\supseteq F_{dual}(u_{i})\cap F_{dual}(v_{j})=X_{i}\cap
X_{j}\neq\emptyset$

holds true. $\square$

######  Example 3.

Fig.9 (b) shows us the intersected-graph $G_{yper}$ of a hypergraph
$\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$ subject to $R_{est}(1)$, and
$\mathcal{H}_{yper}$ has its own vertex set $\Lambda=[1,12]$ and its own
hyperedge set

${\begin{split}\mathcal{E}=&\big{\\{}\\{2,12\\},\\{1,11\\},\\{1,10\\},\\{6,10,11,12\\},\\{4,5,6\\},\\{5,7\\},\\{7,8,9\\},\\\
&\\{1,8\\},\\{4,9\\},\\{3,4\\},\\{2,8\\},\\{1,2,3\\},\\{1,7\\}\big{\\}}\end{split}}$
(13)

since $[1,12]=\bigcup_{e\in\mathcal{E}}e$. Moreover, the intersected-
hypergraph $G_{yper}$ contains a clique $\big{\\{}\\{1,2,3\\},\\{1,11\\}$,
$\\{1,10\\}$, $\\{1,8\\}$, $\\{1,7\\}\big{\\}}$, and hyperedge cycles

$\big{\\{}\\{1,2,3\\},\\{2,8\\},\\{2,12\\}\big{\\}},\big{\\{}\\{2,8\\},\\{1,8\\},\\{7,8,9\\}\big{\\}},\big{\\{}\\{4,5,6\\},\\{4,9\\},\\{3,4\\}\big{\\}},\big{\\{}\\{1,7\\},\\{7,8,9\\},\\{5,7\\}\big{\\}}$

Furthermore, the intersected-hypergraph $G_{yper}$ has a _Hamilton hyperedge
cycle_

${\begin{split}C_{yper}=&\\{2,12\\}\\{\textbf{{\color[rgb]{0.00,0.00,1.00}12}}\\}\\{6,10,11,12\\}\\{\textbf{{\color[rgb]{0.00,0.00,1.00}6}}\\}\\{4,5,6\\}\\{\textbf{{\color[rgb]{0.00,0.00,1.00}5}}\\}\\{5,7\\}\\{\textbf{{\color[rgb]{0.00,0.00,1.00}7}}\\}\\{7,8,9\\}\\{\textbf{{\color[rgb]{0.00,0.00,1.00}9}}\\}\\{4,9\\}\\{\textbf{{\color[rgb]{0.00,0.00,1.00}4}}\\}\\{3,4\\}\\\
&\\{\textbf{{\color[rgb]{0.00,0.00,1.00}3}}\\}\\{1,2,3\\}\\{\textbf{{\color[rgb]{0.00,0.00,1.00}1}}\\}\\{1,7\\}\\{\textbf{{\color[rgb]{0.00,0.00,1.00}1}}\\}\\{1,10\\}\\{\textbf{{\color[rgb]{0.00,0.00,1.00}1}}\\}\\{1,11\\}\\{\textbf{{\color[rgb]{0.00,0.00,1.00}1}}\\}\\{1,8\\}\\{\textbf{{\color[rgb]{0.00,0.00,1.00}8}}\\}\\{2,8\\}\\{\textbf{{\color[rgb]{0.00,0.00,1.00}2}}\\}\\{2,12\\}\end{split}}$

because of $G_{yper}$ has no _ear_.

Figure 9: (a) A tree $T$ admits a graceful-intersection total set-labeling
$F:V(T)\rightarrow\mathcal{E}$, where $\mathcal{E}$ is defined in Eq.(13); (b)
the intersected-graph $G_{yper}$ of a hypergraph
$\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$ subject to $R_{est}(1)$, and $T$ is
a spanning tree of $G_{yper}$.

It is noticeable, there are two or more graphs admitting graceful-intersection
total set-labelings defined on a unique hyperedge set $\mathcal{E}$, see
examples $T,T_{1},T_{2},T_{3}$ shown in Fig.9 (a) and Fig.10 (a), Fig.10 (b)
and Fig.10 (c). Clearly, the intersected-graph $G_{yper}$ contains each of
$T,T_{1},T_{2},T_{3}$ as its set-colored subgraphs. Notice that each set-
colored tree $T_{i}$ has no _ear_. $\square$

Figure 10: Three trees $T_{1},T_{2},T_{3}$ admit three graceful-intersection
total set-labelings defined on a unique hyperedge set $\mathcal{E}$ defined in
Eq.(13), but $T_{i}\not\cong T_{j}$ for $i\neq j$.

######  Example 4.

In Fig.11, we have a set-colored graph $K^{*}=K_{4}\bowtie K_{6}$, where the
hyperedge set $\mathcal{E}=\\{e_{1}$, $e_{2},\dots,e_{10}\\}$ defined on
$\Lambda=\\{a,b,c,e,f,g,h,i,j,k\\}$, each vertex color set of $K_{4}$ is an
ear, however each vertex color set of $K_{6}$ is not an ear, and moreover
$K^{*}$ contains non-ear-hyperedge cycles $C_{6}$ and ear-hyperedge cycles
$C_{4}$. The operation “$\bowtie$” is called _intersection operation_.
$\square$

Figure 11: An set-colored graph $K^{*}=K_{4}\bowtie K_{6}$, where (a) a
complete graph $K_{4}$; (b) a complete graph $K_{6}$.

######  Remark 2.

The concepts of hyperedge path, hyperedge cycle and Hamilton hyperedge cycle
are defined here for distinguishing popular path, cycle and Hamilton cycle of
graphs. A graph $G$ has cycles or paths, however, if $G$ is a set-colored
graph defined by a set-coloring $F:V(G)\rightarrow\mathcal{E}$, where
$\mathcal{E}$ is a hyperedge set defined on $\Lambda$, it may happen that $G$
has no hyperedge cycle or hyperedge path. Others, such as hyperedge degree,
hyperedge coloring, hyperdiameter _etc._ , are defined here for providing
methods of measuring hypergraphs.

In graphs, a vertex $x$ has its own degree $\textrm{deg}(x)=|\\{y:y\in
N(x)\\}|=|N(x)|$, and an edge $uv$ has its own degree
$\textrm{deg}(uv)=|N(u)|+|N(v)|-2$. In hypergraphs, a hypervertex
$x\in\Lambda$ has its own _hypervertex degree_
$\textrm{deg}_{\mathcal{E}}(x)=\big{|}\big{\\{}e_{i}:x\in
e_{i}\in\mathcal{E}\big{\\}}\big{|}$, and a hyperedge $e_{i}\in\mathcal{E}$
has its own _hyperedge degree_
$\textrm{deg}(e_{i})=\big{|}\big{\\{}e_{j}:e_{i}\cap
e_{j}\neq\emptyset,e_{j}\in\mathcal{E}\setminus\\{e_{i}\\}\big{\\}}\big{|}$.
Thereby, the hypervertex degree is a concept only related with a unique
hyperedge set, not for other hyperedge sets. $\parallel$

######  Proposition 17.

If a hypergraph $\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$ has its own
intersected-graph to be connected, then each bipartition
$(\mathcal{E}_{1},\mathcal{E}_{2})$ of $\mathcal{E}$ holds that there exists a
pair of hyperedges $e\in\mathcal{E}_{1}$ and $e\,^{\prime}\in\mathcal{E}_{2}$
satisfying $e\cap e\,^{\prime}\neq\emptyset$.

######  Theorem 18.

∗ If a hypergraph $\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$ has two
intersected-graphs $G_{1}$ and $G_{2}$, then $G_{1}\cong G_{2}$.

###### Proof.

Suppose that two graphs $G_{1}$ and $G_{2}$ are the intersected-graphs of a
hypergraph $\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$, so there a set-coloring
$F_{i}:V(G_{i})\rightarrow\mathcal{E}$ with $i=1,2$. Since each hyperedge
$e\in\mathcal{E}$ corresponds a vertex $u\in V(G_{1})$ holding $F_{1}(u)=e$,
and this hyperedge $e$ corresponds another vertex $v\in V(G_{2})$ holding
$F_{2}(v)=e$, then we get a function $\varphi:V(G_{1})\rightarrow V(G_{2})$,
such that $V(G_{2})\ni v=\varphi(u)$ for $u\in V(G_{1})$ if $F_{1}(u)=e$ and
$F_{2}(v)=e$.

For $e\cup e\,^{\prime}\neq\emptyset$ in $\mathcal{E}$, we have
$F_{1}(uu\,^{\prime})=F_{1}(u)\cap F_{1}(u\,^{\prime})\neq\emptyset$ as
$F_{1}(u)=e$ and $F_{1}(u\,^{\prime})=e\,^{\prime}$ for $uu\,^{\prime}\in
E(G_{1})$, and moreover $F_{2}(vv\,^{\prime})=F_{2}(v)\cap
F_{2}(v\,^{\prime})\neq\emptyset$ as $F_{2}(v)=e$ and
$F_{2}(v\,^{\prime})=e\,^{\prime}$ for $v\,^{\prime}\in E(G_{2})$. Thereby,
$\varphi(u)\varphi(u\,^{\prime})\in E(G_{2})$ for each edge $uu\,^{\prime}\in
E(G_{1})$, that is, a graph homomorphism $G_{1}\rightarrow G_{2}$, and
$\varphi(G_{1})$ is an induced subgraph of $G_{2}$.

Conversely, we have another function $\lambda:V(G_{2})\rightarrow V(G_{1})$,
such that $\varphi(v)\varphi(v\,^{\prime})\in E(G_{1})$ for each edge
$vv\,^{\prime}\in E(G_{2})$, which means a graph homomorphism
$G_{2}\rightarrow G_{1}$, and $\lambda(G_{2})$ is an induced subgraph of
$G_{1}$.

We claim $G_{1}\cong G_{2}$ by Definition 3 and Theorem 4. The proof of this
theorem is covered. ∎

######  Problem 4.

Characterize intersected-graphs having one of properties: (i) double-uniform,
(ii) non-ear and (iii) each vertex color set is an ear.

######  Problem 5.

If each edge $uv\in E(G)$ is in a Hamilton cycle of a connected graph $G$, we
say $G$ to be _edge-hamiltonian_. Characterize edge-hamiltonian graphs.

In Fig.12, the complete graph $K_{4}$ is edge-hamiltonian defined in Problem
5, so are $G_{1}$ and $G_{2}$. However, the graph $G_{3}$ shown in Fig.12(d)
is not edge-hamiltonian, since two edges $uw$ and $xy$ of $G_{3}$ are not in
any Hamilton cycle of $G_{3}$.

Figure 12: (a), (b) and (c) are edge-hamiltonian, (d) is not edge-hamiltonian.

######  Example 5.

There are three Hamilton cycles $C^{*}_{1}=uwyxu$, $C^{*}_{2}=uywxu$ and
$C^{*}_{3}=uwxyu$ in the complete graph $K_{4}$ shown in Fig.12(a), and we let
$e_{i}=E(C^{*}_{i})$ with $i\in[1,3]$, thus, we get a hypergraph
$\mathcal{H}^{K_{4}}_{yper}=(\Lambda,\mathcal{E}^{*})$, where
$\mathcal{E}^{*}=\\{e_{1},e_{2},e_{3}\\}$. Clearly, the intersected-graph
$G(K_{4})$ of the hypergraph $\mathcal{H}^{K_{4}}_{yper}$ is a complete graph
$K_{3}$, since $e_{1}\cap e_{2}=\\{ux,wy\\}$, $e_{1}\cap e_{3}=\\{xy,uw\\}$
and $e_{2}\cap e_{3}=\\{uy,wx\\}$. $\square$

For considering Problem 5, we show the concept of edge-hamiltonian graphic
lattice. Suppose that $\textbf{{H}}=(H_{1},H_{2},\dots,H_{m})$ is an _edge-
hamiltonian graph base_ , where each graph $H_{i}$ is an edge-hamiltonian
graph for $i\in[1,m]$, and there is an _operation base_
$\textbf{{O}}=(O_{1},O_{2},\dots,O_{n})$ such that doing each operation
$O_{k}$ to two edge-hamiltonian graphs $H_{i}$ and $H_{j}$ produces a new
edge-hamiltonian graph, denoted as $O_{k}\langle H_{i},H_{j}\rangle$.

We take a permutation $T_{1},T_{2},\dots,T_{A}$ of edge-hamiltonian graphs
$a_{1}H_{1},a_{2}H_{2},\dots,a_{m}H_{m}$, where $A=\sum^{m}_{i=1}a_{i}$ for
$a_{i}\in Z^{0}$ and $H_{i}\in\textbf{{H}}$, and do an operation $O_{i_{1}}$
selected randomly to $T_{1},T_{2}$, the resultant graph is a new edge-
hamiltonian graph $L_{1}=O_{i_{1}}\langle T_{1},T_{2}\rangle$ with selecting
randomly $O_{i_{1}}\in\textbf{{O}}$. Again we get a new edge-hamiltonian graph
$L_{2}=O_{i_{2}}\langle L_{1},T_{3}\rangle$ with selecting randomly
$O_{i_{2}}\in\textbf{{O}}$, in general, we have edge-hamiltonian graphs
$L_{k}=O_{i_{k}}\langle L_{k-1},T_{k+1}\rangle$ with
$O_{i_{k}}\in\textbf{{O}}$ and $k\in[1,A-1]$. For simplicity, we write the
edge-hamiltonian graph

$L_{A-1}=O_{i_{A-1}}\langle
L_{A-2},T_{A}\rangle=\big{[}\textbf{{O}}\big{]}^{A}_{j=1}T_{j}=\big{[}\textbf{{O}}\big{]}^{M}_{i=1}a_{i}H_{i},$
(14)

so we get an _edge-hamiltonian graphic lattice_

$\textbf{{L}}(Z^{0}[\textbf{{O}}]\textbf{{H}})=\left\\{\big{[}\textbf{{O}}\big{]}^{M}_{i=1}a_{i}H_{i}:a_{i}\in
Z^{0},H_{i}\in\textbf{{H}}\right\\}$ (15)

with $\sum^{m}_{i=1}a_{i}\geq 1$. It is not hard to see that each graph
$G\in\textbf{{L}}(Z^{0}[\textbf{{O}}]\textbf{{H}})$ is just an edge-
hamiltonian graph, so the edge-hamiltonian graphic lattice
$\textbf{{L}}(Z^{0}[\textbf{{O}}]\textbf{{H}})$ is a generator of edge-
hamiltonian graphs. In other word, each graph
$G\in\textbf{{L}}(Z^{0}[\textbf{{O}}]\textbf{{H}})$ does not obey any judging
condition of any one of $H_{1},H_{2},\dots,H_{m}$ to be edge-hamiltonian
graph, which means that there is no necessary and sufficient condition for
judging a hypergraph having _hyperedge Hamilton cycle_.

######  Example 6.

Let $\textbf{{H}}=(H_{1},H_{2},\dots,H_{m})$ be an edge-hamiltonian graph
base. Since each Hamilton cycle of an edge-hamiltonian graph $H_{i}$ runs over
each vertex $u_{i}\in V(H_{i})$, we vertex-split the vertex $u_{i}$ into
$u\,^{\prime}_{i}$ and $u\,^{\prime\prime}_{i}$ such that
$u_{i}=u\,^{\prime}_{i}\odot u\,^{\prime\prime}_{i}$. Similarly, we vertex-
split a vertex $v_{j}$ of another edge-hamiltonian graph $H_{j}$ with $i\neq
j$ into $v\,^{\prime}_{j}$ and $uv\,^{\prime\prime}_{j}$ such that
$v_{j}=v\,^{\prime}_{j}\odot v\,^{\prime\prime}_{j}$. We show the following
operations for constructing edge-hamiltonian graphs as follows:

$O_{1}$: We join vertex $u\,^{\prime}_{i}$ with vertex $v\,^{\prime}_{j}$
together by an edge $u\,^{\prime}_{i}v\,^{\prime}_{j}$, and join
$u\,^{\prime\prime}_{i}$ with $v\,^{\prime\prime}_{j}$ together by an edge
$u\,^{\prime\prime}_{i}v\,^{\prime\prime}_{j}$, the resultant graph is denoted
as $\ominus_{2}\langle H_{i}\wedge u_{i},H_{j}\wedge v_{j}\rangle$, which is
an edge-hamiltonian graph too.

$O_{2}$: We vertex-coincide two vertices $u\,^{\prime}_{i}$ and
$v\,^{\prime}_{j}$ into one vertex $w\,^{\prime}=u\,^{\prime}_{i}\odot
v\,^{\prime}_{j}$, and vertex-coincide $u\,^{\prime\prime}_{i}$ and
$v\,^{\prime\prime}_{j}$ into one vertex
$w\,^{\prime\prime}=u\,^{\prime\prime}_{i}\odot v\,^{\prime\prime}_{j}$, the
resultant graph is denoted as $\odot_{2}\langle H_{i}\wedge u_{i},H_{j}\wedge
v_{j}\rangle$, which is clearly an edge-hamiltonian graph.

$O_{3}$: We vertex-coincide two vertices $u\,^{\prime}_{i}$ and
$v\,^{\prime}_{j}$ into one vertex $w\,^{\prime}=u\,^{\prime}_{i}\odot
v\,^{\prime}_{j}$, and join $u\,^{\prime\prime}_{i}$ with
$v\,^{\prime\prime}_{j}$ together by an edge
$u\,^{\prime\prime}_{i}v\,^{\prime\prime}_{j}$, the resultant graph is denoted
as $[\odot\ominus]\langle H_{i}\wedge u_{i},H_{j}\wedge v_{j}\rangle$, which
is just an edge-hamiltonian graph. $\square$

In fact, there are many ways for constructing edge-hamiltonian graphs: We
vertex-split a vertex $u$ of $G$ into two vertices $u\,^{\prime}$ and
$u\,^{\prime\prime}$, and then

(i) add a new edge $u\,^{\prime}u\,^{\prime\prime}$ to the vertex-split graph
$G\wedge u$, the resultant graph is denoted as $H=G\wedge
u+u\,^{\prime}u\,^{\prime\prime}$;

(ii) add a path $P(u\,^{\prime},u\,^{\prime\prime})$ to the vertex-split graph
$G\wedge u$ to join two vertices $u\,^{\prime}$ and $u\,^{\prime\prime}$, the
resultant graph is denoted as $H\,^{\prime}=G\wedge
u+P(u\,^{\prime},u\,^{\prime\prime})$; and

(iii) add a complete graph $K_{m}$ to vertex-coincide a vertex $x\in V(K_{m})$
with the vertex $u\,^{\prime}$ into one, and to vertex-coincide a vertex $y\in
V(K_{m})$ with the vertex $u\,^{\prime\prime}$ into one, the resultant graph
is denoted as $H^{*}=G\wedge u+\odot\langle
u\,^{\prime},K_{m}\rangle+\odot\langle u\,^{\prime\prime},K_{m}\rangle$.

We have the following fact:

######  Proposition 19.

A connected graph $G$ is edge-hamiltonian if and only if each of $H=G\wedge
u+u\,^{\prime}u\,^{\prime\prime}$, $H\,^{\prime}=G\wedge
u+P(u\,^{\prime},u\,^{\prime\prime})$ and $H^{*}=G\wedge u+\odot\langle
u\,^{\prime},K_{m}\rangle+\odot\langle u\,^{\prime\prime},K_{m}\rangle$ is
edge-hamiltonian.

######  Problem 6.

By Problem 5 and the edge-hamiltonian graphic lattice shown in Eq.(15), we
guess: _There is no necessary and sufficient condition for judging edge-
hamiltonian graphs_ , since each graph
$G=\big{[}\textbf{{O}}\big{]}^{M}_{i=1}a_{i}H_{i}$ may not satisfy the judging
conditions of determining $H_{1},H_{2},\dots,H_{m}$ to be edge-hamiltonian
graphs, and moreover new operations for constructing edge-hamiltonian graphs
will probably arise everyday.

######  Problem 7.

(i) Suppose that $G$ is a connected graph containing Hamilton cycles. If each
path $P_{k}$ of $k$ vertices is in a Hamilton cycle of $G$, we say that $G$ is
_$k$ -path-hamiltonian_. Characterize $k$-path-hamiltonian graphs.

(ii) Determine a positive real number $\mu$, such that each connected graph
$G$ is edge-hamiltonian if minimal degree $\delta(G)\geq\mu\cdot|V(G)|$.

######  Problem 8.

If $\Lambda=\bigcup_{e,e\,^{\prime}\in\mathcal{E}}(e\cap e\,^{\prime})$ for a
hyperedge set $\mathcal{E}$ defined on a finite set $\Lambda$, then
$\mathcal{E}^{*}=\\{e\cap e\,^{\prime}:e,e\,^{\prime}\in\mathcal{E}\\}$ is a
hyperedge set, characterize the intersected-graph of a hypergraph
$\mathcal{H}_{yper}=(\Lambda,\mathcal{E}^{*})$ if $|e^{*}_{i}\cap
e^{*}_{j}|\geq 2$ for each pair of hyperedges
$e^{*}_{i},e^{*}_{j}\in\mathcal{E}^{*}$.

Figure 13:  Three set-colorings of a complete graph $K_{4}$.

######  Theorem 20.

∗ For any connected $(p,q)$-graph $G$, there is a set-coloring
$F:V(G)\rightarrow\mathcal{E}$, where the hyperedge set
$\mathcal{E}\subset\Lambda^{2}$ and $\bigcup_{e\in\mathcal{E}}e=\Lambda$, such
that $F(x)\neq F(y)$ for distinct vertices $x,y\in V(G)$ and induced edge
colors $F(uv)=F(u)\cap F(v)$ for each edge $uv\in E(G)$ holding $F(xy)\neq
F(wz)$ for distinct edges $xy,wz\in E(G)$, as well as $|\Lambda|$ is the
smallest one for any set-coloring $F^{*}:V(G)\rightarrow\mathcal{E}^{*}$ with
$\mathcal{E}^{*}\subset\Lambda^{2}_{*}$ and
$\bigcup_{e\in\mathcal{E}^{*}}e=\Lambda_{*}$ (see an example $K_{4,1}$ shown
in Fig.13(a)). Moreover, we add a requirement: $F(x)\not\subset F(y)$ for
distinct vertices $x,y\in V(G)$ and $F(xy)\not\subset F(wz)$ for distinct
edges $xy,wz\in E(G)$, see an example $K_{4,2}$ shown in Fig.13(b).

######  Problem 9.

Let
$\mathcal{H}_{yper}(G)=\big{\\{}\mathcal{E}_{1},\mathcal{E}_{2},\dots,\mathcal{E}_{M(G)}\big{\\}}$
be the set of hyperedge sets, such that each hyperedge set $\mathcal{E}_{i}$
holds $\Lambda_{i}=\bigcup_{e\in\mathcal{E}_{i}}e$ and forms a hypergraph
$\mathcal{H}^{i}_{yper}=(\Lambda_{i},\mathcal{E}_{i})$, as well as $G$ is the
intersected-graph of each hypergraph
$\mathcal{H}^{i}_{yper}=(\Lambda_{i},\mathcal{E}_{i})$. Find connection
between two hypergraphs $\mathcal{H}^{i}_{yper}=(\Lambda_{i},\mathcal{E}_{i})$
and $\mathcal{H}^{j}_{yper}=(\Lambda_{j},\mathcal{E}_{j})$ if $i\neq j$, and
estimate number $M(G)$.

######  Remark 3.

Notice that the intersected-graph of a hypergraph
$\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$ s.t. $R_{est}(1)$ appeared in [12].

(i) One set-type Topcode-matrix
$T^{set}_{code}=(X^{set},~{}E^{set},~{}Y^{set})^{T}$ defined in Definition 22
may correspond two or more intersected-graphs. There are four set-colored
graphs $T_{1},T_{2},T_{3},T_{4}$ shown in Fig.14, they correspond the set-type
Topcode-matrix $H^{yper}_{code}(K_{4,2})$ shown in Eq.(18). In the topological
structure of view, $K_{4,2}$ (shown in Fig.13(b)), $T_{1},T_{2},T_{3}$ and
$T_{4}$ are not isomorphic from each other. In fact, these four set-colored
graphs $T_{1},T_{2},T_{3},T_{4}$ are obtained from the set-colored graph
$K_{4,2}$ and the vertex-splitting operation, conversely, each set-colored
graph $T_{i}$ with $i\in[1,4]$ is _graph homomorphism_ to $K_{4,2}$.

Figure 14:  Four set-colored graphs correspond a unique set-type Topcode-
matrix $H^{yper}_{code}(K_{4,2})$ shown in Eq.(18).

(ii) By the set-type Topcode-matrix $T^{set}_{code}(H)$ defined in Eq.(17), we
have a _string-type Topcode-matrix_
$T^{string}_{code}(H)=(X^{*},~{}E^{*},~{}Y^{*})^{T}$ with _v-vector_
$X^{*}=(x_{1},x_{2},\dots,x_{q})$, _e-vector_ $E^{*}=(e_{1}$, $e_{2}$,
$\dots$, $e_{q})$ and _v-vector_ $Y^{*}=(y_{1},y_{2},\dots,y_{q})$ consist of
number-based strings $x_{i}$, $e_{i}$ and $y_{i}$ for $i\in[1,q]$, where for
each $i\in[1,q]$, each number-based string $x_{i}$ is a permutation of
$a_{i,1},a_{i,2},\dots,a_{i,A_{i}}$ with $a_{i,j}\in F(x_{i})$ and cardinality
$A_{i}=|F(x_{i})|$, each number-based string $e_{i}$ is a permutation of
$c_{i,1},c_{i,2},\dots,c_{i,C_{i}}$ with $c_{i,j}\in F(e_{i})$ and cardinality
$C_{i}=|F(e_{i})|$, and each number-based string $y_{i}$ is a permutation of
$b_{i,1},b_{i,2},\dots,b_{i,B_{i}}$ with $b_{i,j}\in F(y_{i})$ and cardinality
$B_{i}=|F(y_{i})|$.

Thereby, one set-type Topcode-matrix $T^{set}_{code}(H)$ enables us to obtain
$M(ABC)$ numbered-based string Topcode-matrices like $T^{string}_{code}(H)$,
and we get $(3q)!M(ABC)$ number-based strings in total, where the number

$M(ABC)=\prod^{q}_{i=1}(A_{i})!\prod^{q}_{i=1}(C_{i})!\prod^{q}_{i=1}(B_{i})!$
(16)

It is meaningful to explore more applications of intersected-graphs defined in
Definition 20. $\parallel$

######  Theorem 21.

∗ If a $(p,q)$-graph $G$ admits a graceful-intersection total set-labeling
defined on a hyperedge set $\mathcal{E}\subseteq[0,q]^{2}$ with
$\bigcup_{e_{i}\in\mathcal{E}}e_{i}=[0,q]$, then the intersected-graph of the
hypergraph $\mathcal{H}_{yper}=([0,q],\mathcal{E})$ contains each of
$(p,q)$-graphs admitting graceful-intersection total set-labelings defined on
the hyperedge set $\mathcal{E}$.

######  Problem 10.

Suppose that a connected graph $G$ admits a graceful-intersection set-coloring
$F$ defined on a hyperedge set $\mathcal{E}$ based on a set $\Lambda$, and $G$
is the intersected-graph of the hypergraph
$\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$. Does the hyperedge set
$\mathcal{E}=F(V(G))$ contain a perfect hypermatching
$\\{M_{1},M_{2},\dots,M_{s}\\}\subset\mathcal{E}$ such that $M_{i}\cap
M_{j}=\emptyset$ for $i\neq j$ and $\bigcup^{s}_{i=1}M_{i}=\Lambda$?

###  3.3 Set-type Topcode-matrices

By the intersected-graphs defined in Definition 20, we have:

######  Definition 22.

∗ Since an intersected-$(p,q)$-graph $H$ of a hypergraph
$\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$ subject to $R_{est}(m+1)$ admits a
$W$-type set-coloring $F:V(H)\rightarrow\mathcal{E}$, so this
intersected-$(p,q)$-graph $H$ has its own _set-type Topcode-matrix_

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

with _v-set-vector_ $X^{set}=(F(x_{1}),F(x_{2}),\dots,F(x_{q}))$, _e-set-
vector_ $E^{set}=(F(e_{1})$, $F(e_{2})$, $\dots$, $F(e_{q}))$ and _v-set-
vector_ $Y^{set}=(F(y_{1}),F(y_{2}),\dots,F(y_{q}))$ such that all sets
$F(x_{i}),F(y_{k})\in\mathcal{E}$, and there is a function $\phi_{s}$ for some
$c_{s}\in R_{est}(m+1)$ holding $F(e_{j})=\phi_{s}(F(x_{j}),F(y_{j}))$, as
well as $F(e_{j})\supseteq F(x_{j})\cap F(y_{j})\neq\emptyset$ for each
$j\in[1,q]$. $\square$

See a set-colored graph $K_{4,2}$ shown in Fig.13, and this graph $K_{4,2}$
corresponds its own set-type Topcode-matrix $T^{set}_{code}(K_{4,2})$ as
follows:

$\centering{\begin{split}T^{set}_{code}(K_{4,2})=\left(\begin{array}[]{cccccc}\\{1,2,3\\}&\\{1,2,3\\}&\\{1,2,3\\}&\\{4,1,2\\}&\\{2,3,4\\}&\\{2,3,4\\}\\\
\\{1,2\\}&\\{1,3\\}&\\{2,3\\}&\\{1,4\\}&\\{2,4\\}&\\{3,4\\}\\\
\\{4,1,2\\}&\\{3,4,1\\}&\\{2,3,4\\}&\\{3,4,1\\}&\\{4,1,2\\}&\\{3,4,1\\}\end{array}\right)\end{split}}\@add@centering$
(18)

###  3.4 Subgraphs of intersected-graphs

For a given connected graph $G$ admitting a set-coloring
$F:V(G)\rightarrow\mathcal{E}$, how to judge $G$ to be the intersected-graph
of a hypergraph $\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$? We can answer:

(i) If $G$ is a complete graph, then $G$ is an intersected-graph; and

(ii) if there are no vertices $x,y$ of $G$ holding $xy\not\in E(G)$ and
$F(x)\cap F(y)\neq\emptyset$, then $G$ is an intersected-graph.

######  Theorem 22.

∗ If a tree $T$ admits a mapping $f:V(T)\rightarrow[1,p-1]$ with $p=|V(T)|$
and $f(z)\neq f(y)$ for any pair of distinct vertices $x,y$, then $T$ admits a
set-coloring defined on a hyperedge set $\mathcal{E}$ such that $T$ is a
subgraph of the intersected-graph of a hypergraph
$\mathcal{H}_{yper}=([0,p-1],\mathcal{E})$.

###### Proof.

According the hypothesis of the theorem, we define a set-coloring $F$ for the
tree $T$ by means of the following so-called VSET-coloring algorithm:

Step 1. Each leaf $w_{j}$ of the tree $T$ is set-colored with
$F(w_{j})=\\{f(w_{j}),f(v)\\}$, where the edge $w_{j}v\in E(T)$.

Step 2. Each leaf $w^{1}_{j}$ of the tree $T_{1}=T-L(T)$, where $L(T)$ is the
set of leaves of $T$, is colored by $F(w^{1}_{j})=\\{f(w^{1}_{j}),f(z)\\}$,
where the edge $w^{1}_{j}z\in E(T_{1})$.

Step 3. Each leaf $w^{r}_{j}$ of the tree $T_{r}=T-L(T_{r-1})$, where
$L(T_{r-1})$ is the set of leaves of $T_{r-1}$, is colored by
$F(w^{r}_{j})=\\{f(w^{r}_{j}),f(u)\\}$, where the edge $w^{r}_{j}u\in
E(T_{r})$.

Step 4. Suppose $T_{k}$ is a star $K_{1,m}$ with vertex set
$V(K_{1,m})=\big{\\{}w^{k}_{j},u_{0}:j\in[1,m]\big{\\}}$ and edge set
$E(K_{1,m})=\big{\\{}u_{0}w^{k}_{1},u_{0}w^{k}_{2},\dots,u_{0}w^{k}_{m}\big{\\}}$,
we color each leaf $w^{k}_{j}$ with
$F(w^{k}_{j})=\big{\\{}f(w^{k}_{j}),f(u_{0})\big{\\}}$, and
$F(u_{0})=\\{f(u_{0})\\}$.

Step 5. $F(uv)=F(u)\cap F(v)\neq\emptyset$ for each edge $uv\in E(T)$.

Thereby, the tree $T$ admits the set-coloring $F$ subject to
$R_{est}(1)=\\{c_{0}\\}$, such that $c_{0}$ holds $F(uv)\supseteq F(u)\cap
F(v)\neq\emptyset$ for each edge $uv\in E(T)$. So, $T$ is a subgraph of the
intersected-graph of a hypergraph $\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$
with its hyperedge set $\mathcal{E}=F(V(T))$, and
$\Lambda=[1,p-1]=\bigcup_{e\in\mathcal{E}}e$, we are done. ∎

Figure 15: An example for understanding the proof of Theorem 22.

######  Corollary 23.

If a tree $T$ admits a graceful labeling, then $T$ admits a graceful set-
coloring $F$ subject to $R_{est}(2)=\\{c_{0},c_{1}\\}$, such that $c_{0}$
holds $F(uv)\supseteq F(u)\cap F(v)\neq\emptyset$ for each edge $uv\in E(T)$,
and $c_{1}$ holds $a_{uv}=|a_{u}-a_{v}|$ for some $a_{uv}\in F(uv)$, $a_{u}\in
F(u)$ and $a_{v}\in F(v)$, which derives a set

$\\{a_{uv}=|a_{u}-a_{v}|:uv\in E(T)\\}=[1,|E(T)|\,]$

and moreover $T$ is a subgraph of the intersected-graph of a hypergraph
$\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$ with $\mathcal{E}=F(V(T))$ and
$\Lambda=[0,|E(T)|\,]=\bigcup_{e\in\mathcal{E}}e$.

######  Example 7.

A _multiple topological authentication_ is shown in Fig.16, we observe that a
lobster $T$ is as a _topological public-key_ , and other lobsters
$T_{1},T_{2},T_{3},T_{4},T_{5},T_{6}$ form a group of _topological private-
keys_ , where

  1. (i)

$T_{2}$ admits a _pan-edge-magic total labeling_ $f_{2}$ holding
$f_{2}(x_{i})+f_{2}(e_{i})+f_{2}(y_{i})=16$ for each edge $e_{i}=x_{i}y_{i}\in
E(T_{2})$;

  2. (ii)

$T_{3}$ admits a _pan-edge-magic total labeling_ $f_{3}$ holding
$f_{3}(x_{i})+f_{3}(e_{i})+f_{3}(y_{i})=27$ for each edge $e_{i}=x_{i}y_{i}\in
E(T_{3})$;

  3. (iii)

$T_{4}$ admits a _felicitous labeling_ $f_{4}$ holding
$f_{4}(e_{i})=f_{4}(x_{i})+f_{4}(y_{i})~{}(\bmod~{}11)$ for each edge
$e_{i}=x_{i}y_{i}\in E(T_{4})$;

  4. (iv)

$T_{5}$ admits an _edge-magic graceful labeling_ $f_{5}$ holding
$\big{|}f_{5}(x_{i})+f_{5}(y_{i})-f_{5}(e_{i})\big{|}=4$ for each edge
$e_{i}=x_{i}y_{i}\in E(T_{5})$;

  5. (v)

$T_{6}$ admits an _edge-odd-graceful labeling_ $f_{6}$ holding
$\\{f_{6}(x_{i})+f_{6}(y_{i})+f_{6}(e_{i}):e_{i}=x_{i}y_{i}\in
E(T_{6})\\}=[16,26]$. $\square$

######  Definition 23.

∗ Suppose that a graph $G$ admits a vertex labeling $f:V(G)\rightarrow[a,b]$
with $f(x)\neq f(y)$ for distinct vertices $x,y\in V(G)$. If there is a group
of edge labelings $f_{1},f_{2},\dots,f_{m}$ induced by $f$ such that each edge
labeling $f_{k}$ holds an equation $e_{k}(f(u),f_{k}(uv),f(v))=0$ for each
edge $uv\in E(G)$, we call $f$ a _one-v multiple-e labeling_ of $G$. $\square$

Figure 16: A lobster $T_{1}$ admits a vertex labeling $f_{1}$ shown in (a),
and this labeling $f_{1}$ induces other labelings $f_{2},f_{3},f_{4},f_{5}$
and $f_{6}$, cited from [29].

######  Example 8.

In Example 7, the lobster $T$ admits a one-v multiple-e labeling defined in
Definition 23 consisted of $f_{1}:V(T)\rightarrow[0,11]$ and $f_{k}$ induced
by $f_{1}$ as follows:

  1. $\textbf{c}_{1}$:

A _pan-edge-magic total labeling_ $f_{2}$ holds
$f_{2}(x_{i})+f_{2}(x_{i}y_{i})+f_{2}(y_{i})=16$ for each edge $x_{i}y_{i}\in
E(T)$;

  2. $\textbf{c}_{2}$:

A _pan-edge-magic total labeling_ $f_{3}$ holds
$f_{3}(x_{i})+f_{3}(x_{i}y_{i})+f_{3}(y_{i})=27$ for each edge $x_{i}y_{i}\in
E(T)$;

  3. $\textbf{c}_{3}$:

A _felicitous labeling_ $f_{4}$ holds
$f_{4}(x_{i}y_{i})=f_{4}(x_{i})+f_{4}(y_{i})~{}(\bmod~{}11)$ for each edge
$x_{i}y_{i}\in E(T)$;

  4. $\textbf{c}_{4}$:

An _edge-magic graceful labeling_ $f_{5}$ holds
$\big{|}f_{5}(x_{i})+f_{5}(y_{i})-f_{5}(x_{i}y_{i})\big{|}=4$ for each edge
$x_{i}y_{i}\in E(T)$;

  5. $\textbf{c}_{5}$:

An _edge-odd-graceful labeling_ $f_{6}$ holds
$\\{f_{6}(x_{i})+f_{6}(y_{i})+f_{6}(x_{i}y_{i}):x_{i}y_{i}\in
E(T)\\}=[16,26]$.

Then we get a set-coloring $F$ of the lobster $T$ defined by
$F(w)=\\{f_{1}(w)\\}$ for $w\in V(T)$, and

$F(x_{i}y_{i})=\\{f_{2}(x_{i}y_{i}),f_{3}(x_{i}y_{i}),f_{4}(x_{i}y_{i}),f_{5}(x_{i}y_{i}),f_{6}(x_{i}y_{i})\\},~{}x_{i}y_{i}\in
E(T)$

The set-colored graph $L$ shown in Fig.17 (a) is the above lobster $T$ colored
with a set-coloring. Moreover, we, by using the VSET-coloring algorithm
introduced in the proof of Theorem 22, get a graph $L_{yper}$ shown in Fig.17
(b) admitting a set-coloring $\varphi$, and $L_{yper}$ is a subgraph of the
intersected-graph of a hypergraph
$\mathcal{H}\,^{\prime\prime}_{yper}=([0,11],\mathcal{E}\,^{\prime\prime})$
subject to $R_{est}(6)=\\{c_{0},c_{1},c_{2},c_{3},c_{4},c_{5}\\}$, where the
hyperedge set

${\begin{split}\mathcal{E}\,^{\prime\prime}=\big{\\{}\\{0,5\\},\\{1,5\\},\\{2,5\\},\\{2\\},\\{2,6\\},\\{2,7\\},\\{2,8\\},\\{3,8\\},\\{3,9\\},\\{2,11\\},\\{4,11\\},\\{4,10\\}\big{\\}}\end{split}}$
(19)

holding $[0,11]=\bigcup_{e\in\mathcal{E}\,^{\prime\prime}}e$, such that the
vertex color set $\varphi(V(L_{yper}))=\mathcal{E}\,^{\prime\prime}$ and the
edge color set

${\begin{split}\varphi(E(L_{yper}))=&\big{\\{}\\{5,1,11,22,21\\},\\{5,2,3,7,9,17,20\\},\\{5,2,6,10,19,21\\},\\{2,4,8,15,19\\},\\\
&\\{2,5,7,9,13,18\\},\\{2,5,3,9,14\\},\\{2,6,10,11,17\\},\\{8,0,5,7,9,16\\},\\\
&\\{3,1,4,7,8,15\\},\\{11,1,4,12\\},\\{4,2,3,10,13\\}\big{\\}}\end{split}}$
(20)

The Graham reduction of the hyperedge set $\mathcal{E}\,^{\prime\prime}$ is an
empty set, and $\mathcal{E}\,^{\prime\prime}$ contains an ear set
$\big{\\{}\\{0,5\\},\\{1,5\\},\\{2,6\\},\\{2,7\\},\\{3,9\\},\\{4,10\\}\big{\\}}$.
The set-coloring $F$ of the set-colored graph $L$ and the set-coloring
$\varphi$ of the set-colored graph $L_{yper}$ hold $F(V(L)\cup
E(L))=\varphi(V(L_{yper})\cup E(L_{yper}))\setminus\mathcal{X}$ with
$\mathcal{X}=\big{\\{}\\{2\\},\\{3\\},\\{4\\},\\{5\\},\\{8\\},\\{11\\}\big{\\}}$.

Figure 17: (a) $L$ admits a set-coloring, but $L$ is not a subgraph of any
intersected-graph; (b) $L_{yper}$ is a subgraphs of some intersected-graph.

######  Theorem 24.

∗ Each graph $G$ admitting a one-v multiple-e labeling, which induces a set-
coloring $\varphi$, then there is a graph $G^{*}$ admitting this set-coloring
$\varphi$ such that $G^{*}\cong G$, and $G^{*}$ is a subgraph of the
intersected-graph of a hypergraph $\mathcal{H}_{yper}=(\Lambda,\mathcal{E})$.

######  Theorem 25.

[26] Each tree admits a _$(k,d)$ -gracefully total coloring_ defined in
Definition 8, also, a _gracefully total coloring_ as $(k,d)=(1,1)$, an _odd-
gracefully total coloring_ as $(k,d)=(1,2)$.

######  Theorem 26.

∗ Each tree admits a graceful-intersection total set-labeling and an odd-
graceful-intersection total set-labeling.

###### Proof.

By Theorem 25 in [26], each tree $T$ admits a _gracefully total coloring_
defined in Definition 8 and an _odd-gracefully total coloring_ , so we define
a graceful-intersection total set-labeling $F_{grace}$ and an odd-graceful-
intersection total set-labeling $F_{odd}$ of $T$ in the following.

Suppose that $f:V(T)\rightarrow[0,p-1]$ is a gracefully total coloring of $T$
of $p$ vertices, so the induced edge color set

$f(E(T))=\\{f(uv)=|f(u)-f(v)|:uv\in E(T)\\}=[1,p-1]$

We define $F_{grace}(x)=\\{f(xy):y\in N(x)\\}$ for $x\in V(T)$, and
$F_{grace}(uv)=\\{f(uv)\\}$ for $uv\in E(T)$, so $F_{grace}$ is really a
graceful-intersection total set-labeling of $T$ since the edge color set
$f(E(T))=[1,p-1]$ implies

$F_{grace}(x)=\\{f(xy):y\in N(x)\\}\neq\\{f(wz):z\in N(w)\\}=F_{grace}(w)$

for any two vertices $x,w\in V(T)$.

By the same way introduced above, we can show an odd-graceful-intersection
total set-labeling $F_{odd}$ of $T$.

The proof of this theorem is complete. ∎

######  Problem 11.

Find graceful labelings and odd-graceful labelings of trees corresponding to
some graceful-intersection total set-labelings and some odd-graceful-
intersection total set-labelings of the trees.

######  Theorem 27.

∗ Each connected $(p,q)$-graph $G$ admits a set-coloring
$F:V(G)\rightarrow\mathcal{E}$ with a hyperedge set $\mathcal{E}$ defined on
$\Lambda=[1,p]$, such that $F(x)\neq F(y)$ for distinct vertices $x,y\in
V(G)$, and each edge $uv\in E(G)$ is colored by an induced hyperedge color set
$F(uv)$ holding $F(uv)\supseteq F(u)\cap F(v)\neq\emptyset$.

###### Proof.

Let $T$ be a spanning tree of the connected $(p,q)$-graph $G$, and let
$\Lambda=[1,p]$. By Theorem 26, this tree $T$ admits a graceful-intersection
total set-labeling $\varphi:V(T)\rightarrow\mathcal{E}_{T}$, such that
$\varphi(x)\neq\varphi(y)$ for distinct vertices $x,y\in V(T)$, and each edge
$uv$ of $E(T)$ is colored with an induced hyperedge
$\varphi(uv)=\varphi(u)\cap\varphi(v)$, as well as
$\Lambda=\bigcup_{e\in\mathcal{E}_{T}}e$. That is, $\mathcal{E}_{T}$ is really
a hyperedge set defined on $\Lambda=[1,p]$.

We add an edge $u_{1}v_{1}\in E(G)\setminus E(T)$ to $T$, the edge-added graph
is denoted as $G_{1}=T+u_{1}v_{1}$, we define a set-coloring $\varphi_{1}$ for
$G_{1}$ as follows:

Case 1. $\varphi(u_{1})\cap\varphi(v_{1})\neq\emptyset$. Then we set
$\varphi_{1}(w)=\varphi(w)$ for $w\in[V(G_{1})\cup
E(G_{1})]\setminus\\{u_{1}v_{1}\\}$, and
$\varphi_{1}(u_{1}v_{1})=\varphi(u_{1})\cap\varphi(v_{1})$.

Case 2. $\varphi(u_{1})\cap\varphi(v_{1})=\emptyset$. We let
$\varphi_{1}(w)=\varphi(w)$ for $w\in[V(G_{1})\cup
E(G_{1})]\setminus\\{u_{1},v_{1},u_{1}v_{1}\\}$, and we pick up a subset
$e_{1}\in\Lambda^{2}\setminus\mathcal{E}_{T}$ to set
$\varphi_{1}(u_{1})=\varphi(u_{1})\cup e_{1}$ and
$\varphi_{1}(v_{1})=\varphi(v_{1})\cup e_{1}$, as well as
$\varphi_{1}(u_{1}v_{1})=e_{1}$. Clearly,
$\varphi_{1}(u_{1})\neq\varphi_{1}(v_{1})$. Since
$|\mathcal{E}_{T}|=|\varphi(V(T))|=p$, we can always do that
$\varphi_{1}(u_{1})\neq\varphi_{1}(z)$ and
$\varphi_{1}(v_{1})\neq\varphi_{1}(z)$ for $z\in
V(G_{1})\setminus\\{u_{1},v_{1}\\}$.

Thereby, the above set-coloring
$\varphi_{1}:V(G_{1})\rightarrow\mathcal{E}_{1}$, where $\mathcal{E}_{1}$ is a
hyperedge set defined on $\Lambda=[1,p]$.

Notice that $|E(G)|\leq\frac{1}{2}p(p-1)$, and the number of subsets of the
set $\Lambda$ is $|\Lambda^{2}|=2\,^{p}-1$. This theorem can be shown by
induction, we are done. ∎

######  Theorem 28.

∗ Each connected $(p,q)$-graph $G$ admits at lest $q!$ graceful-intersection
total set-colorings defined on hyperedge sets $\mathcal{E}$ holding
$[1,q]=\bigcup_{e\in\mathcal{E}}e$ true.

###### Proof.

We take a permutation $u_{1}v_{1},u_{2}v_{2},\dots,u_{q}v_{q}$ of edges of the
connected $(p,q)$-graph $G$, and define an _edge labeling_
$f:E(G)\rightarrow\Lambda=[1,q]$ such that $f(u_{i}v_{i})=i$ for $i\in[1,q]$.
By the VSET-coloring algorithm introduced in the proof of Theorem 22, we
obtain a set-coloring $F:V(G)\rightarrow\mathcal{E}$ such that each edge
$u_{i}v_{i}$ is colored with $F(u_{i}v_{i})=\\{f(u_{i}v_{i})\\}$, and
$F(x)=\\{f(xy):y\in N(x)\\}$ for each vertex $x\in V(G)$, as well as
$F(E(G))=\mathcal{E}$ holding $F(u_{i}v_{i})\supseteq F(u_{i})\cap
F(v_{i})\neq\emptyset$ and $\Lambda=\bigcup_{e\in\mathcal{E}}e$. Clearly,
there are $q!$ permutations
$u_{i_{1}}v_{i_{1}},u_{i_{2}}v_{i_{2}},\dots,u_{i_{q}}v_{i_{q}}$ of edges
$u_{1}v_{1},u_{2}v_{2},\dots,u_{q}v_{q}$ of $G$, we are done. ∎

######  Theorem 29.

∗ Each tree $T$ of $q$ edges admits a graceful-intersection total set-labeling
$F:V(T)\rightarrow\mathcal{E}\subseteq[0,q]^{2}$ with
$\bigcup_{e_{i}\in\mathcal{E}}e_{i}=[1,q]$, then the tree $T$ contains an
independent vertex set $X$ so that the vertex color set $\\{e=F(x):x\in X\\}$
is just a perfect hypermatching $\mathcal{M}\subset\mathcal{E}$, and
$\bigcup_{e\in\mathcal{M}}e=[1,q]$.

###### Proof.

If $T$ is a star $K_{1,n}$, the result of the theorem stands up. By induction,
we have a tree $T-u$ of $(q-1)$ edges by removing randomly a leaf $u\in L(T)$,
so the leaf-removed tree $T-u$ admits a graceful-intersection total set-
labeling
$F\,^{\prime}:V(T-u)\rightarrow\mathcal{E}\,^{\prime}\subseteq[0,q-1]^{2}$
with $\bigcup_{e_{i}\in\mathcal{E}\,^{\prime}}e_{i}=[1,q]$, and the hyperedge
set $\mathcal{E}\,^{\prime}$ contains a perfect hypermatching
$\\{M\,^{\prime}_{1},M\,^{\prime}_{2},\dots,M\,^{\prime}_{a}\\}=\mathcal{M}\,^{\prime}\subset\mathcal{E}\,^{\prime}$
with $M\,^{\prime}_{i}\cap M\,^{\prime}_{j}=\emptyset$ for $i\neq j$. Suppose
that the leaf $u$ is adjacent with $v$ in $T$, that is, $uv\in E(T)$. We
discuss the following two cases:

Case 1. If $F\,^{\prime}(v)\in\mathcal{M}\,^{\prime}$, we define a set-
coloring $F$ for the tree $T$ as: $F(w)=F\,^{\prime}(w)$ for
$w\in[V(T)\setminus\\{u,v\\}]\cup[E(T)\setminus\\{uv\\}]$, since
$V(T)\setminus\\{u,v\\}\subset V(T-u)$ and $E(T)\setminus\\{uv\\}\subset
E(T-u)$, next we set $F(v)=F\,^{\prime}(v)\cup\\{q\\}$, $F(uv)=\\{q\\}$ and
$F(u)=\\{q\\}$. Thereby, $F(V(T))=\mathcal{E}$ holds
$[1,q]=\bigcup_{e_{i}\in\mathcal{E}}e_{i}$ is a hyperedge set defined on
$[1,q]$, and $\mathcal{M}\subset\mathcal{E}$ is a perfect hypermatching, where

$\mathcal{M}=[\mathcal{M}\,^{\prime}\setminus\\{F\,^{\prime}(v)\\}]\cup[F\,^{\prime}(v)\cup\\{q\\}]=\\{M_{1},M_{2},\dots,M_{a}\\}$

with $M_{i}\cap M_{j}=\emptyset$ for $i\neq j$.

Case 2. If $F\,^{\prime}(v)\not\in\mathcal{M}\,^{\prime}$, we define a set-
coloring $F$ for the tree $T$ by setting $F(w)=F\,^{\prime}(w)$ for
$w\in[V(T)\setminus\\{u\\}]\cup[E(T)\setminus\\{uv\\}]$, and $F(uv)=\\{q\\}$
and $F(u)=\\{q\\}$. Moreover, $\mathcal{M}=\mathcal{M}\,^{\prime}\cup\\{q\\}$
is a perfect hypermatching of the hyperedge set $\mathcal{E}=F(V(T))$, where
$\mathcal{M}=\\{M\,^{\prime}_{1},M\,^{\prime}_{2},\dots,M\,^{\prime}_{a},\\{q\\}\\}$.

We have shown the theorem. ∎

######  Theorem 30.

∗ If a tree $T$ of $q$ edges admits a set-ordered graceful labeling $f$ with
$\max f(X)<\min f(Y)$ for the bipartition $(X,Y)$ of $V(T)$ (refer to
Definition 6), then this set-ordered graceful labeling $f$ induces a graceful-
intersection total set-labeling
$F:V(T)\rightarrow\mathcal{E}^{*}\subseteq[0,q]^{2}$ with
$\bigcup_{e_{i}\in\mathcal{E}^{*}}e_{i}=[1,q]$, such that two vertex color
sets $M_{X}=\\{e=F(x):x\in X\\}$ and $M_{Y}=\\{e\,^{\prime}=F(y):y\in Y\\}$
are two perfect hypermatchings of the set-colored tree $T$ holding $M_{X}\cup
M_{Y}=\mathcal{E}^{*}$ and $M_{X}\cap M_{Y}=\emptyset$ true.

###### Proof.

Since $F:V(T)\rightarrow\mathcal{E}^{*}\subseteq[0,q]^{2}$ by the hypothesis
of the theorem, we have $\bigcup_{x\in X}F(x)=[1,q]$, and moreover
$f(E(T))=[1,q]$ and each edge $x_{i}y_{j}\in E(T)$ holds $x_{i}\in X$ and
$y_{j}\in Y$, which means $F(x)\cap F(x\,^{\prime})=\emptyset$, that is,
$M_{X}=\\{e=F(x):x\in X\\}$ is a perfect hypermatching. By the same way,
$M_{Y}=\\{e\,^{\prime}=F(y):y\in Y\\}$ is a perfect hypermatching too. ∎

######  Problem 12.

Characterize trees admitting set-ordered graceful labelings by means of
perfect hypermatchings generated from graceful-intersection total set-
labelings.

##  4 Algorithms for producing set-colorings

###  4.1 PSCS-algorithms

For producing set-colorings (PSCS) of graphs, we introduce the following
methods in terms of algorithmic representations.

PSCS-algorithm-1. If $T$ is a tree admitting a $W$-type coloring or a $W$-type
labeling $f$ holding $f(uv)\neq f(xy)$ for any pair of edges $uv$ and $xy$ of
$T$, and $|f(V(T))|=|V(T)|$, then we have:

Step 1.1. Apply the VSET-coloring algorithm to $T$ first, such that $T$ admits
a $W$-type set-coloring $F_{1}$ induced by $f$, and each leaf $w$ of $T$ is
colored with $F_{1}(w)$ holding $|F_{1}(w)\cap F_{1}(z)|=1$, where the vertex
$z$ is adjacent with $w$ in $T$, and $F_{1}(x)\neq F_{1}(u)$ for two distinct
vertices $x,u\in V(T)$ since $f(uv)\neq f(xy)$ for any pair of edges $uv$ and
$xy$ of $T$.

Step 1.2. Do the VSET-coloring algorithm to $T$ once time, here, the tree $T$
admits a $W$-type set-coloring $F_{2}$ induced by $F_{1}$ such that each each
leaf $w$ of $T$ and its adjacent vertex $z$ are colored with $F_{2}(w)$ and
$F_{2}(z)$ that hold $|F_{2}(w)\cap F_{2}(z)|\geq 2$, clearly, $F_{2}(x)\neq
F_{2}(u)$ for two distinct vertices $x,u\in V(T)$ since $f(uv)\neq f(xy)$ for
any pair of edges $uv$ and $xy$ of $T$.

Step 1.$k$. After $k$ times of doing the VSET-coloring algorithm to the tree
$T$, we get a $W$-type set-coloring $F_{k}$ of $T$ and $|F_{k}(w)\cap
F_{k}(z)|\geq k$ for each leaf $w$ and its adjacent vertex $z$. Suppose that
the diameter $D(T)=m$, then $|F_{k}(w)\cap F_{k}(z)|\geq
k=\lfloor\frac{m}{2}\rfloor$ for each leaf $w$ and its adjacent vertex $z$, as
well as $F_{k}(x)\neq F_{k}(u)$ for two distinct vertices $x,u\in V(T)$.

See trees $D_{1},D_{2},D_{3},D_{4}$ shown in Fig.18 and Fig.19 for
understanding the PSCS-algorithm-1. Moreover, $F_{k}(V(T))=\mathcal{E}_{k}$ is
a _hyperedge set_ define on the set $\Lambda_{k}=f(V(T))$.

Figure 18: (a) A tree $D_{1}$ admits a graceful labeling $f$; (b) the tree
$D_{2}$ admits a graceful set-coloring $F_{1}$ induced by $f$ and the VSET-
coloring algorithm.
Figure 19: (c) The tree $D_{3}$ admits a graceful set-coloring $F_{2}$ induced
by the VSET-coloring algorithm and the graceful set-coloring $F_{1}$ of the
tree $D_{2}$ shown in Fig.18; (d) the tree $D_{4}$ admits a graceful set-
coloring $F_{3}$ induced by the VSET-coloring algorithm and the graceful set-
coloring $F_{2}$ of the tree $D_{3}$.

PSCS-algorithm-2. Suppose that a tree $H$ admits a $W$-type coloring or a
$W$-type labeling $g$ with $g(uv)\neq g(xy)$ for any pair of edges $uv$ and
$xy$ of $H$, and $|g(V(H))|=|V(H)|=\Lambda$.

Firstly, by the method introduced in the proof of Theorem 26, we define a
$W$-type total set-labeling $F$ of $H$ in the following way:
$F(x)=\\{g(xy):y\in N(x)\\}$ for $x\in V(H)$, where $N(x)$ is the set of
neighbors of the vertex $x$, and $F(uv)=\\{f(uv)\\}$ for each edge $uv\in
E(H)$, so

$F(x)=\\{g(xy):y\in N(x)\\}\neq\\{g(wz):z\in N(w)\\}=F(w)$

for any two vertices $x,w\in V(H)$ based on the edge color set $g(E(T))$, then
$F(V(H))=\mathcal{E}$ is a hyperedge set define on the set $\Lambda=g(V(H))$.

Secondly, we do the VSET-coloring algorithm to the tree $H$ admitting the
$W$-type total set-labeling $F$ for more complex set-colorings.

PSCS-algorithm-3. Suppose that a connected $(p,q)$-graph $G$ contains at least
a cycle and admits $W$-type labeling or a $W$-type coloring $h$ satisfying
$h(uv)\neq h(xy)$ for any pair of distinct edges $uv$ and $xy$ of $G$.

Step 3.1. Do the vertex-splitting operation to the connected $(p,q)$-graph $G$
for getting a tree $T_{G}$ of $(q+1)$ vertices, first, we select randomly an
edge $xy$ in a cycle $C$ of $G$, and vertex-split $x$ into two vertices
$x\,^{\prime}$ and $x\,^{\prime\prime}$, such that $N(x)=N(x\,^{\prime})\cup
N(x\,^{\prime\prime})$ with $N(x\,^{\prime})\cap
N(x\,^{\prime\prime})=\emptyset$ and cardinality $|N(x\,^{\prime})|=1$, so the
resultant graph $G_{1}$ is connected, and define a total coloring $h_{1}$ for
$G_{1}$ by setting $h_{1}(w)=h(w)$ for $w\in
V(G-\\{x\,^{\prime},x\,^{\prime\prime}\\})\cup
E(G-\\{x\,^{\prime},x\,^{\prime\prime}\\})$, and $h_{1}(x\,^{\prime})=h(x)$,
$h_{1}(x\,^{\prime\prime})=h(x)$, as well as $h_{1}(x\,^{\prime}y)=h(xy)$ for
$y\in N(x\,^{\prime})$ and $h_{1}(ux\,^{\prime\prime})=h(ux)$ for $u\in
N(x\,^{\prime\prime})$. Go on in this way, after $q-p+1$ times, we get the
desired tree $T_{G}$ of $(q+1)$ vertices admitting a $W$-type coloring
$h_{q-p+1}$ satisfying $h_{q-p+1}(uv)\neq h_{q-p+1}(xy)$ for any pair of
distinct edges $uv,xy\in E(T_{G})$. See examples shown in Fig.20 (a) and (b).

Figure 20: (a) A non-tree graph $G$ admitting a graceful labeling; (b) a tree
$G_{1}$ obtained from $G$ by dong the vertex-splitting operation; (c) the tree
$G_{2}$ admitting a graceful-type set-coloring s.t.$R_{est}(2)$, where
$G_{2}\cong G_{1}$.

Step 3.2. Define a set-coloring $F$ for the tree $T_{G}$
s.t.$R_{est}(m+1)=\\{c_{i}\\}^{m}_{i=0}$ by doing the VSET-coloring algorithm
to $T_{G}$ several times, such that each edge is colored with $F(uv)$ holding
$c_{0}:F(uv)\supseteq F(u)\cap F(v)\neq\emptyset$, and one $c_{j}$ holds
$a^{j}_{uv}=|a^{j}_{u}-a^{j}_{v}|$ for some $a^{j}_{u}\in F(u)$ and
$a^{j}_{v}\in F(v)$, that is,

$F(uv)=\big{[}F(u)\cap
F(v)\big{]}\cup\big{\\{}a^{j}_{uv}=|a^{j}_{u}-a^{j}_{v}|:j\in[1,m]\big{\\}}$

with $R_{est}(m+1)=\\{c_{i}\\}^{m}_{i=0}$. See a tree $G_{3}$ shown in Fig.20
(c) for understanding this process.

Step 3.3. Let
$S^{*}=\\{j_{1},j_{2},\dots,j_{s}\\}=\Lambda\setminus\\{F(x):x\in
V(T_{G})\\}$, where $\Lambda=[a,b]$ with integers $a,b$ subject to $0\leq
a\leq b$. Making a new set-coloring $F\,^{\prime}$ by setting
$F\,^{\prime}(uv)=F(uv)$ for $uv\in E(T_{G})$, and each vertex $x\in V(T_{G})$
is colored with $F\,^{\prime}(x)=F(x)$ or $F\,^{\prime}(x)=F(x)\cup S^{*}_{x}$
with $S^{*}_{x}=\\{j_{a},j_{b},\dots,j_{l}\\}\subseteq S^{*}$, such that
$F\,^{\prime}(V(T_{G}))=\Lambda$ and $F\,^{\prime}(x)\neq F\,^{\prime}(w)$ for
distinct vertices $x,w\in V(T_{G})$. See the vertex colors of a graph
$G_{yper}$ shown in Fig.21.

Step 3.4. Define a set-coloring $F^{*}$
s.t.$R^{*}_{est}(m+1)=\\{c^{*}_{i}\\}^{m}_{i=0}$ in the following way:
$F^{*}(y)=F\,^{\prime}(y)$ for $y\in V(T_{G})$,

$F^{*}(uv)=\big{[}F^{*}(u)\cap
F^{*}(v)\big{]}\cup\\{a^{i}_{uv}=|a^{i}_{u}-a^{i}_{v}|:a^{i}_{u}\in
F^{*}(u),a^{i}_{v}\in F^{*}(v),i\in[1,m]\\}$

where $R^{*}_{est}(m+1)=\\{c^{*}_{i}\\}^{m}_{i=0}$ consisted of
$c^{*}_{0}:F^{*}(uv)\supseteq F^{*}(u)\cap F^{*}(v)\neq\emptyset$, and
$c^{*}_{i}:a^{i}_{uv}=|a^{i}_{u}-a^{i}_{v}|$ for some $a^{i}_{u}\in F^{*}(u)$
and $a^{i}_{v}\in F^{*}(v)$ with $i\in[1,m]$. The graph $G_{yper}$ shown in
Fig.21 admits such a set-coloring $F^{*}$
s.t.$R^{*}_{est}(m+1)=\\{c^{*}_{i}\\}^{m}_{i=0}$. Thereby,
$F^{*}(V(T_{G}))=\mathcal{E}^{*}$ is a hyperedge set defined on
$\Lambda=[a,b]$.

After vertex-coinciding $u=A_{1}\odot A_{2}$, $v=B_{1}\odot B_{2}\odot B_{2}$,
$w=C_{1}\odot C_{2}$ and $z=D_{1}\odot D_{2}$ of $G_{yper}$ shown in Fig.21,
we obtain the original connected graph $G$ admitting a set-coloring
$\varphi^{*}$ induced by the set-coloring $F^{*}$ of the tree $G_{yper}$,
where

$\varphi^{*}(u)=F^{*}(A_{1})\cup F^{*}(A_{2}),\varphi^{*}(v)=F^{*}(B_{1})\cup
F^{*}(B_{2})\cup F^{*}(B_{3}),\varphi^{*}(w)=F^{*}(C_{1})\cup F^{*}(C_{2})$

and $\varphi^{*}(z)=F^{*}(D_{1})\cup F^{*}(D_{2})$, and each $w$ of other
edges and vertices of $G$ is colored with $\varphi^{*}(w)=F^{*}(w)$.

Figure 21: $G_{\textrm{yper}}$ is a subgraph of some intersected-graph
admitting the set-coloring $F^{*}$.

PSCS-algorithm-4. By Definition 9, an edge-odd-graceful graph base
$\textbf{B}=(G_{1},G_{2},\dots$, $G_{m})$ admits an edge-odd-graceful vertex-
matching labeling $F=\uplus^{m}_{i=1}f_{i}$, where each connected
$(p_{i},q_{i})$-graph $G_{i}$ admits a labeling $f_{i}$ holding

$f_{i}(E(G_{i}))=\\{f_{i}(u_{j}v_{j})=|f_{i}(u_{j})-f_{i}(v_{j})|:~{}u_{j}v_{j}\in
E(G_{i})\\}=[1,2q_{i}-1]^{o}$

and $\bigcup^{m}_{i=1}f_{i}(V(G_{i}))=[0,M]$ with $m\geq 2$. Then we have a
graph $G^{*}$, denoted as $\langle\odot\cup\rangle^{m}_{i=1}G_{i}$, obtained
by vertex-coinciding those vertices of $G_{1},G_{2},\dots,G_{m}$ colored with
the same color into one vertex, and union all graphs that have no vertices
colored with the same color together. Now, we define a set-coloring for
$G^{*}$ in the following process:

Step 4.1. If $G_{i}\in\textbf{B}$ is a tree, then we get a set-coloring
$F_{i}$ of $G_{i}$ by the PSCS-algorithm-1, such that
$F_{i}(V(G_{i}))=\mathcal{E}_{i}$ defined on a set $\Lambda_{i}$.

Step 4.2. If $G_{j}\in\textbf{B}$ is not a tree, then there is a set-coloring
$F_{j}$ of $G_{j}$ obtained by the PSCS-algorithm-3, like the set-coloring
$\varphi^{*}$ of $G$, such that $F_{j}(V(G_{j})=\mathcal{E}_{j}$ defined on a
set $\Lambda_{j}$.

Step 4.3. We define a set-coloring $\theta$ of the graph
$G^{*}=\langle\odot\cup\rangle^{m}_{i=1}G_{i}$ in the following way:

(i) $\theta(w)=\bigcup^{p}_{i=1}F_{k_{i}}(w_{k_{i}})$ if a vertex $w$ of
$G^{*}$ is $w=\odot^{p}_{i=1}w_{k_{i}}$ obtained by the vertex $w_{k_{i}}$ of
graphs $G_{k_{i}}$ of the base B with $i\in[1,p]$.

(ii) If an edge $wz$ of $G^{*}$ is $wz=\ominus^{s}_{r=1}w_{j_{r}}z_{j_{r}}$
generated by some edges $w_{j_{r}}z_{j_{r}}$ of graphs $G_{j_{r}}$ of the base
B for $r\in[1,s]$, then we color it as
$\theta(wz)=\bigcup^{s}_{r=1}F_{j_{r}}(w_{j_{r}}z_{j_{r}})$.

(iii) For other $G^{*}$’s vertices $x$ and edges $xy$ that do not participate
into vertex-coincided vertices $w=\odot^{p}_{i=1}w_{k_{i}}$ and edge-coincided
edges $wz=\ominus^{s}_{r=1}w_{j_{r}}z_{j_{r}}$, we color $\theta(x)=F_{i}(x)$
if $x\in V(G_{i})$ and $\theta(xy)=F_{j}(xy)$ if $xy\in E(G_{j})$.

Thereby, $\theta(V(G^{*}))=\mathcal{E}^{*}=\bigcup^{m}_{j=1}\mathcal{E}_{j}$
and $\Lambda^{*}=\bigcup_{e\in\mathcal{E}^{*}}e$ for
$\Lambda^{*}=\bigcup^{m}_{j=1}\Lambda_{j}$, such that $G^{*}$ is a subgraph of
the intersected-graph of the hypergraph
$\mathcal{H}_{yper}=(\Lambda^{*},\mathcal{E}^{*})$.

###  4.2 Set-colorings with multiple intersections

######  Definition 24.

∗ Let $\mathcal{E}$ be a set of subsets of a finite set $\Lambda$ such that
each hyperedge $e\in\mathcal{E}$ satisfies $e\neq\emptyset$ and corresponds
another hyperedge $e\,^{\prime}\in\mathcal{E}$ holding $e\cap
e\,^{\prime}\neq\emptyset$, as well as $\Lambda=\bigcup_{e\in\mathcal{E}}e$.
Suppose that a connected graph $H$ admits a _total set-labeling_ $\pi:V(H)\cup
E(H)\rightarrow\mathcal{E}$ with $\pi(w)\neq\pi(z)$ for distinct vertices
$w,z\in V(H)$, and the edge color set $\pi(uv)$ for each edge $uv\in E(G)$
holds $\pi(uv)\neq\pi(uw)$ for $w\in N(u)$ and each vertex $u\in V(G)$. There
are the following intersected-type restrictive conditions:

  1. Chyper-1.

$\pi(u)\cap\pi(v)\subseteq\pi(uv)$ and $\pi(u)\cap\pi(v)\neq\emptyset$ for
each edge $uv\in E(G)$.

  2. Chyper-2.

$\pi(u)\cap\pi(v)\subseteq\pi(uv)$ and $|\pi(u)\cap\pi(v)|\geq r\geq 2$ for
each edge $uv\in E(G)$.

  3. Chyper-3.

$\pi(uv)\cap\pi(u)\neq\emptyset$ and $\pi(uv)\cap\pi(v)\neq\emptyset$ for each
edge $uv\in E(G)$.

  4. Chyper-4.

$\pi(uv)\cap\pi(uw)\neq\emptyset$ for $w\in N(u)$ and each vertex $u\in V(G)$.

  5. Chyper-5.

$\pi(uv)\cap\pi(uw)=\emptyset$ for $w\in N(u)$ and each vertex $u\in V(G)$.

Then we have:

  1. Cgraph-1.

If Chyper-1 holds true, $G$ is called a _subintersected-graph_ and $\pi$ is
called a _subintersected total set-labeling_ of $G$.

  2. Cgraph-2.

If Chyper-2 holds true, $G$ is called a _$r$ -rank subintersected-graph_ and
$\pi$ is called a _$r$ -rank subintersected total set-labeling_ of $G$.

  3. Cgraph-3.

If Chyper-1 and Chyper-3 hold true, $G$ is called an _intersected-edge-
intersected graph_ and $\pi$ is called an _intersected-edge-intersected total
set-labeling_ of $G$.

  4. Cgraph-4.

If Chyper-2 and Chyper-3 hold true, $G$ is called a _$r$ -rank intersected-
edge-intersected graph_ and $\pi$ is called a _$r$ -rank intersected-edge-
intersected total set-labeling_ of $G$.

  5. Cgraph-5.

$G$ is called an _edge-intersected graph_ if Chyper-3 holds true, and $\pi$ is
called an _edge-intersected total set-labeling_ of $G$.

  6. Cgraph-6.

If Chyper-3 and Chyper-4 hold true, then $G$ is called an _adjacent edge-
intersected graph_ , and $\pi$ is called an _adjacent edge-intersected total
set-labeling_ of $G$.

  7. Cgraph-7.

If Chyper-3 and Chyper-5 hold true, then $G$ is called an _individual edge-
intersected graph_ , and $\pi$ is called an _individual edge-intersected total
set-labeling_ of $G$. $\square$

######  Problem 13.

Since $\Lambda=\bigcup_{e\in\mathcal{E}}e$ for a hyperedge set $\mathcal{E}$
based on a finite set $\Lambda$, and a connected graph $G$ admits a _$W$
-type-intersected total set-labeling_ $F$ defined in Definition 24,
characterize hyperedge sets $\mathcal{E}$ and estimate extremum number
$\min\big{\\{}\max\Lambda:\Lambda=\bigcup_{e\in\mathcal{E}}e\big{\\}}$ when
each $\Lambda$ is a finite nonnegative integer set.

######  Theorem 31.

Each tree admits one of subintersected total set-labeling, intersected-edge-
intersected total set-labeling, edge-intersected total set-labeling, adjacent
edge-intersected total set-labeling and individual edge-intersected total set-
labeling defined in Definition 24.

###### Proof.

By Theorem 25, a tree $T$ admits a gracefully total coloring $f$ with
$f(V(T))\subseteq[0,q]$ and $f(E(T))=[1,q]$, where $|E(T)|=q$. Let
$\Lambda=[1,q]$ in the following deduction.

F-1. We define a total set-labeling $F_{1}$ as: $F_{1}(x)=\\{f(xv):v\in
N(x)\\}$ for each vertex $x\in V(T)$, and each edge $uv$ of $E(T)$ is colored
with $F_{1}(uv)=\\{f(uv)\\}$ and for each edge $uv\in E(T)$. Clearly,
$F_{1}(x)\neq F_{1}(y)$ for distinct vertices $x,y\in V(T)$ and
$[1,q]=F_{1}(V(T))$, since $f(E(T))=\Lambda$. So, $F_{1}(V(T))$ is a
_hyperedge set_ $\mathcal{E}_{1}$ defined on $\Lambda$, and moreover
$\\{f(uv)\\}=F_{1}(u)\cap F_{1}(v)\subseteq F_{1}(uv)$. Thereby, we claim that
$F_{1}$ is a _subintersected total set-labeling_ of $T$ according to
Definition 24, and $T$ is a subintersected-graph, as a subgraph of the
intersected-graph of a hypergraph
$\mathcal{H}_{yper}=(\Lambda,\mathcal{E}_{1})$.

F-2. Notice that $F_{1}(uv)\cap F_{1}(u)=\\{f(uv)\\}$ and $F_{1}(uv)\cap
F_{1}(v)=\\{f(uv)\\}$, so $F_{1}$ is an _intersected-edge-intersected total
set-labeling_ defined in Definition 24, and $T$ is an intersected-edge-
intersected graph.

F-3. We have $F_{1}$ to be an _edge-intersected total set-labeling_ and $T$ to
be an edge-intersected graph because $F_{1}(uv)\cap F_{1}(u)=\\{f(uv)\\}$ and
$F_{1}(uv)\cap F_{1}(v)=\\{f(uv)\\}$ from Definition 24.

F-4. Notice that (i) $F_{1}(uv)\cap F_{1}(uw)=\emptyset$ for $w\in N(u)$ and
each vertex $u\in V(T)$; (ii) and $F_{1}(uv)\cap F_{1}(u)=\\{f(uv)\\}$ and
$F_{1}(uv)\cap F_{1}(v)=\\{f(uv)\\}$. We say that $T$ is an individual edge-
intersected graph admitting an _individual edge-intersected total set-
labeling_ $F_{1}$.

F-5. Let $L(T_{i})$ be the leaf-set of leaves of the tree $T_{i}$, where a
leaf is a vertex having degree one. So, we have trees $T_{i+1}=T_{i}-L(T_{i})$
for $i\in[1,m]$ with $m=\big{\lfloor}\frac{D(T)+1}{2}\big{\rfloor}-1$, where
$T_{1}=T$ and $D(T)$ is the diameter of $T$. And, for $i\in[1,m]$, each leaf-
set $L(T_{i})$ can be cut into subsets
$L_{r}(T_{i})=\\{w_{i,r,1},w_{i,r,2},\dots,w_{i,r,d(v_{i,r})}\\}$ for
$r\in[1,A_{i}]$, $w_{i,r,j}\in N(v_{i,r})$ for $j\in[1,d(v_{i,r})]$, where
$v_{i,r}$ is not a leaf of $T_{i}$ and has its own degree
$d(v_{i,r})=\textrm{deg}_{T}(v_{i,r})\geq 2$.

We define a new total set-labelling $F_{2}$ for $T$ as follows:
$F_{2}(x)=F_{1}(x)$ for each vertex $x\in V(T)$. For coloring edges of $T$,
there are the following cases:

Case 1. If $T$ is a star $K_{1,n}$ with its center vertex $x_{0}$ and leaf set
$L(K_{1,n})=\\{x_{1},x_{2},\dots,x_{n}\\}$, we set
$F_{2}(x_{0}x_{i})=\bigcup^{n}_{j=1}F_{1}(x_{0}x_{j})$ for each $i\in[1,n]$.
So, $F_{2}$ is an adjacent edge-intersected total set-labeling of $K_{1,n}=T$.

Case 2. If the diameter $D(T)\geq 3$. We present the following algorithm:

Step C2.1. For the leaf set $L(T_{1})$ and $r\in[1,A_{1}]$, we color each edge
$w_{1,r,j}v_{1,r}$ with

$F_{2,1}(w_{1,r,j}v_{1,r})=F_{1}(v_{1,r}z_{1,r})\bigcup\left[\bigcup^{d(v_{1,r})}_{j=1}F_{1}(w_{1,r,j}v_{1,r})\right]$
(21)

for $j\in[1,d(v_{i,r})]$, and
$F_{2,1}(w_{1,r,j}v_{1,r})=F_{2,1}(v_{1,r}z_{1,r})$, where $z_{1,r}\not\in
L(T_{1})$, however, $v_{1,r}\in L(T_{2})$ and $z_{1,r}\in L(T_{3})$.

Step C2.2. For leaf set $L(T_{2})$ and $r\in[1,A_{2}]$, notice that
$v_{1,r}\in L(T_{2})$ for $r\in[1,A_{1}]$, so $v_{1,r}\in
L_{r}(T_{2})=\\{w_{2,r,1},w_{2,r,2},\dots,w_{2,r,d(v_{2,r})}\\}$, and
$v_{1,r}=w_{2,r,s}$ for some $s$ and $z_{1,r}=v_{2,r}$, then each edge
$w_{2,r,j}v_{2,r}$ is colored with

$F_{2,2}(w_{2,r,j}v_{2,r})=F_{2,1}(v_{1,r}z_{1,r})\bigcup
F_{1}(v_{2,r}z_{2,r})\bigcup\left[\bigcup^{d(v_{2,r})}_{j=1,j\neq
s}F_{1}(w_{2,r,j}v_{2,r})\right]$ (22)

for $j\in[1,d(v_{2,r})]$, and
$F_{2,2}(w_{2,r,j}v_{2,r})=F_{2,2}(v_{2,r}z_{2,r})$, where $z_{2,r}\not\in
L(T_{2})$, however, $v_{2,r}\in L(T_{3})$ and $z_{2,r}\in L(T_{4})$.

Step C2.k. For leaf set $L(T_{k})$ and $r\in[1,A_{k}]$, we have leaves
$v_{k-1,r}\in L(T_{k})$ for $r\in[1,A_{k-1}]$, and $v_{k-1,r}\in
L_{r}(T_{k})=\\{w_{k,r,1},w_{k,r,2},\dots,w_{k,r,d(v_{k,r})}\\}$, as well as
$v_{k-1,r}=w_{k,r,s}$ for some $s$ and $z_{k-1,r}=v_{k,r}$, and we color each
edge $w_{k,r,j}v_{k,r}$ with

$F_{2,k}(w_{k,r,j}v_{k,r})=F_{2,k-1}(v_{k-1,r}z_{k-1,r})\bigcup
F_{1}(v_{k,r}z_{k,r})\bigcup\left[\bigcup^{d(v_{k,r})}_{j=1,j\neq
s}F_{1}(w_{k,r,j}v_{k,r})\right]$ (23)

for $j\in[1,d(v_{k,r})]$, and
$F_{2,k}(w_{k,r,j}v_{k,r})=F_{2,k}(v_{k,r}z_{k,r})$, where $z_{k,r}\not\in
L(T_{k})$, however, $v_{k,r}\in L(T_{k+1})$ and $z_{2,r}\in L(T_{k+2})$.

Go on in the above procure, we meet:

(a) The last tree $T_{m}=T_{m-1}-L(T_{m-1})$ is a star $K_{1,1}$ with
$V(K_{1,1})=\\{w_{m,1,1},v_{m,1}\\}$ and $E(K_{1,1})=\\{w_{m,1,1}v_{m,1}\\}$,
we set

$F_{2,m}(w_{m,1,1}v_{m,1})=F_{1}(w_{m,1,1}v_{m,1})\cup
F_{2,m-1}(w_{m,1,1}w_{m-1,i})\cup F_{2,m-1}(v_{m,1}v_{m-1,j})$

where $w_{m-1,i},v_{m-1,j}\in L(T_{m-1})$.

(b) The last tree $T_{m}=T_{m-1}-L(T_{m-1})$ is a star $K_{1,p}$ with
$V(K_{1,p})=\\{v_{m,1},w_{m,1,q}:q\in[1,p]\\}$ and
$E(K_{1,p})=\\{v_{m,1}w_{m,1,q}:q\in[1,p]\\}$, so $w_{m,1,q}w_{m-1,j,q}\in
E(t)$ and $w_{m-1,j,q}\in L(T_{m-1})$, we color each edge $v_{m,1}w_{m,1,q}$
as

$F_{2,m}(v_{m,1}w_{m,1,q})=\left[\bigcup^{p}_{q=1}F_{2,m-1}(w_{m,1,q}w_{m-1,j,q})\right]\bigcup\left[\bigcup^{p}_{q=1}F_{1}(v_{m,1}w_{m,1,q})\right]$
(24)

for $q\in[1,p]$

Thereby, $F_{2}(xy)$ for $xy\in E(T)$ is defined as $F_{2}(xy)=F_{2,k}(xy)$ if
$x\in L(T_{k})$ and $y\in L(T_{k-1})$ for $k\in[1,m]$. It is not difficult to
see $F_{2}(uv)\cap F_{2}(uw)\neq\emptyset$ for $w\in N(u)$ and each vertex
$u\in V(T)$, so we claim that $F_{2}$ is an adjacent edge-intersected total
set-labeling of $T$, and $F_{2}(V(T))$ is a hyperedge set of a hypergraph
$\mathcal{H}_{yper}=(\Lambda,F_{2}(V(T)))$. See Fig.22 for obtaining an
adjacent edge-intersected total set-labeling of a tree.

Figure 22: An algorithm for obtaining the adjacent edge-intersected total set-
labeling $F$ of the tree $O_{1}$ shown in (a), where $F(uv)=[1,17]$ in
$O_{6}$.

Another algorithm is shown in Fig.23. We use a longest path to make an
adjacent edge-intersected total set-labeling of a tree each time. Let $T_{1}$
be a tree with diameter $D(T_{1})\geq 3$, and $T_{1}$ admit a graceful
coloring $g$ with $g(V(T_{1}))\subseteq[0,q]$ and $g(E(T_{1}))=[1,q]$, where
$|E(T_{1})|=q$. Let $\Lambda=[1,q]$,
$m=\big{\lfloor}\frac{D(T)+1}{2}\big{\rfloor}-1$.

Step 1. Define a total set-labeling $F^{*}$ as: $F^{*}(x)=\\{g(xy):y\in
N(x)\\}$ for each vertex $x\in V(T)$, and $F^{*}(uv)=\\{g(uv)\\}$ for each
edge $uv\in E(T_{1})$. Clearly, $F^{*}(x)\neq F^{*}(y)$ for distinct vertices
$x,y\in V(T_{1})$ and $F^{*}(V(T))=\Lambda$, since $g(E(T_{1}))=\Lambda$. So,