# A New Type of Graphical Passwords Based on Odd-Elegant Labelled Graphs

Authors: Hongyu Wang; Jin Xu; Mingyuan Ma; Hongyan Zhang
Journal: Security and Communication Networks
 (2018)

---

## Abstract

Graphical password (GPW) is one of various passwords used in information communication. The QR code, which is widely used in the current world, is one of GPWs. Topsnut-GPWs are new-type GPWs made by topological structures (also, called graphs) and number theory, but the existing GPWs use pictures/images almost. We design new Topsnut-GPWs by means of a graph labelling, called odd-elegant labelling. The new Topsnut-GPWs will be constructed by Topsnut-GPWs having smaller vertex numbers; in other words, they are compound Topsnut-GPWs such that they are more robust to deciphering attacks. Furthermore, the new Topsnut-GPWs can induce some mathematical problems and conjectures.


---

## Body

## 1. Introduction and Preliminary

### 1.1. Researching Background

Graphical passwords (GPWs) have been investigated for over 20 years, and many important results can be found in three surveys [1–3]. GPW schemes have been proposed as a possible alternative to text-based schemes. However, the existing GPWs have (i) no mathematical computation; (ii) more storage space; (iii) no individuality; (iv) geometric positions; (v) slow running speed; (vi) vulnerable to attack; and (vii) no transformation from lower safe level to high security. However, QR code is a successful example of GPW’ applications in mobile devices by fast, relatively reliable and other functions [4, 5]. GPWs may be accepted by users having mobile devices with touch screen [6, 7].Wang et al. show an idea of “topological structures plus number theory” for designing new-type GPWs (abbreviated as Topsnut-GPWs, [8–10]). All topological structures used in Topsnut-GPWs can be stored in a computer through ordinary algebraic matrices. And Topsnut-GPWs have no requirement of geometric positions for users and allow users to make their individual passwords rather than learning more rules they do not like and so on.How to quickly build up a large scale of Topsnut-GPWs from those Topsnut-GPWs having smaller vertex numbers? How to construct a one-key versus more-locks (one-lock versus more-keys) for some Topsnut-GPWs? And how to compute Topsnut-GPWs’ space by the basic computing unit2
n? Obviously, we need enough graphs and lots of graph coloring/labellings, and we can turn more things into Topsnut-GPWs. Let G
p be the number of graphs having p vertices. From [11], we knowp
G
p
bits
18
1787577725145611700547878190848
100
19
24637809253125004524383007491432768
114
20
645490122795799841856164638490742749440
129
21
32220272899808983433502244253755283616097664
145
22
3070846483094144300637568517187105410586657814272
161
23
559946939699792080597976380819462179812276348458981632
179
24
195704906302078447922174862416726256004122075267063365754368
197whereG
p
≈
2
b
i
t
s for p
=
18,19
,
…
,
24. It means that adding various graph labellings enables us to design tremendous Topsnut-GPWs with huge topological structures and vast of graph coloring/labellings, since there are over 150 graph labellings introduced in [12]. As a fact, Topsnut-GPWs can generate alphanumeric passwords with longer units. As an example, we take a path v
1
v
10
v
11
v
20 in Figure 6(d) to produce an alphanumeric password (1)
W
=
1
′
1816141210201
′
10
′
11517211110
′
11
′
10202011
′
20
′
111579320
′by selecting the neighbors of each vertex of these four vertices v
1
,
v
10
,
v
11, and v
20. Clearly, such password W may have longer unit in a large scale of Topsnut-GPW for meeting the need of high level security.In this article, we will apply a graph labelling called odd-elegant labelling [13]. And we will define some construction operations under odd-elegant labelling for designing our compound Topsnut-GPWs.


### 1.2. Preliminary

We use standard notation and terminology of graph theory. Graphs mentioned are loopless, with no multiple edges, undirected, connected, and finite, unless otherwise specified. Others can be found in [14]. Here, we will use A (
p
,
q
)-graph G which is one with p vertices and q edges; the symbol [
m
,
n
] stands for an integer set {
m
,
m
+
1
,
…
,
n
} for integers m and n with 0
≤
m
<
n; [
s
,
t
]
o indicating an odd-set {
s
,
s
+
2
,
…
,
t
}, where s and t both are odd integers with 1
≤
s
<
t; and [
k
,
l
]
e represents an even-set {
k
,
k
+
2
,
…
,
l
}, where k and l are both even integers with respect to 0
≤
k
<
l.Definition 1 (see [13]).
Suppose that a(
p
,
q
)-graph G admits a mapping f
:
V
(
G
)
→
[
0,2
q
-
1
] such that f
(
u
)
≠
f
(
v
) for distinct vertices u
,
v
∈
V
(
G
), and the label f
(
u
v
) of every edge u
v
∈
E
(
G
) is defined as f
(
u
v
)
=
f
(
u
)
+
f
(
v
)
(
m
o
d
2
q
) and the set of all edge labels is equal to [
1,2
q
-
1
]
o. One considers f to be anodd-elegant labelling and G to be anodd-elegant.Definition 2 (see [15]).
Suppose that a bipartite graphG receives a labelling f such that m
a
x
{
f
(
x
)
:
x
∈
X
}
<
m
i
n
{
f
(
y
)
:
y
∈
Y
}, where (
X
,
Y
) is the bipartition of vertex set V
(
G
) of G. We call f aset-ordered labelling (So-labelling for short).As shown in Figure1, there are four different examples of Definitions 1 and 2.Figure 1
(a) An odd-elegant tree; (b) an odd-elegant graph; (c) a set-ordered odd-elegant tree; (d) a set-ordered odd-elegant graph.
(a)
(b)
(c)
(d)Definition 3.
LetG
j be a (
p
j
,
q
j
)-graph with j
=
1,2. A graph G obtained by identifying each vertex x
i
,
1 of G
1 with a vertex x
i
,
2 of G
2 into one vertex x
i
=
x
i
,
1
∘
x
i
,
2 with i
∈
[
1
,
m
] is called an m
-identification graph and denoted as G
=
⨀
m
〈
G
1
,
G
2
〉; the vertices x
1
,
x
2
,
…
,
x
m are called theidentification-vertices.Moreover, them-identification graph G
=
⨀
m
〈
G
1
,
G
2
〉 defined in Definition 3 has p
1
+
p
2
-
m vertices and q
1
+
q
2 edges. One can split each identification-vertex x
i
=
x
i
,
1
∘
x
i
,
2 into two vertices x
i
,
1 and x
i
,
2 (called thesplitting-vertices) for i
∈
[
1
,
m
], such that G is split into two parts G
1 and G
2. For the purpose of convenience, the above procedure of producing am m-identification graph G
=
⨀
m
〈
G
1
,
G
2
〉 is called an m
-identification operation; conversely, the procedure of splitting G
=
⨀
m
〈
G
1
,
G
2
〉 into two parts G
1 and G
2 is named as them-splitting operation.Definition 4.
LetG
i be a connected (
p
i
,
q
)-graph with i
=
1,2, and let p
=
p
1
+
p
2
-
2. If the 2-identification (
p
,
q
)-graph G
=
⨀
2
〈
G
1
,
G
2
〉 has a mapping f
:
V
(
G
)
→
[
0
,
q
-
1
] holding the following: (i) f
(
x
)
≠
f
(
y
) for each pair of vertices x
,
y
∈
V
(
G
), (ii) f is an odd-elegant labelling of G
i with i
=
1,2, and (iii) f
V
G
1
∩
f
V
G
2
=
2 and f
(
V
(
G
1
)
)
∪
f
(
V
(
G
2
)
)
⊆
[
0
,
q
-
1
], then one calls G atwin odd-elegant graph (a TOE-graph), f aTOE-labelling, G
1 aTOE-source graph, G
2 aTOE-associated graph, and (
G
1
,
G
2
) aTOE-matching pair.We illustrate Definition4 with Figure 2. In other words, a twin odd-elegant graph G
=
⨀
2
〈
G
1
,
G
2
〉 with its TOE-source graph G
1 and TOE-associated graph G
2, where (
G
1
,
G
2
) is a TOE-matching pair.Figure 2
The formation process of Definition4.Furthermore, if eachG
i with i
=
1,2 is a connected graph in Definition 4, and the TOE-source G
1 is a bipartite connected graph having its own bipartition (
X
1
,
Y
1
) and a labelling f satisfying Definition 2, we call the 2-identification graph G
=
⨀
2
〈
G
1
,
G
2
〉 aset-ordered twin odd-elegant graph (So-TOE-graph) and f aset-ordered twin odd-elegant labelling (So-TOE-labelling). Notice that the source graph G
1 is a set-ordered odd-elegant graph by Definitions 1 and 2. In vivid speaking, a source graph and its associated graph defined in Definition 4 can be called aTOE-lock-model and aTOE-key-model ([10]), respectively.


### 1.3. Techniques for Constructing 2-Identification Graphs

The following three operations,CA-operation, edge-series operation, and base-pasted operation, will be used in this article.(O-1) CA-Operation. Suppose each graph G
k has an odd-elegant labelling f
k and V
(
G
k
)
=
{
x
l
k
:
l
=
1,2
,
…
,
|
V
(
G
k
)
|
} with k
∈
[
1
,
m
]. Clearly, for a
≠
b with a
,
b
∈
[
1
,
m
], there are vertices x
i
a
∈
V
(
G
a
) and x
j
b
∈
V
(
G
b
) such that f
a
(
x
i
a
)
=
f
b
(
x
j
b
). For example, some G
k has a vertex x
i
k such that the label f
k
(
x
i
k
)
=
0 with k
∈
[
1
,
m
]. We can combine those vertices that have the same labels into one vertex, which gives us a new graph, denoted by G
=
⨀
ϵ
〈
G
1
,
G
2
,
…
,
G
m
〉. This process is called aCA-operation on G
1
,
G
2
,
…
,
G
m.(O-2) Edge-Series Operation. Given two groups of disjoint trees G
1
r
,
G
2
r
,
…
,
G
m
r with r
=
1,2 there are vertices x
k
r
,
y
k
r
∈
V
(
G
k
r
) with k
∈
[
1
,
m
]. Joining the vertex y
j
r with the vertex x
j
+
1
r by an edge for j
∈
[
1
,
m
-
1
] produces a tree H
r (denoted by H
r
=
⊖
k
=
1
m
G
k
r) with r
=
1,2; next we let one vertex u
s
1
∈
V
(
H
1
) coincide with one vertex v
s
2
∈
V
(
H
2
) into one vertex a
s
=
u
s
1
∘
v
s
2 with s
=
1,2. The resulting graph ⨀
2
〈
H
1
,
H
2
〉 is just a 2-identification graph.(O-3) Base-Pasted Operation. Given two disjoint trees T
r (calledbase-trees) having vertices x
1
r
,
x
2
r
,
…
,
x
m
r and two groups of disjoint trees G
1
r
,
G
2
r
,
…
,
G
m
r with r
=
1,2, we let a vertex u
k
r
∈
V
(
G
k
r
) coincide with the vertex x
k
r
∈
V
(
T
r
) into one vertex u
k
r
∘
x
k
r for k
∈
[
1
,
m
] such that the resulting tree F
r (i.e., F
r
=
T
r
⨀
k
=
1
m
G
k
r) has V
(
F
r
)
=
⋃
k
=
1
m
V
(
G
k
r
), E
(
F
r
)
=
(
⋃
k
=
1
m
E
(
G
k
r
)
)
∪
E
(
T
r
) for r
=
1,2. We overlap one vertex w
s
1
∈
V
(
F
1
) with one vertex z
s
2
∈
V
(
F
2
) into one vertex b
s
=
w
s
1
∘
z
s
2 with s
=
1,2 to build up a 2-identification graph F
=
⨀
2
〈
F
1
,
F
2
〉 holding V
(
F
1
)
∩
V
(
F
2
)
=
{
a
1
,
a
2
} and E
(
F
)
=
E
(
F
1
)
∪
E
(
F
2
)
.In the following, we give the diagrams withm
=
2 for edge-series operation and base-pasted operation, shown in Figures 3 and 4, respectively.Figure 3
A scheme of the edge-series operation.Figure 4
A scheme of the base-pasted operation.


## 1.1. Researching Background

Graphical passwords (GPWs) have been investigated for over 20 years, and many important results can be found in three surveys [1–3]. GPW schemes have been proposed as a possible alternative to text-based schemes. However, the existing GPWs have (i) no mathematical computation; (ii) more storage space; (iii) no individuality; (iv) geometric positions; (v) slow running speed; (vi) vulnerable to attack; and (vii) no transformation from lower safe level to high security. However, QR code is a successful example of GPW’ applications in mobile devices by fast, relatively reliable and other functions [4, 5]. GPWs may be accepted by users having mobile devices with touch screen [6, 7].Wang et al. show an idea of “topological structures plus number theory” for designing new-type GPWs (abbreviated as Topsnut-GPWs, [8–10]). All topological structures used in Topsnut-GPWs can be stored in a computer through ordinary algebraic matrices. And Topsnut-GPWs have no requirement of geometric positions for users and allow users to make their individual passwords rather than learning more rules they do not like and so on.How to quickly build up a large scale of Topsnut-GPWs from those Topsnut-GPWs having smaller vertex numbers? How to construct a one-key versus more-locks (one-lock versus more-keys) for some Topsnut-GPWs? And how to compute Topsnut-GPWs’ space by the basic computing unit2
n? Obviously, we need enough graphs and lots of graph coloring/labellings, and we can turn more things into Topsnut-GPWs. Let G
p be the number of graphs having p vertices. From [11], we knowp
G
p
bits
18
1787577725145611700547878190848
100
19
24637809253125004524383007491432768
114
20
645490122795799841856164638490742749440
129
21
32220272899808983433502244253755283616097664
145
22
3070846483094144300637568517187105410586657814272
161
23
559946939699792080597976380819462179812276348458981632
179
24
195704906302078447922174862416726256004122075267063365754368
197whereG
p
≈
2
b
i
t
s for p
=
18,19
,
…
,
24. It means that adding various graph labellings enables us to design tremendous Topsnut-GPWs with huge topological structures and vast of graph coloring/labellings, since there are over 150 graph labellings introduced in [12]. As a fact, Topsnut-GPWs can generate alphanumeric passwords with longer units. As an example, we take a path v
1
v
10
v
11
v
20 in Figure 6(d) to produce an alphanumeric password (1)
W
=
1
′
1816141210201
′
10
′
11517211110
′
11
′
10202011
′
20
′
111579320
′by selecting the neighbors of each vertex of these four vertices v
1
,
v
10
,
v
11, and v
20. Clearly, such password W may have longer unit in a large scale of Topsnut-GPW for meeting the need of high level security.In this article, we will apply a graph labelling called odd-elegant labelling [13]. And we will define some construction operations under odd-elegant labelling for designing our compound Topsnut-GPWs.


## 1.2. Preliminary

We use standard notation and terminology of graph theory. Graphs mentioned are loopless, with no multiple edges, undirected, connected, and finite, unless otherwise specified. Others can be found in [14]. Here, we will use A (
p
,
q
)-graph G which is one with p vertices and q edges; the symbol [
m
,
n
] stands for an integer set {
m
,
m
+
1
,
…
,
n
} for integers m and n with 0
≤
m
<
n; [
s
,
t
]
o indicating an odd-set {
s
,
s
+
2
,
…
,
t
}, where s and t both are odd integers with 1
≤
s
<
t; and [
k
,
l
]
e represents an even-set {
k
,
k
+
2
,
…
,
l
}, where k and l are both even integers with respect to 0
≤
k
<
l.Definition 1 (see [13]).
Suppose that a(
p
,
q
)-graph G admits a mapping f
:
V
(
G
)
→
[
0,2
q
-
1
] such that f
(
u
)
≠
f
(
v
) for distinct vertices u
,
v
∈
V
(
G
), and the label f
(
u
v
) of every edge u
v
∈
E
(
G
) is defined as f
(
u
v
)
=
f
(
u
)
+
f
(
v
)
(
m
o
d
2
q
) and the set of all edge labels is equal to [
1,2
q
-
1
]
o. One considers f to be anodd-elegant labelling and G to be anodd-elegant.Definition 2 (see [15]).
Suppose that a bipartite graphG receives a labelling f such that m
a
x
{
f
(
x
)
:
x
∈
X
}
<
m
i
n
{
f
(
y
)
:
y
∈
Y
}, where (
X
,
Y
) is the bipartition of vertex set V
(
G
) of G. We call f aset-ordered labelling (So-labelling for short).As shown in Figure1, there are four different examples of Definitions 1 and 2.Figure 1
(a) An odd-elegant tree; (b) an odd-elegant graph; (c) a set-ordered odd-elegant tree; (d) a set-ordered odd-elegant graph.
(a)
(b)
(c)
(d)Definition 3.
LetG
j be a (
p
j
,
q
j
)-graph with j
=
1,2. A graph G obtained by identifying each vertex x
i
,
1 of G
1 with a vertex x
i
,
2 of G
2 into one vertex x
i
=
x
i
,
1
∘
x
i
,
2 with i
∈
[
1
,
m
] is called an m
-identification graph and denoted as G
=
⨀
m
〈
G
1
,
G
2
〉; the vertices x
1
,
x
2
,
…
,
x
m are called theidentification-vertices.Moreover, them-identification graph G
=
⨀
m
〈
G
1
,
G
2
〉 defined in Definition 3 has p
1
+
p
2
-
m vertices and q
1
+
q
2 edges. One can split each identification-vertex x
i
=
x
i
,
1
∘
x
i
,
2 into two vertices x
i
,
1 and x
i
,
2 (called thesplitting-vertices) for i
∈
[
1
,
m
], such that G is split into two parts G
1 and G
2. For the purpose of convenience, the above procedure of producing am m-identification graph G
=
⨀
m
〈
G
1
,
G
2
〉 is called an m
-identification operation; conversely, the procedure of splitting G
=
⨀
m
〈
G
1
,
G
2
〉 into two parts G
1 and G
2 is named as them-splitting operation.Definition 4.
LetG
i be a connected (
p
i
,
q
)-graph with i
=
1,2, and let p
=
p
1
+
p
2
-
2. If the 2-identification (
p
,
q
)-graph G
=
⨀
2
〈
G
1
,
G
2
〉 has a mapping f
:
V
(
G
)
→
[
0
,
q
-
1
] holding the following: (i) f
(
x
)
≠
f
(
y
) for each pair of vertices x
,
y
∈
V
(
G
), (ii) f is an odd-elegant labelling of G
i with i
=
1,2, and (iii) f
V
G
1
∩
f
V
G
2
=
2 and f
(
V
(
G
1
)
)
∪
f
(
V
(
G
2
)
)
⊆
[
0
,
q
-
1
], then one calls G atwin odd-elegant graph (a TOE-graph), f aTOE-labelling, G
1 aTOE-source graph, G
2 aTOE-associated graph, and (
G
1
,
G
2
) aTOE-matching pair.We illustrate Definition4 with Figure 2. In other words, a twin odd-elegant graph G
=
⨀
2
〈
G
1
,
G
2
〉 with its TOE-source graph G
1 and TOE-associated graph G
2, where (
G
1
,
G
2
) is a TOE-matching pair.Figure 2
The formation process of Definition4.Furthermore, if eachG
i with i
=
1,2 is a connected graph in Definition 4, and the TOE-source G
1 is a bipartite connected graph having its own bipartition (
X
1
,
Y
1
) and a labelling f satisfying Definition 2, we call the 2-identification graph G
=
⨀
2
〈
G
1
,
G
2
〉 aset-ordered twin odd-elegant graph (So-TOE-graph) and f aset-ordered twin odd-elegant labelling (So-TOE-labelling). Notice that the source graph G
1 is a set-ordered odd-elegant graph by Definitions 1 and 2. In vivid speaking, a source graph and its associated graph defined in Definition 4 can be called aTOE-lock-model and aTOE-key-model ([10]), respectively.


## 1.3. Techniques for Constructing 2-Identification Graphs

The following three operations,CA-operation, edge-series operation, and base-pasted operation, will be used in this article.(O-1) CA-Operation. Suppose each graph G
k has an odd-elegant labelling f
k and V
(
G
k
)
=
{
x
l
k
:
l
=
1,2
,
…
,
|
V
(
G
k
)
|
} with k
∈
[
1
,
m
]. Clearly, for a
≠
b with a
,
b
∈
[
1
,
m
], there are vertices x
i
a
∈
V
(
G
a
) and x
j
b
∈
V
(
G
b
) such that f
a
(
x
i
a
)
=
f
b
(
x
j
b
). For example, some G
k has a vertex x
i
k such that the label f
k
(
x
i
k
)
=
0 with k
∈
[
1
,
m
]. We can combine those vertices that have the same labels into one vertex, which gives us a new graph, denoted by G
=
⨀
ϵ
〈
G
1
,
G
2
,
…
,
G
m
〉. This process is called aCA-operation on G
1
,
G
2
,
…
,
G
m.(O-2) Edge-Series Operation. Given two groups of disjoint trees G
1
r
,
G
2
r
,
…
,
G
m
r with r
=
1,2 there are vertices x
k
r
,
y
k
r
∈
V
(
G
k
r
) with k
∈
[
1
,
m
]. Joining the vertex y
j
r with the vertex x
j
+
1
r by an edge for j
∈
[
1
,
m
-
1
] produces a tree H
r (denoted by H
r
=
⊖
k
=
1
m
G
k
r) with r
=
1,2; next we let one vertex u
s
1
∈
V
(
H
1
) coincide with one vertex v
s
2
∈
V
(
H
2
) into one vertex a
s
=
u
s
1
∘
v
s
2 with s
=
1,2. The resulting graph ⨀
2
〈
H
1
,
H
2
〉 is just a 2-identification graph.(O-3) Base-Pasted Operation. Given two disjoint trees T
r (calledbase-trees) having vertices x
1
r
,
x
2
r
,
…
,
x
m
r and two groups of disjoint trees G
1
r
,
G
2
r
,
…
,
G
m
r with r
=
1,2, we let a vertex u
k
r
∈
V
(
G
k
r
) coincide with the vertex x
k
r
∈
V
(
T
r
) into one vertex u
k
r
∘
x
k
r for k
∈
[
1
,
m
] such that the resulting tree F
r (i.e., F
r
=
T
r
⨀
k
=
1
m
G
k
r) has V
(
F
r
)
=
⋃
k
=
1
m
V
(
G
k
r
), E
(
F
r
)
=
(
⋃
k
=
1
m
E
(
G
k
r
)
)
∪
E
(
T
r
) for r
=
1,2. We overlap one vertex w
s
1
∈
V
(
F
1
) with one vertex z
s
2
∈
V
(
F
2
) into one vertex b
s
=
w
s
1
∘
z
s
2 with s
=
1,2 to build up a 2-identification graph F
=
⨀
2
〈
F
1
,
F
2
〉 holding V
(
F
1
)
∩
V
(
F
2
)
=
{
a
1
,
a
2
} and E
(
F
)
=
E
(
F
1
)
∪
E
(
F
2
)
.In the following, we give the diagrams withm
=
2 for edge-series operation and base-pasted operation, shown in Figures 3 and 4, respectively.Figure 3
A scheme of the edge-series operation.Figure 4
A scheme of the base-pasted operation.


## 2. Main Results and Their Proofs

Lemma 5.
Each starK
1
,
n is a TOE-source tree of a So-TOE-tree.Proof of Lemma5 is shown in Figure 5. It describes the construction process of the So-TOE-tree ⨀
〈
K
1
,
n
,
K
1
,
n
〉 by any TOE-source tree K
1
,
n.Figure 5
An example of illustrating Lemma5.Figure 6
Examples of Theorem6.
(a)
G
1
(b)
T
2
(c)
T
2
′
(d)
G
=
⨀
2
〈
G
1
,
T
2
〉
(e)
G
′
=
⨀
2
〈
G
1
,
T
2
′
〉Theorem 6.
Every set-ordered odd-elegant graph being not a star is a So-TOE-source graph of at least two So-TOE graphs.Proof.
Suppose that(
p
1
,
q
)-graph G
1 having vertex bipartition is (
X
,
Y
), where X
=
{
x
i
:
i
∈
[
1
,
s
]
}, Y
=
{
y
j
:
j
∈
[
1
,
t
]
}, s
+
t
=
p
1, and m
i
n
{
s
,
t
}
≥
2. By the hypothesis of the theorem, G
1 has a set-ordered odd-elegant labelling f
1 defined by f
1
(
x
i
)
+
2
≤
f
1
(
x
i
+
1
), i
∈
[
1
,
s
-
1
]; f
1
(
y
1
)
=
f
1
(
x
s
)
+
1, f
1
(
y
j
)
+
2
≤
f
1
(
y
j
+
1
), i
∈
[
1
,
t
-
1
]; f
1
(
y
t
)
≤
2
q
-
1. Hence, f
1
(
E
(
G
1
)
)
=
{
f
1
(
x
y
)
=
f
1
(
x
)
+
f
1
(
y
)
(
m
o
d
2
q
)
:
x
y
∈
E
(
G
1
)
}
=
[
1,2
q
-
1
]
o. It is not difficult to observe that f
1
(
V
(
G
1
)
)
⊂
{
0,2
,
…
,
f
1
(
x
s
)
,
f
1
(
y
1
)
,
…
,
2
q
-
1
}; that is, f
1
(
X
)
/
2
⊂
N and (
f
1
(
Y
)
+
1
)
/
2
⊂
N.
Case
1. We construct a labelling f
2 of a new tree T
2 having q
+
1 vertices by the labelling f
1 such that f
2
(
V
(
T
2
)
)
=
[
1
,
f
1
(
x
s
)
+
1
]
o
∪
[
f
1
(
y
1
)
-
1,2
q
-
2
]
e, such that f
2
(
E
(
T
2
)
)
=
{
f
2
(
u
v
)
=
f
2
(
u
)
+
f
2
(
v
)
(
m
o
d
2
q
)
:
u
v
∈
E
(
T
2
)
}
=
[
1,2
q
-
1
]
o, where f
2
(
u
)
≠
f
2
(
v
) for u
,
v
∈
V
(
T
2
). This tree T
2 can be built up in the following way: a bipartition (
U
1
,
V
1
) with U
1
=
{
u
i
:
i
∈
[
1
,
s
1
]
} and V
1
=
{
v
j
:
j
∈
[
1
,
t
1
]
}, where s
1
+
t
1
=
q
+
1, such that f
2
(
u
i
)
=
2
i
-
1, i
∈
[
1
,
s
1
]; f
2
(
v
j
)
=
2
(
s
1
-
2
+
j
), j
∈
[
1
,
t
1
]. Any edge u
i
v
j
∈
E
(
T
2
) satisfies f
2
(
u
i
v
j
)
=
f
2
(
u
i
)
+
f
2
(
v
j
)
(
m
o
d
2
q
) with i
∈
[
1
,
s
1
] and j
∈
[
1
,
t
1
]. We construct the edge set of T
2 as {
u
1
v
j
,
u
i
v
t
1
:
i
∈
[
1
,
s
1
]
,
j
∈
[
1
,
t
1
-
1
]
} such that the edge labels are f
2
(
u
i
v
t
1
)
=
2
i
-
3, f
2
(
u
1
v
j
)
=
2
j
+
2
s
1
-
3
(
m
o
d
2
q
) for i
∈
[
1
,
s
1
] and j
∈
[
1
,
t
1
-
1
]. Observe that f
2
(
E
(
T
2
)
)
=
[
1,2
q
-
1
]
o, f
1
(
y
1
)
=
f
2
(
u
s
1
), and f
1
(
x
s
)
=
f
2
(
v
1
).
Now, we can combine the vertexy
1 and x
s of G
1 with the vertex u
s
1 and v
1 of T
2 into one (two identification-vertices) w
1 and w
2, respectively, so we obtain the desired graph G
=
⨀
2
〈
G
1
,
T
2
〉. And G has a labelling f defined as f
(
x
i
)
=
f
1
(
x
i
), i
∈
[
1
,
s
-
1
]; f
(
y
j
)
=
f
1
(
y
j
), i
∈
[
2
,
t
]; f
(
u
k
)
=
f
2
(
u
k
), k
∈
[
1
,
s
1
-
1
], f
(
v
1
)
=
f
2
(
v
l
), l
∈
[
2
,
t
1
], f
(
w
1
)
=
f
1
(
y
1
), and f
(
w
2
)
=
f
1
(
x
s
). Clearly, any pair of two vertices of G are assigned different numbers. According to Definition 4, G is an So-TOE-graph having the source graph G
1. Examples that illustrate Case 1 of Theorem 6 are shown by Figures 6(a), 6(b), and 6(d).
Case
2. Similarly to Case 1, we can get the following results: let f
2
(
V
(
T
2
′
)
)
=
[
1
,
f
1
(
x
s
)
-
1
]
o
∪
[
f
1
(
y
1
)
-
1,2
q
-
2
]
e
∪
0, f
2
(
E
(
T
2
′
)
)
=
[
1,2
q
-
1
]
o, and furthermore f
2
(
u
)
≠
f
2
(
v
) for u
,
v
∈
V
(
T
2
′
). This tree T
2
′ can be built up in the following way: a bipartition (
U
2
,
V
2
) with U
2
=
{
u
i
:
i
∈
[
1
,
s
1
-
1
]
} and V
2
=
{
v
j
:
j
∈
[
1
,
t
1
+
1
]
}, such that f
2
(
u
i
)
=
2
i
-
1, i
∈
[
1
,
s
1
-
1
]; f
2
(
v
j
)
=
2
(
s
-
2
+
j
), j
∈
[
1
,
t
1
], f
2
(
v
t
1
+
1
)
=
0. Any edge u
i
v
j
∈
E
(
T
2
′
) satisfies f
2
(
u
i
v
j
)
=
f
2
(
u
i
)
+
f
2
(
v
j
)
(
m
o
d
2
q
) with i
∈
[
1
,
s
1
-
1
] and j
∈
[
1
,
t
1
+
1
]. We construct the edge set of T
2
′ as {
u
1
v
j
,
u
i
v
t
+
1
:
i
∈
[
2
,
s
1
-
1
]
,
j
∈
[
1
,
t
1
]
} such that the edge labels are f
2
(
u
i
v
t
+
1
)
=
2
i
-
1, for i
∈
[
1
,
s
1
-
1
], and f
2
(
u
1
v
j
)
=
2
(
s
+
j
)
-
3, for j
∈
[
1
,
t
1
]. Observe that f
2
(
E
(
T
2
′
)
)
=
[
1,2
q
-
1
]
o, f
1
(
x
1
)
=
f
2
(
v
t
1
+
1
), and f
1
(
x
s
)
=
f
2
(
v
1
).
Now, we can combine the vertexx
1 and x
s of T
1 with the vertex v
t
1
+
1 and v
1 of T
2
′ into one (the identified vertex) w
1 and w
2, so we obtain the desired tree G
′
=
⨀
2
〈
G
1
,
T
2
′
〉. And G
′ has a labelling f defined as f
(
x
i
)
=
f
1
(
x
i
), i
∈
[
2
,
s
-
1
]; f
(
y
j
)
=
f
1
(
y
j
), i
∈
[
1
,
t
]; f
(
u
k
)
=
f
2
(
u
k
), k
∈
[
1
,
s
1
-
1
], f
(
v
l
)
=
f
2
(
v
l
), l
∈
[
2
,
t
1
], f
(
w
1
)
=
0, and f
(
w
2
)
=
f
1
(
x
s
). Clearly, any pair of two vertices of G
′ are assigned different numbers. According to Definition 4, G
′ is a So-TOE-graph having the source graph G
1. An example for illustrating Case 2 of Theorem 6 is given by Figures 6(a), 6(c), and 6(e).Theorem 7.
Suppose thatG
k
=
⨀
2
〈
G
k
1
,
G
k
2
〉 is a So-TOE-graph, where each G
k
1 is a source tree for k
∈
[
1
,
m
]. Then G
=
⨀
2
〈
H
1
,
H
2
〉 obtained by the edge-series operation has a So-TOE-labelling.Proof.
By the hypothesis of the theorem, every(
p
k
1
+
p
k
2
-
2,2
q
k
)-graph G
k has a set-ordered odd-elegant source-(
p
k
1
,
q
k
)-graph G
k
1 and an associated-(
p
k
2
,
q
k
)-graph G
k
2 for k
∈
[
1
,
m
]. Let V
(
G
k
1
)
∩
V
(
G
k
2
)
=
{
w
k
1
,
w
k
2
}; the vertex set of each graph G
k
r can be partitioned into (
X
k
r
,
Y
k
r
) with r
=
1,2, where X
k
r
=
{
x
k
,
i
r
:
i
∈
[
1
,
s
k
r
]
}, Y
k
r
=
{
y
k
,
j
r
:
j
∈
[
1
,
t
k
r
]
}, and s
k
r
+
t
k
r
=
p
k
r for k
∈
[
1
,
m
] and r
=
1,2. By Definition 4, every G
k has a So-TOE-labelling θ
k with k
∈
[
1
,
m
] such that θ
k
(
x
k
,
1
r
)
≥
r
-
1; θ
k
(
x
k
,
i
r
)
+
2
≤
θ
k
(
x
k
,
i
+
1
r
) with i
∈
[
1
,
s
k
r
]; θ
k
(
y
k
,
1
r
)
=
θ
k
(
x
k
,
s
k
r
r
)
-
(
-
1
)
r; θ
k
(
y
k
,
j
r
)
+
2
≤
θ
k
(
y
k
,
j
+
1
r
) for i
∈
[
1
,
t
k
r
]; and θ
k
(
y
t
k
r
r
)
≤
2
q
k
-
r.
Therefore,θ
k
(
E
(
G
k
r
)
)
=
{
θ
k
(
x
y
)
=
θ
k
(
x
)
+
f
k
r
(
y
)
(
m
o
d
2
q
k
)
:
x
y
∈
E
(
G
k
r
)
}
=
[
1,2
q
k
-
1
]
o, where θ
k
(
x
)
≠
θ
k
(
y
) for distinct vertices x
,
y
∈
V
(
G
k
), which means θ
k
(
x
k
,
s
k
1
)
=
θ
k
(
y
k
,
1
2
)
=
θ
k
(
w
k
1
) and θ
k
(
y
k
,
1
1
)
=
θ
k
(
x
k
,
s
k
2
)
=
θ
k
(
w
k
2
). Clearly, the labels of other vertices of G
k
1
∪
G
k
2 differ from each other.
Firstly, we splitG
k into two parts G
k
1 and G
k
2, that is, doing a 2-splitting operation on every G
k with k
∈
[
1
,
m
]. Secondly, our discussion focuses on G
k
1 and G
k
2 with k
∈
[
1
,
m
]. We construct a graph by joining the vertex y
k
,
t
k
r with the vertex x
k
+
1,1
r by an edge, where k
∈
[
1
,
m
-
1
] and r
=
1,2, called H
r. For the purpose of convenience, we set S
(
a
,
b
)
=
∑
l
=
a
b
‍
θ
l
(
x
l
,
s
l
1
1
)
+
2, Q
(
1
,
t
)
=
2
∑
l
=
1
t
‍
(
q
l
+
1
), Q
m
=
2
∑
l
=
1
m
‍
(
q
l
+
m
-
1
), S
(
1,0
)
=
0, and Q
(
1,0
)
=
0. For r
=
1,2, i
∈
[
1
,
s
k
r
], and j
∈
[
1
,
t
k
r
], we define a new labelling f as follows:(T-1)
f
(
x
k
,
i
r
)
=
θ
k
(
x
k
,
i
r
)
+
S
(
1
,
k
-
1
);
(T-2)
f
(
y
k
,
j
r
)
=
θ
k
(
y
k
,
j
r
)
+
Q
(
1
,
k
-
1
)
+
S
(
k
+
1
,
m
);
(T-3)
f
(
x
k
,
i
r
y
k
,
j
r
)
=
f
(
x
k
,
i
r
)
+
f
(
y
k
,
j
r
)
(
m
o
d
Q
m
);
(T-4)
f
(
y
k
,
t
k
r
x
k
+
1,1
r
)
=
f
(
x
k
+
1,1
r
)
+
f
(
y
k
,
t
k
r
)
(
m
o
d
Q
m
).
By the labelling forms (T-1) and (T-2) above, we can verifyf
(
x
k
,
i
1
)
∈
[
0
,
f
(
x
m
,
s
m
1
)
]
e
=
0
,
S
(
1
,
m
)
-
2
e with k
∈
[
1
,
m
] and have the following properties: (i) f
(
x
k
,
i
2
)
∈
[
1
,
f
(
x
m
,
s
m
2
)
]
o
=
[
1
,
S
(
1
,
m
)
-
1
]
o; (ii) f
(
y
k
,
j
1
)
∈
[
f
(
y
1,1
1
)
,
f
(
y
m
,
t
m
1
)
]
o
=
[
S
(
1
,
m
)
-
1
,
Q
m
-
1
]
o; and (iii) f
(
y
k
,
j
2
)
∈
[
f
(
y
1,1
2
)
,
f
(
y
m
,
t
m
2
)
]
e
=
[
S
(
1
,
m
)
-
2
,
Q
m
-
2
]
e.
Computing the labelling forms (T-3) and (T-4) enables us to obtainf
(
E
(
H
r
)
)
=
[
1
,
Q
m
-
1
]
o for r
=
1,2. Now, we combine the vertex x
m
,
s
m
1 with the vertex y
1,1
2 into one vertex and then combine the vertex y
1,1
1 with the vertex x
m
,
s
m
2 into one vertex. (i.e., do the 2-identification operation). Thus the labelling f is a So-TOE-labelling of G
=
⨀
2
〈
H
1
,
H
2
〉; therefore, G is a So-TOE-graph too.See Figures7, 8 and 9 for understanding Theorem 7.Figure 7
Four So-TOE-graphsG
k with k
∈
[
1
,
4
] described in the proof of Theorem 7.
(a)
G
1
(b)
G
2
(c)
G
3
(d)
G
4Figure 8
A So-TOE-graph made by the graphs shown in Figure7 for illustrating Theorem 7.Figure 9
Another So-TOE-graph made by the graphs shown in Figure7 for illustrating Theorem 7.In experiments, for each arrangementG
k
1
r
,
G
k
2
r
,
…
,
G
k
m
r of G
1
r
,
G
2
r
,
…
,
G
m
r, there are many possible constructions of G
=
⨀
2
〈
H
1
,
H
2
〉 for holding Theorem 7 (as shown in Figure 9).Theorem 8.
Suppose thatG
k
=
⨀
2
〈
G
k
1
,
G
k
2
〉 is a So-TOE-graph, where each G
k
1 is a source graph for k
∈
[
1
,
p
]. Then G
=
⨀
2
〈
S
1
,
S
2
〉 obtained by the base-pasted operation has a So-TOE-labelling if two base-trees T
1 and T
2 are set-ordered.Proof.
By the hypothesis of the theorem, every(
p
k
1
+
p
k
2
-
2,2
q
)-graph G
k
=
⨀
2
〈
G
k
1
,
G
k
2
〉 has a set-ordered odd-elegant source-(
p
k
1
,
q
)-graph G
k
1 and an associated-(
p
k
2
,
q
)-graph G
k
2 for k
∈
[
1
,
p
]. Let G
k
1
∩
G
k
2
=
{
w
k
1
,
w
k
2
}; the vertex set of each graph G
k
r can be partitioned into (
X
k
r
,
Y
k
r
) with r
=
1,2, where X
k
r
=
{
x
k
,
i
r
:
i
∈
[
1
,
s
k
r
]
}, Y
k
r
=
{
y
k
,
j
r
:
j
∈
[
1
,
t
k
r
]
}, s
k
r
≤
t
k
r, and s
k
r
+
t
k
r
=
p
k
r for k
∈
[
1
,
p
] and r
=
1,2. Every G
k, by Definition 4, has a So-TOE-labelling π
k with k
∈
[
1
,
p
], and π
k has the following properties: π
k
(
x
k
,
1
r
)
=
r
-
1; π
k
(
x
k
,
i
r
)
+
2
≤
π
k
(
x
k
,
i
+
1
r
) for i
∈
[
1
,
s
k
r
]; π
k
(
x
k
,
s
k
r
)
=
M
-
1
+
r; π
k
(
y
k
,
1
r
)
=
π
k
(
x
k
,
s
k
r
r
)
-
(
-
1
)
r
=
M
-
1
+
r
-
(
-
1
)
r; π
k
(
y
k
,
j
r
)
+
2
≤
π
k
(
y
k
,
j
+
1
r
) with i
∈
[
1
,
t
k
r
]; π
k
(
y
t
k
r
r
)
=
2
q
-
r; and π
k
(
x
k
,
i
r
y
k
,
j
r
)
=
π
k
(
x
k
,
i
r
)
+
π
k
(
y
k
,
j
r
)
(
m
o
d
2
q
).
Thus, the properties of each So-TOE-labellingπ
k induce π
k
(
E
(
G
k
r
)
)
=
{
π
k
(
x
y
)
=
π
k
(
x
)
+
f
k
r
(
y
)
(
m
o
d
2
q
)
:
x
y
∈
E
(
G
k
r
)
}, and also(2)
π
k
E
G
k
r
=
π
k
x
k
,
1
r
+
π
k
y
k
,
1
r
,
π
k
x
k
,
s
k
r
r
+
π
k
y
k
,
t
k
r
r
m
o
d
2
q
=
1,2
q
-
1
o
,where π
k
(
x
)
≠
π
k
(
y
) if x
≠
y and x
,
y
∈
V
(
G
k
). In other words, we have π
k
(
x
k
,
s
k
1
)
=
π
k
(
y
k
,
1
2
)
=
π
k
(
w
k
1
) and π
k
(
y
k
,
1
1
)
=
π
k
(
x
k
,
s
k
2
)
=
π
k
(
w
k
2
). The labels of other vertices of G
k
1
∪
G
k
2 differ from each other.
LetV
(
T
r
)
=
{
z
1
r
,
z
2
r
,
…
,
z
p
r
}, such that there exists a set-ordered odd-elegant labelling f
T
r
o
e, satisfying f
T
r
o
e
(
z
i
r
)
<
f
T
r
o
e
(
z
i
+
1
r
) with i
∈
[
1
,
p
-
1
], and the bipartition (
U
r
,
V
r
) of vertex set of T
r satisfies |
U
r
|
≤
|
V
r
| for |
U
r
|
=
l and r
=
1,2.
Next, we discuss all graphsG
k
1 and G
k
2 with k
∈
[
1
,
p
] by the parity of positive integer p in the following two cases.
Case
1. For considering the case p
=
2
β
+
1 and r
=
1,2, we define a new labelling f with i
∈
[
1
,
s
k
r
] and j
∈
[
1
,
t
k
r
] in the following way:(C-1)
f
(
x
2
k
-
1
,
i
r
)
=
π
2
k
-
1
(
x
2
k
-
1
,
i
r
)
+
2
(
q
+
1
)
(
k
-
1
) with k
∈
[
1
,
β
+
1
];
(C-2)
f
(
x
2
k
,
i
r
)
=
π
2
k
(
x
2
k
,
i
r
)
+
2
(
q
+
1
)
(
β
+
k
)
-
2
-
(
-
1
)
r with k
∈
[
1
,
β
];
(C-3)
f
(
y
2
k
-
1
,
j
r
)
=
π
2
k
-
1
(
y
2
k
-
1
,
j
r
)
+
2
(
q
+
1
)
(
β
+
k
-
1
) with k
∈
[
1
,
β
+
1
];
(C-4)
f
(
y
2
k
,
j
r
)
=
π
2
k
(
y
2
k
,
j
r
)
+
2
(
q
+
1
)
(
k
-
1
)
+
2
+
(
-
1
)
r with k
∈
[
1
,
β
];
(C-5)
f
(
x
k
,
i
r
y
k
,
j
r
)
=
f
(
y
k
,
j
r
)
+
f
(
x
k
,
i
r
)
(
m
o
d
2
p
(
q
+
1
)
-
2
).
Based upon the labelling forms (C-1)–(C-4), we compute(3)
⋃
k
=
1
β
+
1
f
X
2
k
-
1
1
∪
⋃
k
=
1
β
f
Y
2
k
1
=
0,2
q
+
1
β
+
M
e
;
⋃
k
=
1
β
+
1
f
Y
2
k
-
1
1
∪
⋃
k
=
1
β
f
X
2
k
1
=
2
q
+
1
β
+
M
+
1,2
p
q
+
1
-
3
o
,
r
=
1
,
⋃
k
=
1
β
+
1
f
X
2
k
-
1
2
∪
⋃
k
=
1
β
f
Y
2
k
2
=
1,2
q
+
1
β
+
M
+
1
o
;
⋃
k
=
1
β
+
1
f
Y
2
k
-
1
2
∪
⋃
k
=
1
β
f
X
2
k
2
=
2
q
+
1
β
+
M
,
2
p
q
+
1
-
4
e
,
r
=
2
.
Thereby, we have shown that⋃
r
=
1
2
⋃
k
=
1
p
f
V
G
k
r
⊂
[
0,2
p
(
q
+
1
)
-
3
] and (4)
⋃
r
=
1
2
⋃
k
=
1
p
f
E
G
k
r
∪
⋃
r
=
1
2
f
E
T
r
=
1,2
p
q
+
1
-
3
o
,and furthermore the labels of vertices, except f
(
x
p
,
s
1
)
=
f
(
y
1,1
2
) and f
(
x
p
,
s
2
)
=
f
(
y
1,1
1
), differ from each other, and the labels of edges differ from each other.
Next, after computing the labelling forms (C-5) withk
∈
[
1
,
p
], we obtain(5)
f
E
G
2
k
-
1
r
=
A
2
,
B
1
o
,
k
∈
1
,
β
+
1
;
f
E
G
2
k
r
=
A
1
,
B
0
o
,
k
∈
1
,
β
.
m
o
d
2
p
q
+
1
-
2
,where A
(
x
)
=
M
+
1
+
2
(
q
+
1
)
(
β
+
2
k
-
x
) and B
(
y
)
=
M
-
3
+
2
(
q
+
1
)
(
β
+
2
k
-
y
). By the above deduction, we can know that(6)
⋃
k
=
1
p
f
E
G
k
r
=
1,2
p
q
+
1
-
3
o
∖
F
,where F
=
{
M
-
1
+
2
(
q
+
1
)
(
β
+
1
+
k
)
,
M
+
1
+
2
(
q
+
1
)
k
:
k
=
0,1
,
2
,
…
,
β
-
1
}. Next, for each vertex z
k
r
∈
V
(
T
r
) with k
∈
[
1
,
p
] and r
=
1,2, we set(7)
f
z
k
1
=
f
x
2
k
-
1
,
s
2
k
-
1
1
1
,
f
z
k
2
=
f
y
2
β
+
k
-
l
+
1,1
2
,
k
∈
1
,
l
;
f
z
l
+
k
1
=
f
x
2
k
,
1
1
,
f
z
β
+
1
+
k
2
=
f
y
2
k
,
t
2
k
2
2
,
k
∈
1
,
β
;
f
z
l
+
β
+
k
1
=
f
x
2
k
-
1,1
2
,
f
z
l
+
k
2
=
f
y
2
l
+
k
-
1
,
t
2
l
+
k
-
1
2
1
,
k
∈
1
,
β
+
1
-
l
.
According to formula (7), we obtain f
(
z
i
r
z
j
r
)
=
f
(
z
i
r
)
+
f
(
z
j
r
)
∈
F with i
∈
[
1
,
l
], j
∈
[
l
+
1
,
p
], and r
=
1,2, which means(8)
f
E
T
r
=
F
.
Doing aCA-operation on G
k
r and T
r having labelling f for k
∈
[
1
,
p
] produces a new graph S
r with r
=
1,2. Now, we combine the vertex x
p
,
s
p
1
1 with the vertex y
1,1
2 into one vertex w
1
=
x
p
,
s
p
1
1
∘
y
1,1
2 and moreover identify the vertex y
1,1
1 with the vertex x
p
,
s
p
2
2 into one vertex w
2
=
y
1,1
1
∘
x
p
,
s
p
2
2 (i.e., do a 2-identification operation).
By Definitions2 and 4 and formulae (3)–(8), the labelling f is a So-TOE-labelling of G
=
⨀
2
〈
S
1
,
S
2
〉. Hence, G is a So-TOE-graph. Here, we have proven Case 1. For understanding Case 1, see Figures 10 and 11.
Case
2. We, for the case p
=
2
β and r
=
1,2, define a new labelling f for i
∈
[
1
,
s
k
r
] and j
∈
[
1
,
t
k
r
] in the following way:(L-1)
f
(
x
2
k
-
1
,
i
r
)
=
π
2
k
-
1
(
x
2
k
-
1
,
i
r
)
+
2
(
q
+
1
)
(
k
-
1
) with k
∈
[
1
,
β
];
(L-2)
f
(
x
2
k
,
i
r
)
=
π
2
k
(
x
2
k
,
i
r
)
+
2
(
q
+
1
)
(
β
+
k
)
-
M
-
4
-
(
-
1
)
r with k
∈
[
1
,
β
];
(L-3)
f
(
y
2
k
-
1
,
j
r
)
=
π
2
k
-
1
(
y
2
k
-
1
,
j
r
)
+
2
(
q
+
1
)
(
β
+
k
-
1
)
-
M
-
2 with k
∈
[
1
,
β
];
(L-4)
f
(
y
2
k
,
j
r
)
=
π
2
k
(
y
2
k
,
j
r
)
+
2
(
q
+
1
)
(
k
-
1
)
+
2
+
(
-
1
)
r with k
∈
[
1
,
β
];
(L-5)
f
(
x
k
,
i
r
y
k
,
j
r
)
=
f
(
y
k
,
j
r
)
+
f
(
x
k
,
i
r
)
(
m
o
d
2
p
(
q
+
1
)
-
2
).
From the above labelling forms (L-1)–(L-4), we can compute(9)
⋃
k
=
1
β
f
X
2
k
-
1
1
∪
⋃
k
=
1
β
f
Y
2
k
1
=
0,2
q
+
1
β
-
2
e
;
⋃
k
=
1
β
f
Y
2
k
-
1
1
∪
⋃
k
=
1
β
f
X
2
k
1
=
2
q
+
1
β
-
1,2
p
q
+
1
-
3
o
,
r
=
1
,
⋃
k
=
1
β
f
X
2
k
-
1
2
∪
⋃
k
=
1
β
f
Y
2
k
2
=
1,2
q
+
1
β
-
1
o
;
⋃
k
=
1
β
f
Y
2
k
-
1
2
∪
⋃
k
=
1
β
f
X
2
k
2
=
2
q
+
1
β
-
2,2
p
q
+
1
-
4
e
,
r
=
2
.
Thereby, we conclude that⋃
r
=
1
2
⋃
k
=
1
p
f
V
G
k
r
=
[
0,2
p
(
q
+
1
)
-
3
] and (10)
⋃
r
=
1
2
⋃
k
=
1
p
f
E
G
k
r
∪
⋃
r
=
1
2
f
E
T
r
=
1,2
p
q
+
1
-
3
o
,in which the labels of vertices and edges, except f
(
y
p
,
t
p
1
1
)
=
f
(
y
1,1
2
) and f
(
y
p
,
t
p
2
2
)
=
f
(
y
1,1
1
), differ from each other, respectively.
Again, by computing the labelling form (L-5) for eachk
∈
[
1
,
p
], we obtain(11)
f
E
G
2
k
-
1
r
=
α
2
,
β
1
o
;
f
E
G
2
k
r
=
α
1
,
β
0
o
,
m
o
d
2
p
q
+
1
-
2
,
k
∈
1
,
β
,where α
(
x
)
=
2
(
q
+
1
)
(
β
+
2
k
-
x
)
-
1 and β
(
y
)
=
2
(
q
+
1
)
(
β
+
2
k
-
y
)
-
5.
Synthesizing the above argument, we get⋃
k
=
1
p
f
E
G
k
r
=
[
1,2
p
(
q
+
1
)
-
3
]
o
∖
F
′, where the set F
′
=
{
2
(
q
+
1
)
(
β
+
k
)
-
3
(
m
o
d
2
p
(
q
+
1
)
-
2
)
:
k
∈
[
1,2
β
-
1
]
}. For each vertex z
k
r
∈
T
r with ∈
[
1
,
p
] and r
=
1,2, we set(12)
f
z
k
1
=
f
x
2
k
-
1,1
1
,
f
z
k
2
=
f
x
2
β
+
k
-
l
,
s
2
β
+
k
-
l
2
2
,
k
∈
1
,
l
;
f
z
l
+
k
1
=
f
x
2
k
,
s
2
k
1
1
,
f
z
β
+
k
2
=
f
x
2
k
-
1,1
2
,
k
∈
1
,
β
;
f
z
l
+
β
+
k
1
=
f
y
2
k
,
t
2
k
2
2
,
f
z
l
+
k
2
=
f
y
2
l
+
k
-
1,1
1
,
k
∈
1
,
β
-
l
.
The above formula (12) enables us to obtain f
(
z
i
r
z
j
r
)
=
f
(
z
i
r
)
+
f
(
z
j
r
)
∈
F
′ with i
∈
[
1
,
l
], j
∈
[
l
+
1
,
p
], and r
=
1,2. Thereby, we have shown(13)
f
E
T
r
=
F
′
.
After performing aCA-operation on G
k
r and T
r having labelling f for k
∈
[
1
,
p
], then we obtain a new graph S
r with r
=
1,2. Now, we overlap the vertex y
p
,
t
p
1
1 with the vertex y
1,1
2 into one vertex w
1
′
=
y
p
,
t
p
1
1
∘
y
1,1
2 and overlap the vertex y
1,1
1 with the vertex y
p
,
t
p
2
2 into one vertex w
2
′
=
y
1,1
1
∘
y
p
,
t
p
2
2 (i.e., do a 2-identification operation) in order to obtain G
′
=
⨀
2
〈
S
1
,
S
2
〉. Furthermore, by Definitions 2 and 4 and formulae (9)–(13), the labelling f is a So-TOE-labelling of G
′, which implies that G
′ is a So-TOE-graph.
Hence, the proof of Case 2 is finished, and illustrating this case is given in Figures12 and 13.
The proof of the theorem is complete.Figure 10
Seven So-TOE-graphsG
k with k
∈
[
1
,
7
] and two base-trees T
1 and T
2 described in the proof of Case 1 of Theorem 8.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)Figure 11
A So-TOE-graph⨀
2
〈
S
1
,
S
2
〉 made by the graphs shown in Figure 10 for understanding the proof of Case 1 of Theorem 8.Figure 12
Six So-TOE-graphsG
k with k
∈
[
1
,
6
] and two base-trees T
1 and T
2 described in the proof of Case 2 of Theorem 8.Figure 13
A So-TOE-graph⨀
2
〈
S
1
,
S
2
〉 made by the graphs shown in Figure 12 for understanding the proof of Case 2 of Theorem 8.


## 3. Conclusion and Further Research

There are new Topsnut-GPWs having twin odd-elegant labellings introduced here. We define the twin odd-elegant labelling and investigate the2-identification graph G
=
⨀
2
〈
G
1
,
G
2
〉, called twin odd-elegant graph. We think that finding all possible TOE-matching pairs (
G
,
H
) defined in Definition 4 may be interesting for a given TOE-graph G with an odd-elegant labelling g. Let (14)
M
T
O
E
G
,
g
=
H
:
G
,
H
is  a  TOE-matching  pairbe the set of all TOE-associated graphs H, so, we have aTOE-book
B
(
G
,
g
)
=
⋃
H
∈
M
T
O
E
(
G
,
g
)
⨀
2
〈
G
,
H
〉 withbook-back
G andbook-pages
H
∈
M
T
O
E
(
G
,
g
).We should pay attention to the following problems:(i) SinceG
=
⨀
2
G
,
H
∩
⨀
2
〈
G
,
H
′
〉 for any pair of book-pages H
,
H
′
∈
M
T
O
E
(
G
,
g
), does V
(
G
)
=
⋃
H
∈
M
T
O
E
G
,
g
V
G
∩
V
H?(ii) Suppose thatG has m pairwise different odd-elegant labellings g
1
,
g
2
,
…
,
g
m. Find some possible relationships among TOE-books B
(
G
,
g
i
) with i
∈
[
1
,
m
].For the future researching work on Topsnut-GPWs, we propose the following.Conjecture 9.
Let each⨀
2
〈
G
k
1
,
G
k
2
〉 be a TOE-graph for k
∈
[
1
,
m
] with m
≥
2. The 2-identification graph G
=
⨀
2
〈
H
1
,
H
2
〉 obtained by the edge-series operation (resp., the base-pasted operation) admits a TOE-labelling.rConjecture 10.
Every simple and connected TOE-graph admits an odd-elegant labelling.Conjecture 11.
Each connected graph is the TOE-source graph of a certain TOE-graph.A more interesting problem is to design super Topsnut-GPWs such that each super Topsnut-GPW will not be deciphered by attacks of nonquantum computers, since (i) our methods introduced here can construct quickly large scale of Topsnut-GPWs having hundreds vertices; (ii) the space of the Topsnut-GPWs given in Theorem8 is quite tremendous; (iii) the 2-identification graphs ⨀
2
〈
H
1
,
H
2
〉 of Theorem 7 and ⨀
2
〈
S
1
,
S
2
〉 of Theorem 8 are the compound type of Topsnut-GPWs based on smaller scale of Topsnut-GPWs G
k
=
⨀
2
〈
G
k
1
,
G
k
2
〉 with k
∈
[
1
,
m
], and they induce the TOE-books B
(
H
1
,
f
) and B
(
S
1
,
g
); it may be guessed that there is no polynomial algorithm for determining the TOE-books; and (iv) no polynomial algorithm was reported for finding all odd-elegant labellings of a given graph.Thereby, we hope to discover such super Topsnut-GPWs which can be used in the era of quantum information.



---

*Source: 9482345-2018-04-11.xml*