Printer Friendly

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

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 unit [2.sup.n]? Obviously, we need enough graphs and lots of graph coloring/labellings, and we can turn more things into Topsnut-GPWs. Let [G.sub.p] be the number of graphs having p vertices. From [11], we know
p     [G.sub.p]                                                  bits

18    1787577725145611700547878190848                             100
19    24637809253125004524383007491432768                         114
20    645490122795799841856164638490742749440                     129
21    32220272899808983433502244253755283616097664                145
22    3070846483094144300637568517187105410586657814272           161
23    559946939699792080597976380819462179812276348458981632      179
24    195704906302078447922174862416726256004122075267063365-     197


where [G.sub.p] [approximately equal to] [2.sup.bits] 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.sub.1] [v.sub.10] [v.sub.11] [v.sub.20] in Figure 6(d) to produce an alphanumeric password

W = 1'1816141210201'1Q/1151721111Q/11,10202011,2Q/111579320' (1)

by selecting the neighbors of each vertex of these four vertices [v.sub.1], [v.sub.10], [v.sub.11], and [v.sub.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 oddelegant 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 [less than or equal to] m < n; [[s, t].sup.[omicron]] indicating an odd-set {s, s + 2, ..., t}, where s and t both are odd integers with 1 [less than or equal to] s < t; and [[k, l].sup.e] represents an even-set {k, k + 2, ..., l}, where k and l are both even integers with respect to 0 [less than or equal to] k < l.

Definition 1 (see [13]). Suppose that a (p, q)-graph G admits a mapping f : 7(G) [right arrow] [0, 2q - 1] such that f(u) [not equal to] f(v) for distinct vertices u, v [member of] 7(G), and the label f(uv) of every edge uv [member of] E(G) is defined as f(uv) = f(u) + f(v) (mod 2q) and the set of all edge labels is equal to [[1, 2q - 1].sup.[omicron]]. One considers f to be an odd-elegant labelling and G to be an odd-elegant.

Definition 2 (see [15]). Suppose that a bipartite graph G receives a labelling f such that max{f(x) : x [member of] X} < min{f(y) : y [member of] Y}, where (X, Y) is the bipartition of vertex set V(G) of G. We call f a set-ordered labelling (So-labelling for short).

As shown in Figure 1, there are four different examples of Definitions 1 and 2.

Definition 3. Let [G.sub.j] be a ([p.sub.j], [q.sub.j])-graph with j = 1, 2. A graph G obtained by identifying each vertex [x.sub.i,1] of [G.sub.1] with a vertex [x.sub.i,1] of [G.sub.2] into one vertex [x.sub.i] = [x.sub.i,1] [omicron] [x.sub.i,2] with i [member of] [1, m] is called an m-identification graph and denoted as G = [[circle dot].sub.m] <[G.sub.1], [G.sub.2]>; the vertices [x.sub.1], [x.sub.2], ..., [x.sub.m] are called the identification-vertices.

Moreover, the m-identification graph G = [[circle dot].sub.m] <[G.sub.1], [G.sub.2]> defined in Definition 3 has [p.sub.1] + [p.sub.2] - m vertices and [q.sub.1] + [q.sub.2] edges. One can split each identification-vertex [x.sub.i] = [x.sub.i,1] [omicron] [x.sub.i,2] into two vertices [x.sub.i,1] and [x.sub.i,2] (called the splitting-vertices) for i[member of] [1, m], such that G is split into two parts [G.sub.1] and [G.sub.2]. For the purpose of convenience, the above procedure of producing am m-identification graph G = [[circle dot].sub.m] <[G.sub.1], [G.sub.2]> is called an m-identification operation; conversely, the procedure of splitting G = [[circle dot].sub.m] <[G.sub.1], [G.sub.2]> into two parts [G.sub.1] and [G.sub.2] is named as the m-splitting operation.

Definition4. Let [G.sub.i] be a connected ([p.sub.i], q)-graph with i = 1, 2, and let p = [p.sub.1] + [p.sub.2] - 2. If the 2-identification (p, q)-graph G = [[circle dot].sub.2] <[G.sub.1], [G.sub.2]> has a mapping f : 7(G) [right arrow] [0, q - 1] holding the following: (i) f(x) = f(y) for each pair of vertices x, y [member of] V(G), (ii) f is an odd-elegant labelling of [G.sub.i] with i = 1, 2, and (iii) [absolute value of f(V([G.sub.1])) [intersection] f(V([G.sub.2]))] = 2 and f(V([G.sub.1])) [union] f(V([G.sub.2])) [subset not equal to] [0, q - 1], then one calls G a twin odd-elegant graph (a TOE-graph), f a TOE-labelling, [G.sub.1] a TOE-source graph, [G.sub.2] a TOE-associated graph, and ([G.sub.1], [G.sub.2]) a TOE-matching pair.

We illustrate Definition 4 with Figure 2. In other words, a twin odd-elegant graph G = [[circle dot].sub.2] <[G.sub.1], [G.sub.2]> with its TOE-source graph [G.sub.1] and TOE-associated graph [G.sub.2], where ([G.sub.1], [G.sub.2]) is a TOE-matching pair.

Furthermore, if each [G.sub.i] with i = 1, 2 is a connected graph in Definition 4, and the TOE-source [G.sub.1] is a bipartite connected graph having its own bipartition ([X.sub.1], [Y.sub.1]) and a labelling f satisfying Definition 2, we call the 2-identification graph G = [[circle dot].sub.2] <[G.sub.1], [G.sub.2]> a set-ordered twin odd-elegant graph (So-TOE-graph) and f a set-ordered twin odd-elegant labelling (So-TOE-labelling). Notice that the source graph [G.sub.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 a TOE-lock-model and a TOE-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.sub.k] has an odd-elegant labelling [f.sub.k] and V([G.sub.k]) = {[x.sup.k.sub.l] : l = 1, 2, ..., [absolute value of V([G.sub.k])]} with k [member of] [1, m]. Clearly, for a [not equal to] h with a, b [member of] [1, m], there are vertices [x.sup.a.sub.i] [member of] V([G.sub.a]) and [x.sup.b.sub.j] [member of] V([G.sub.b]) such that [f.sub.a]([x.sup.a.sub.i]) = [f.sub.b]([x.sup.b.sub.j]). For example, some [G.sub.k] has a vertex [x.sup.k.sub.i] such that the label [f.sub.k]([x.sup.k.sub.i]) = 0 with k [member of] [1, m]. We can combine those vertices that have the same labels into one vertex, which gives us a new graph, denoted by G = [[circle dot].sub.[epsilon]] <[G.sub.1], [G.sub.2], ..., [G.sub.m]>. This process is called a CA-operation on [G.sub.1], [G.sub.2], ..., [G.sub.m].

(O-2) Edge-Series Operation. Given two groups of disjoint trees [G.sup.r.sub.1], [G.sup.r.sub.2], ..., [G.sup.r.sub.m] with r = 1, 2 there are vertices [x.sup.r.sub.k], [y.sup.r.sub.k] [member of] V([G.sup.r.sub.k]) with k [member of] [1, m]. Joining the vertex [y.sup.r.sub.j] with the vertex [x.sup.r.sub.j+1] by an edge for j [member of] [1, m - 1] produces a tree [H.sub.r] (denoted by [H.sub.r] = [[??].sup.m.sub.k-1] [G.sup.r.sub.k]) with r = 1, 2; next we let one vertex [u.sup.1.sub.s] [member of] V([H.sub.1]) coincide with one vertex [v.sup.2.sub.s] [member of] V([H.sub.2]) into one vertex [a.sub.s] = [u.sup.1.sub.s] [omicron] [v.sup.2.sub.s] with s = 1, 2. The resulting graph [[circle dot].sub.2] <[G.sub.1], [G.sub.2]> is just a 2-identification graph.

(O-3) Base-Pasted Operation. Given two disjoint trees [T.sub.r] (called base-trees) having vertices [x.sup.r.sub.1], [x.sup.r.sub.2], ..., [x.sup.r.sub.m] and two groups of disjoint trees [G.sup.r.sub.1], [G.sup.r.sub.2], ..., [G.sup.r.sub.m] with r = 1,2, we let a vertex [u.sup.r.sub.k] [member of] V([G.sup.r.sub.k]) coincide with the vertex [x.sup.r.sub.k] [member of] V([T.sub.r]) into one vertex [u.sup.r.sub.1] [omicron] [x.sup.r.sub.k] for k [member of] [1,m] such that the resulting tree [F.sub.r] (i.e., [F.sub.r] = [T.sub.r] [[circle dot].sup.m.sub.k=1] [G.sup.r.sub.k]) has V([F.sub.r]) = [[universal].sup.m.sub.k=1] V([G.sup.r.sub.k]), E([F.sub.r]) = ([[universal].sup.m.sub.k=1] E([G.sup.r.sub.k])) [union] E([T.sub.r]) for r = 1, 2. We overlap one vertex [w.sup.1.sub.s] [member of] V([F.sub.1]) with one vertex [z.sup.2.sub.s] [member of] V([F.sub.2]) into one vertex [b.sub.s] = [w.sup.1.sub.s] [omicron] [z.sup.2.sub.s] with s = 1, 2 to build up a 2-identification graph F = [[circle dot].sub.2] <[F.sub.1], [F.sub.2]> holding V(F1) n V([F.SUB.2]) = [av a2} and E(F) = E([F.sub.1]) [union] E([F.sub.2]).

In the following, we give the diagrams with m = 2 for edge-series operation and base-pasted operation, shown in Figures 3 and 4, respectively.

2. Main Results and Their Proofs

Lemma 5. Each star [K.sub.1,n] is a TOE-source tree of a So-TOE-tree.

Proof of Lemma 5 is shown in Figure 5. It describes the construction process of the So-TOE-tree [circle dot] <[K.sub.1,n], [K.sub.1,n]> by any TOE-source tree [K.sub.1,n].

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.sub.1], q)-graph [G.sub.1] having vertex bipartition is (X, Y), where X = {[x.sub.i] : i [member of] [1, s]}, Y = {[y.sub.j] : j [member of] [1, t]}, s + t = [p.sub.1], and min{s, t} [greater than or equal to] 2. By the hypothesis of the theorem, [G.sub.1] has a set-ordered odd-elegant labelling f1 defined by [f.sub.1]([x.sub.i]) +2 [less than or equal to] [f.sub.1]([x.sub.i+1]), i [member of] [1, s - 1]; [f.sub.1]([y.sub.1]) =

[f.sub.1]([x.sub.s]) + 1, [f.sub.1]([y.sub.j]) + 2 [less than or equal to] [f.sub.1]([y.sub.j+1]), i [member of] [l, s - 1]; [f.sub.1]([y.sub.1]) = [f.sub.1]([x.sub.s]) + 1, [f.sub.1]([y.sub.j]) + 2 [less than or equal to] [f.sub.1]([y.sub.j+1]), I [member of] [1, t - 1]; [f.sub.1]([y.sub.t]) [less than or equal to] 2q - 1. Hence, [f.sub.1](E([G.sub.1]) = {[f.sub.1](xy) = [f.sub.1](x) + [f.sub.1](y) (mod 2q) : xy [member of] E([G.sub.1])} = [[1, 2q - 1].sup.[omicron]]. It is not difficult to observe that [f.sub.1] (V([G.sub.1])) [subset] {0, 2,..., [f.sub.1]([x.sub.s]) [f.sub.1]([y.sub.1]), ..., 2q - 1}; that is, [f.sub.1](X)/2 [subset] N and ([f.sub.1](Y) + 1)/2 [subset] N.

Case 1. We construct a labelling [f.sub.2] of a new tree [T.sub.2] having q+1 vertices by the labelling [f.sub.1] such that [f.sub.2](V([T.sub.2])) = [[1, [f.sub.1]([x.sub.s]) + 1].sup.[omicron]] [union] [[[f.sub.1]([y.sub.1]) - 1, 2q - 2].sup.e], such that [f.sub.2](E([T.sub.2])) = {[f.sub.2](uv) = [f.sub.2](u) + [f.sub.2](v) (mod 2q) : uv [member of] E([T.sub.2])} = [[1, 2q - 1].sup.[omicron]], where [f.sub.2](u) = [f.sub.2](v) for u, v [member of] V([T.sub.2]). This tree [T.sub.2] can be built up in the following way: a bipartition ([U.sub.1], [V.sub.1] with [U.sub.1] = {[u.sub.i] : i [member of] [1, [s.sub.1]]} and [V.sub.1] = {[v.sub.j] : j [member of] [1, [t.sub.1]]}, where [s.sub.1] + [t.sub.1] = q + 1, such that [f.sub.2]([u.sub.i]) = 2i -1, i [member of] [1, [s.sub.1]]; [f.sub.2]([v.sub.j]) = 2([s.sub.1] - 2 + j), j [member of] [1, [t.sub.1]]. Any edge [u.sub.i][v.sub.j] [member of] E([T.sub.2]) satisfies [f.sub.2]([u.sub.i][v.sub.j]) = [f.sub.2]([u.sub.i]) + [f.sub.2]([v.sub.j]) (mod 2q) with i [member of] [1, [s.sub.1]] and j [member of] [1, [t.sub.1]]. We construct the edge set of [T.sub.2] as [mathematical expression not reproducible] such that the edge labels are [mathematical expression not reproducible]. Observe that [mathematical expression not reproducible].

Now, we can combine the vertex [y.sub.1] and [x.sub.s] of [G.sub.1] with the vertex [mathematical expression not reproducible] into one (two identification-vertices) [w.sub.1] and [w.sub.2], respectively, so we obtain the desired graph G = [[circle dot].sub.2] <[G.sub.1], [T.sub.2]>. And G has a labelling f defined as [mathematical expression not reproducible]. 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.sub.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.sub.2](V([T'.sub.2])) = [[1, [f.sub.1]([x.sub.s]) - 1].sup.[omicron]] [union] [[[f.sub.1]([y.sub.1]) - 1, 2q - 2].sup.e] U [0}, [f.sub.2](E([T'.sub.2])) = [[1, 2q - 1].sup.[omicron]], and furthermore [f.sub.2](u) [not equal to] [f.sub.2](v) for u, v [member of] V([T'.sub.2]). This tree [T'.sub.2] can be built up in the following way: a bipartition [mathematical expression not reproducible]. Any edge [u.sub.i][v.sub.j] [member of] E([T'.sub.2]) satisfies [f.sub.2]([u.sub.i][v.sub.j]) = [f.sub.2]([u.sub.i])+[f.sub.2]([v.sub.j]) (mod 2q) with i [member of] [1, [s.sub.1] - 1] and j [member of] [1, [t.sub.1] + 1]. We construct the edge set of [T'.sub.2] as {[u.sub.1][v.sub.j], [u.sub.i][v.sub.t+1] : i [member of] [2, [s.sub.1] - 1], j [member of] [1,f1]} such that the edge labels are [mathematical expression not reproducible].

Now, we can combine the vertex [x.sub.1] and [x.sub.s] of [T.sub.1] with the vertex [mathematical expression not reproducible] into one (the identified vertex) [w.sub.1] and [w.sub.2], so we obtain the desired tree G' = [[circle dot].sub.2] <[G.sub.1], [T'.sub.2]>. And G' has a labelling f defined as [mathematical expression not reproducible]. 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.sub.1]. An example for illustrating Case 2 of Theorem 6 is given by Figures 6(a), 6(c), and 6(e).

Theorem 7. Suppose that [G.sub.k] = [[circle dot].sub.2] <[G.sup.1.sub.1], [G.sup.2.sub.2]> is a So-TOE graph, where each [G.sub.k] is a source tree for k [member of] [1, m], Then G = [[circle dot].sub.2] <[H.sub.1], [H.sub.2]> obtained by the edge-series operation has a So-TOE-labelling.

Proof. By the hypothesis of the theorem, every ([p.sup.1.sub.k] + [p.sup.2.sub.k] - 2, 2[q.sub.k])-graph [G.sub.k] has a set-ordered odd-elegant source-([p.sup.1.sub.k], [q.sub.k])-graph [G.sup.1.sub.k] and an associated-([p.sup.2.sub.k], [q.sub.k])-graph [G.sup.2.sub.k] for k [member of] [1, m]. Let V([G.sup.1.sub.k]) [intersection] V([G.sup.2.sub.k]) = {[w.sup.1.sub.k], [w.sup.2.sub.k]}; the vertex set of each graph [G.sup.r.sub.k] can be partitioned into ([X.sup.r.sub.k], [Y.sup.r.sub.k]) with r = 1,2, where [X.sup.r.sub.k] = {[x.sup.r.sub.k,i] : i [member of] [1, [s.sup.r.sub.k]]}, [Y.sup.r.sub.k] = {[y.sup.r.sub.k,j] : j [member of] [1, [t.sup.r.sub.k]]}, and [s.sup.r.sub.k] + [t.sup.r.sub.k] = Pk for k e [1,m] and r = 1,2. By Definition 4, every [G.sub.k] has a So-TOE-labelling [[theta].sub.k] with k [member of] [1, m] such that [mathematical expression not reproducible].

Therefore, [[theta].sub.k](E([G.sup.r.sub.k])) = {[[theta].sub.k](xy) = [[theta].sub.k](x) + [f.sup.r.sub.k](y) (mod 2[q.sub.k]) : xy [member of] E([G.sup.r.sub.k])} = [[1, 2[q.sub.k] - 1].sup.[omicron]], where [[theta].sub.k](x) = [[theta].sub.k](y) for distinct vertices x, y [member of] V([G.sub.k]), which means [[mathematical expression not reproducible]. Clearly, the labels of other vertices of [G.sup.1.sub.k] [union] [G.sup.2.sub.k] differ from each other.

Firstly, we split [G.sub.k] into two parts [G.sup.1.sub.k] and [G.sup.2.sub.k], that is, doing a 2-splitting operation on every [G.sub.k] with k [member of] [1, m]. Secondly, our discussion focuses on [G.sup.1.sub.k] and [G.sup.1.sub.k] with k [member of] [1, m]. We construct a graph by joining the vertex [mathematical expression not reproducible] with the vertex [x.sup.r.sub.k+1,1] by an edge, where k [member of] [1, m - 1] and r = 1, 2, called [H.sub.r]. For the purpose of convenience, we set S(a, b) = [mathematical expression not reproducible]. For r = 1, 2, i [member of] [1, [s.sup.r.sub.k]], and j [member of] [1, [t.sup.r.sub.k]], we define a new labelling f as follows:

(T-1) f([x.sup.r.sub.k,i]) = [[theta].sub.k]([x.sup.r.sub.k,i]) + S(1, k - 1);

(T-2) f([y.sup.r.sub.k,j]) = [[theta].sub.k]([y.sup.r.sub.k,j]) + Q(1, k - 1) + S(k + 1, m);

(T-3) f([x.sup.r.sub.k,i] [y.sup.r.sub.k,j]) = f([x.sup.r.sub.k,i]) + f([y.sup.r.sub.k,j]) (mod [Q.sub.m]);

(T-4) [mathematical expression not reproducible].

By the labelling forms (T-1) and (T-2) above, we can verify [mathematical expression not reproducible] with k [member of] [1,m] and have the following properties: [mathematical expression not reproducible].

Computing the labelling forms (T-3) and (T-4) enables us to obtain f(E([H.sub.r])) = [[1, [Q.sub.m] - 1].sup.[omicron]] for r = 1, 2. Now, we combine the vertex [mathematical expression not reproducible] with the vertex [y.sup.2.sub.1,1] into one vertex and then combine the vertex [y.sup.1.sub.1,1] with the vertex [mathematical expression not reproducible] into one vertex. (i.e., do the 2-identification operation). Thus the labelling f is a So-TOE-labelling of G = [[circle dot].sub.2] <[H.sub.1], [H.sub.2]>; therefore, G is a So-TOE-graph too. ?

See Figures 7, 8 and 9 for understanding Theorem 7.

In experiments, for each arrangement [mathematical expression not reproducible], there are many possible constructions of G = [[circle dot].sub.2] <[H.sub.1], [H.sub.2]> for holding Theorem 7 (as shown in Figure 9).

Theorem 8. Suppose that [G.sub.k] = [[circle dot].sub.2] <[G.sup.1.sub.k], [G.sup.1.sub.k]> is a So-TOE-graph, where each G\, is a source graph for k [member of] [1, p]. Then G = [[circle dot].sub.2] <[S.sub.1], [S.sub.2]> obtained by the base-pasted operation has a So-TOE-labelling if two base-trees [T.sub.1] and [T.sub.2] are set-ordered.

Proof. By the hypothesis of the theorem, every ([p.sup.1.sub.k] + [p.sup.2.sub.k] - 2q)-graph [G.sub.k] = [[circle dot].sub.2] <[G.sup.1.sub.k], [G.sup.1.sub.k]> has a set-ordered odd-elegant source-([p.sup.1.sub.k], q)-graph [G.sup.1.sub.k] and an associated-([p.sup.1.sub.k], q)-graph [G.sup.2.sub.k] for k [member of] [1, p]. Let [G.sup.1.sub.k] [intersection] [G.sup.2.sub.k] = {[w.sup.1.sub.k], [w.sup.2.sub.k]}; the vertex set of each graph [G.sup.r.sub.k] can be partitioned [mathematical expression not reproducible]. Every [G.sub.k], by Definition 4, has a So-TOE-labelling [[pi].sub.k] with k [member of] [1, p], and [[pi].sub.k] has the following properties: [mathematical expression not reproducible].

Thus, the properties of each So-TOE-labelling [[pi].sub.k] induce [[pi].sub.k](E([G.sup.r.sub.k])) = {[[pi].sub.k](xy) = [[pi].sub.k](x) + [f.sup.r.sub.k](y) (mod 2q) : xy [member of] E([G.sup.r.sub.k])}, and also

[mathematical expression not reproducible], (2)

where [[pi].sub.k](x) = [[pi].sub.k](y) if x [not equal to] y and x, y [member of] V([G.sub.k]). In other words, we have [mathematical expression not reproducible]. The labels of other vertices of [G.sup.1.sub.k] [union] [G.sup.2.sub.k] differ from each other.

Let V([T.sub.r]) = {[z.sup.r.sub.1], [z.sup.r.sub.2], ..., [z.sup.r.sub.p]}, such that there exists a set-ordered odd-elegant labelling [mathematical expression not reproducible], and the bipartition ([U.sub.r], [V.sub.r]) of vertex set of [T.sub.r] satisfies [absolute value of [U.sub.r]] [less than or equal to] [absolute value of [V.sub.r]] for [absolute value of [U.sub.r]] = l and r = 1, 2.

Next, we discuss all graphs [G.sup.1.sub.k] and [G.sup.2.sub.k] with k [member of] [1,p] by the parity of positive integer p in the following two cases.

Case 1. For considering the case p = 2[beta] + 1 and r = 1, 2, we define a new labelling f with i [member of] [1, [s.sup.r.sub.k]] and j [member of] [1, [t.sup.r.sub.k]] in the following way:

(C-1) [mathematical expression not reproducible];

(C-2) [mathematical expression not reproducible];

(C-3) [mathematical expression not reproducible];

(C-4) [mathematical expression not reproducible];

(C-5) f([x.sup.r.sub.k,i], [y.sup.r.sub.k,i]) = f([y.sup.r.sub.k,j]) + f([x.sup.r.sub.k,i]) (mod 2p(q + 1)-2).

Based upon the labelling forms (C-1)-(C-4), we compute

[mathematical expression not reproducible].(3)

Thereby, we have shown that [[universal].sup.2.sub.r=1] [[universal].sup.p.sub.k=1] f(V([[G.sup.r.sub.k])) [subset] [0, 2p(q + 1) - 3] and

[mathematical expression not reproducible], (4)

and furthermore the labels of vertices, except f([x.sup.1.sub.p,s]) = f([y.sup.2.sub.1,1]) and f(4[x.sup.2.sub.p,s]) = f([y.sup.1.sub.1,1]), differ from each other, and the labels of edges differ from each other.

Next, after computing the labelling forms (C-5) with k [member of] [1, p], we obtain

f(B([G.sup.r.sub.2k-1])) = [[A(2), B(1)].sup.[omicron]], k [member of] [1, [beta] + 1];

f(E([G.sup.r.sub.2k])) = [[A(1), B(1)].sup.[omicron]], k [member of] [1, [beta]].

(mod 2p(q + 1) - 2), (5)

where A(x) = M + 1 + 2( + 1)([beta] + 2k - x) and B(p) = M - 3 + 2(q + 1)([beta] + 2k - p). By the above deduction, we can know that

[mathematical expression not reproducible], (6)

where F = {M - 1 + 2(q + 1)([beta] + 1 + k), M + 1 + 2(q + 1)k : k = 0, 1, 2, ..., [beta] - 1}. Next, for each vertex [z.sup.r.sub.k] [member of] V([T.sub.r]) with k [member of] [1, p] and r = 1,2, we set

[mathematical expression not reproducible]. (7)

According to formula (7), we obtain f([z.sup.r.sub.i] [z.sup.r.sub.j]) = f([z.sup.r.sub.i]) + f([z.sup.r.sub.j]) [member of] F with i [member of] [1, l], j [member of] [ + 1, p], and r = 1, 2, which means

f(F([T.sub.r])) = F. (8)

Doing a CA-operation on [G.sup.r.sub.k] and [T.sub.r] having labelling f for k [member of] [1, p] produces a new graph [S.sub.r] with r = 1, 2. Now, we combine the vertex [mathematical expression not reproducible] with the vertex pj2 1 into one vertex [mathematical expression not reproducible] and moreover identify the vertex [y.sup.1.sub.1,1] with the vertex [mathematical expression not reproducible] into one vertex [mathematical expression not reproducible] (i.e., do a 2-identification operation).

By Definitions 2 and 4 and formulae (3)-(8), the labelling f is a So-TOE-labelling of G = [[circle dot].sub.2] <[S.sub.1], [S.sub.2]>. Hence, G is a SoTOE-graph. Here, we have proven Case 1. For understanding Case 1, see Figures 10 and 11.

Case 2. We, for the case p = 2[beta] and r = 1,2, define a new labelling f for i [member of] [1, [s.sup.r.sub.k]] and j [member of] [1, [t.sup.r.sub.k]] in the following way:

(L-1) [mathematical expression not reproducible];

(L-2) [mathematical expression not reproducible];

(L-3) [mathematical expression not reproducible];

(L-4) [mathematical expression not reproducible];

(L-5) f([x.sup.r.sub.k,i][y.sup.r.sub.k,j]) = f([y.sup.r.sub.k,j]) + f([x.sup.r.sub.k,i]) (mod 2p(q + 1) - 2).

From the above labelling forms (L-1)-(L-4), we can compute

[mathematical expression not reproducible]. (9)

Thereby, we conclude that [[universal].sup.2.sub.r=1] [[universal].sup.p.sub.k=1] f(V([[G.sup.r.sub.k])) = [0, 2p(q + 1) - 3] and

[mathematical expression not reproducible], (10)

in which the labels of vertices and edges, except [mathematical expression not reproducible], differ from each other, respectively.

Again, by computing the labelling form (L-5) for each k e [1, p],we obtain

[mathematical expression not reproducible], (11)

where [alpha](x) = 2(q + 1)([beta] + 2k - x) - 1 and p(y) = 2(q+ 1)(p + 2k - y) - 5.

Synthesizing the above argument, we get [[universal].sup.p.sub.k=1] f(E([G.sup.r.sub.k])) = [[1, 2p(q + 1) - 3].sup.[omicron]] \ F', where the set F' = [2(q + 1)([beta] + k) - 3 (mod2p(q + 1) - 2) : k [member of] [1, 2[beta] - 1]}. For each vertex [z.sup.r.sub.k] [member of] [T.sub.r] with e [1, p] and r = 1, 2, we set

[mathematical expression not reproducible]. (12)

The above formula (12) enables us to obtain /([z.sup.r.sub.i][z.sup.r.sub.j]) = f([z.sup.r.sub.i]) + f([z.sup.r.sub.j]) [member of] F' with i [member of] [1, 1], j [member of] [l + 1, p], and r = 1, 2. Thereby, we have shown

f(E([T.sub.r])) = F'. (13)

After performing a CA-operation on [G.sup.r.sub.k] and Tr having labelling f for k [member of] [1, p], then we obtain a new graph [S.sub.r] with r = 1,2. Now, we overlap the vertex [mathematical expression not reproducible] with the vertex [y.sup.2.sub.1,1] into one vertex [mathematical expression not reproducible] and overlap the vertex [y.sup.1.sub.1,1] with the vertex [mathematical expression not reproducible] into one vertex [mathematical expression not reproducible] (i.e., do a 2-identification operation) in order to obtain G = Q2{S1,S2). 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 Figures 12 and 13.

The proof of the theorem is complete. ?

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 the 2-identification graph G = [[circle dot].sub.2] <[G.sub.1], [G.sub.2]>, called twin odd-elegant graph. We think that finding all possible TOE-matching pairs (G, H) defined in Definition 4 maybe interesting for a given TOE-graph G with an odd-elegant labelling g. Let

[M.sub.TOE] (G, g)

= {H : (G, H) is a TOE-matching pair} (14)

be the set of all TOE-associated graphs H, so, we have a TOE-book [mathematical expression not reproducible] with book-back G and book-pages H [member of] [M.sub.TOE](G, g).

We should pay attention to the following problems:

(i) Since G = [[circle dot].sub.2](G, H) [intersection] [[circle dot].sub.2](G, H') for any pair of book-pages [mathematical expression not reproducible]?

(ii) Suppose that G has m pairwise different odd-elegant labellings [g.sub.1], [g.sub.2], ..., [g.sub.m]. Find some possible relationships among TOE-books B(G, [g.sub.i] with i [member of] [1, m].

For the future researching work on Topsnut-GPWs, we propose the following.

Conjecture 9. Let each [[circle dot].sub.2] <[G.sup.1.sub.k], [G.sup.1.sub.k]> be a TOE-graph for k [member of] [1, m] with m [greater than or equal to] 2. The 2-identification graph G = [[circle dot].sub.2] <[H.sub.1], [H.sub.2]> obtained by the edge-series operation (resp., the base-pasted operation) admits a TOE-labelling. r

Conjecture 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 Theorem 8 is quite tremendous; (iii) the 2-identification graphs 02 (H1,H2) of Theorem 7 and [[circle dot].sub.2] <[S.sub.1], [S.sub.2]> of Theorem 8 are the compound type of Topsnut-GPWs based on smaller scale of Topsnut-GPWs [G.sub.k] = [[circle dot].sub.2] <[G.sup.1.sub.k], [G.sup.2.sub.k]> with k [member of] [1,m], and they induce the TOE-books B([H.sub.1], f) and B([S.sub.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.

https://doi.org/10.1155/2018/9482345

Data Availability

The data used to support the findings of this study are available from the corresponding author upon request.

Conflicts of Interest

The authors declare that they have no conflicts of interest.

Acknowledgments

This work was supported by the National Key R&D Program of China (no. 2016YFB0800700) and the National Natural Science Foundation of China (nos. 61572046, 61502012, 61672050, 61672052, 61363060, and 61662066).

References

[1] X. Suo, Y. Zhu, and G. S. Owen, "Graphical passwords: a survey," in Proceedings of the 21st Annual Computer Security Applications Conference (ACSAC '05), pp. 463-472, Tucson, Ariz, USA, December 2005.

[2] R. Biddle, S. Chiasson, and P. C. Van Oorschot, "Graphical passwords: learning from the first twelve years," ACM Computing Surveys, vol. 44, no. 4, Article 19:1-41. Technical Report TR-0909, School of Computer Science, Carleton University, Ottawa, Canada. 2009. (25 pages, 145 reference papers), 2012.

[3] H. Gao, W. Jia, F Ye, and L. Ma, "A survey on the use of graphical passwords in security," Journal of Software, vol. 8, no. 7, pp. 320-329, 2013.

[4] "QR Code Essentials". Denso ADC. 2011. Retrieved 12 March 2013.

[5] "QR Code features". Denso-Wave. Archived from the original on 2013-01-29. Retrieved 3 October 2011.

[6] X. Suo, "A Study of Graphical Password for Mobile Devices," in Mobile Computing, Applications, and Services, vol. 130 of Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, pp. 202-214, Springer International Publishing, Cham, 2014.

[7] B. Yao, H. Sun, X. Zhang, H. Wang, J. Li, and G. Yan, "Graph theory towards designing graphical passwords for mobile devices," in Proceedings of the 2017 IEEE 2nd Information Technology, Networking, Electronic and Automation Control Conference (ITNEC), pp. 1640-1644, Chengdu, China, December 2017

[8] H. Wang, J. Xu, and B. Yao, "Exploring new cryptographical construction of complex network data," in Proceedings of the 1st IEEE International Conference on Data Science in Cyberspace, DSC 2016, pp. 155-160, June 2016.

[9] H. Wang, J. Xu, and B. Yao, "The key-models and their lock-models for designing new labellings of networks," in Proceedings of the 2016 IEEE Advanced Information Management, Communicates, Electronic and Automation Control Conference, IMCEC 2016, pp. 565-568, October 2016.

[10] H. Wang, J. Xu, and B. Yao, "Twin Odd-graceful Trees Towards Information Security," in Proceedings of the 7th International Congress of Information and Communication Technology, ICICT 2017, pp. 15-20, Elsevier Science Publishers B. V, February 2017.

[11] F. Harary and E. M. Palmer, Graphical enumeration, Academic Press, 1973.

[12] J. A. Gallian, "A Dynamic Survey of Graph Labeling," The Electronic Journal of Combinatorics, vol. 17, DS6. (440 pages, 2265 reference papers), 2013.

[13] X. Zhou, B. Yao, and X. Chen, "Every lobster is odd-elegant," Information Processing Letters, vol. 113, no. 1-2, pp. 30-33, 2013.

[14] J. A. Bondy and U. S. R. Murty, Graph Theory, Springer, London, UK, 2008.

[15] B. Yao, H. Cheng, M. Yao, and M. Zhao, "A note on strongly graceful trees," Ars Combinatoria, vol. 92, pp. 155-169, 2009.

Hongyu Wang (iD), (1) Jin Xu, (1) Mingyuan Ma, (1) and Hongyan Zhang (2)

(1) School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China

(2) School of Management Science and Engineering, Shandong Normal University, Jinan 250014, China

Correspondence should be addressed to Hongyu Wang; why5126@pku.edu.cn

Received 11 January 2018; Accepted 1 March 2018; Published 11 April 2018

Academic Editor: Zheng Yan

Caption: 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.

Caption: Figure 2: The formation process of Definition 4.

Caption: Figure 3: A scheme of the edge-series operation.

Caption: Figure 4: A scheme of the base-pasted operation.

Caption: Figure 5: An example of illustrating Lemma 5.

Caption: Figure 6: Examples of Theorem 6.

Caption: Figure 7: Four So-TOE-graphs [G.sub.k] with k e [1,4] described in the proof of Theorem 7.

Caption: Figure 8: A So-TOE-graph made by the graphs shown in Figure 7 for illustrating Theorem 7.

Caption: Figure 9: Another So-TOE-graph made by the graphs shown in Figure 7 for illustrating Theorem 7.

Caption: Figure 10: Seven So-TOE-graphs [G.sub.k] with k [member of] [1, 7] and two base-trees [T.sub.1] and [T.sub.2] described in the proof of Case 1 of Theorem 8.

Caption: Figure 11: A So-TOE-graph [[circle dot].sub.2] <[S.sub.1], [S.sub.2]> made by the graphs shown in Figure 10 for understanding the proof of Case 1 of Theorem 8.

Caption: Figure 12: Six So-TOE-graphs [G.sub.k] with k [member of] [1,6] and two base-trees [T.sub.1] and [T.sub.2] described in the proof of Case 2 of Theorem 8.

Caption: Figure 13: A So-TOE-graph [[circle dot].sub.2] <[S.sub.1], [S.sub.2]> made by the graphs shown in Figure 12 for understanding the proof of Case 2 of Theorem 8.
COPYRIGHT 2018 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2018 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Wang, Hongyu; Xu, Jin; Ma, Mingyuan; Zhang, Hongyan
Publication:Security and Communication Networks
Date:Jan 1, 2018
Words:6535
Previous Article:A General Architecture for Multiserver Authentication Key Agreement with Provable Security.
Next Article:Reliable Collaborative Filtering on Spatio-Temporal Privacy Data.
Topics:

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters