Printer Friendly

Edge disjoint Hamilton cycles in Knodel graphs.

The vertices of the Knodel graph [W.sub.[DELTA],n] on n [greater than or equal to] 2 vertices, n even, and of maximum degree [DELTA], 1 [less than or equal to] [DELTA] [less than or equal to] |lo[g.sub.2](n)|, are the pairs (i, j) with i = 1, 2 and 0 [less than or equal to] j [less than or equal to] [n/2] - 1. For 0 [less than or equal to] j [less than or equal to] [n/2] - 1, there is an edge between vertex (1, j) and every vertex (2, j + [2.sup.k] - 1 (mod [n/2])), for k = 0, 1, 2,..., [DELTA] - 1. Existence of a Hamilton cycle decomposition of [W.sub.k,2k], k [greater than or equal to] 6 is not yet known, see Discrete Appl. Math. 137 (2004) 173-195. In this paper, it is shown that the k-regular Knodel graph [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], k [greater than or equal to] 6 has [k/2] J - 1 edge disjoint Hamilton cycles.

Keywords: Knodel Graphs, Hamilton Cycle Decomposition, Tensor Product, Bieulerian Graph

1 Introduction.

All graphs considered here are simple and finite unless otherwise stated. Let [C.sub.k] (resp.[P.sub.k]) denote the cycle (resp. path) on k vertices. For a graph G, if its edge set E(G) can be partitioned into [E.sub.1],[E.sub.2],... ,[E.sub.k] such that <[E.sub.i]> = H ,for all i, 1 [less than or equal to] i [less than or equal to] k, then we say that H decomposes G. A k-factor of G is a k-regular spanning subgraph of it. A k-factorization of a graph G is a partition of the edge set of G into [E.sub.1], [E.sub.2],... , [E.sub.s] such that <[E.sub.i]>, 1 [less than or equal to] i [less than or equal to] s, is a k-factor. We say that a k-regular graph G admits a Hamilton cycle decomposition, if the edge set of G can be partitioned into Hamilton cycles or Hamilton cycles together with a 1-factor according as k is even or odd, respectively. If [H.sub.1], [H.sub.2],... , [H.sub.k] are edge disjoint subgraphs of G such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then we write G = [H.sub.1] [direct sum] [H.sub.2] [direct sum]... [direct sum] [H.sub.k]. The complete graph on n vertices is denoted by [K.sub.n]. Let G be a bipartite graph with bipartition (X, Y), where X = {[x.sub.0], [x.sub.1],... , [x.sub.n-1]}, Y = {[y.sub.0], [y.sub.1],... , [y.sub.n-1]}; the edge [x.sub.i][y.sub.i+l] is called an edge of jump l from X to Y in G, where addition is taken modulo n; the same edge is called an edge of jump n - l from Y to X. If G contains the edges [F.sub.l](X,Y) = {[x.sub.i][y.sub.i+l]|0 [less than or equal to] i [less than or equal to] n - 1, where addition in the subscript is taken modulo n}, 0 [less than or equal to] l [less than or equal to] n - 1, then we say that G has the 1-factor of jump l from X to Y. Clearly, if G = [K.sub.n, n], then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Note that [F.sub.i](X,Y) = [F.sub.n-i](Y,X), 0 [less than or equal to] i [less than or equal to] n - 1, where we assume [F.sub.n](X, Y) = [F.sub.0](X, Y) = [F.sub.0](Y, X).

An anti-directed path P is a digraph, whose underlying graph is a path, in which any two consecutive arcs of P are either directed toward or away from the common incident vertex in P. Similarly, we define anti-directed cycles, see Figures 1(a) and 1(b). A digraph [??] = (V, A) is denoted by [??]. A digraph [??] = (V, A) is said to be k-diregular if [d.sup.+] (x) = k = [d.sup.-] (x) for every x [member of] V. If x is the tail, and y is the head of an arc of [??], then it is denoted by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. A digraph [??] is called aneulerian if [??] has an Euler tour T such that any two consecutive edges of T are either directed toward or away from the common incident vertex in [??], see Figures 1(c) and 1(d). A directed graph is called bieulerian if it is both eulerian (that is, it contains a directed Euler tour) and aneulerian, see Figures 1(c) and 1(d); consequently, a digraph which admits an aneulerian tour cannot be k-diregular for k [greater than or equal to] 3.

[FIGURE 1 OMITTED]

For two graphs G and H their tensor product, denoted by G x H, has vertex set V(G) x V(H) in which ([g.sub.1], [h.sub.1])([g.sub.2], [h.sub.2]) is an edge in G x H whenever [g.sub.1][g.sub.2] [member of] E(G) and [h.sub.1][h.sub.2] [member of] E(H). Similarly, for two digraphs [??] and [??] their tensor product, denoted by [??] x [??], has vertex set V([??]) x V([??]) in which [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is an arc in [??] x [??] whenever [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [member of] A([??]) and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [member of] A([??]), where A([??]) denotes the arc set of [??]. Note that if xx is a loop at x in G (resp. H), then x x V(H) (resp. V(G) x x) induces a copy of H (resp. G) in G x H. A circulant graph X = Circ(n; L) is a graph with vertex set V(X) = {[u.sub.0], [u.sub.1],... , [u.sub.n-1]} and edge set E(X) = {[u.sub.i][u.sub.i+l] | i [member of] Zn, l [member of] L}, where L [[subset].bar] {1,2,..., [n/2]}. The elements of L are called distances of the circulant graph and L is called the set of distances. A circulant digraph [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a digraph with vertex set V([??]) = {[u.sub.0], [u.sub.1],... , [u.sub.n-1]} and arc set [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where L [[subset].bar] {1,2,... , n - 1} . The elements of L are called distances of the circulant digraph. The underlying graph of a digraph D is the undirected graph obtained from [??] by simply deleting the orientations of the arcs of [??]. For graph theoretical terms not defined here, see [2,6].

Knodel graph was originally introduced in [22]. The family of Knodel graphs has been formally defined by Fraigniaud and Peters [7]. Knodel graph [W.sub.[DELTA],n] is a regular graph of even order n and degree [DELTA], 1 [less than or equal to] [DELTA] [less than or equal to] |[log.sub.2](n)|. Knodel graphs are used as competitors for hypercubes in the domains of broadcasting and gossiping. The gossiping problem, as described by Knodel in [22] is the following: "Given n persons, each having an information, want to distribute their information among them in binary calls, each call taking a constant time, how long must it take before each knows all the information among them?" Broadcasting is a similar problem where only one person (the originator) has all the information that needs to be distributed to a group of people in binary calls. Consequently, they deal with problems in dissemination of information in interconnection networks. Every interconnection network can be represented by means of a graph. If this graph has n vertices, the minimum time required for broadcasting is |[log.sub.2] n]. Such graphs are known as minimal broadcasting graphs. For more details on minimal broadcasting and gossiping graphs, see [11,19,20]. There are several papers dealing with Knodel graphs, especially because some subfamilies of Knodel graphs have good properties in terms of broadcasting and gossiping and Fault-Tolerance, see [1,10,14,18,21,23]. In particular, for n = [2.sup.k], the Knodel graph [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], of order n and degree k, turns out to be a minimum broadcast graph. It is known that, the diameter of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], see [9]. It is known that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is vertex-transitive but not edge-transitive, see [8]. Recently, it has been proved, see [4], that the automorphism group of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the dihedral group [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and in the same paper a short proof is given for the diameter of the Knodel graph [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] . For other properties of the Knodel graphs and modified Knodel graphs, see [5,12,13,15-17].

It is known that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is Hamilton cycle decomposable and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is bipancyclic, that is, every cycle of length l, 4 [less than or equal to] l [less than or equal to] [2.sup.k] exists, see [8]. A detailed account of various properties the Knodel graphs and comparison with other interconnection networks has been given in the survey [8].

It is not yet known whether the Knodel graphs [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], k [greater than or equal to] 6 admit a Hamilton cycle decomposition or not [8]. In this paper, we prove that the k-regular Knodel graph [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], k [greater than or equal to] 6 has [k/2] - 1 edge disjoint Hamilton cycles, that is, the edge set of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], k [greater than or equal to] 6 can be partitioned into [k/2] - 1 Hamilton cycles together with a 2-factor, if k is even and [k/2]- 1 Hamilton cycles together with a 3-factor, if k is odd.

2 Definitions and Preliminaries.

Definition 2.1 [8] The Knodel graph on n [greater than or equal to] 2 vertices, n even, and maximum degree [DELTA], 1 [less than or equal to] [DELTA] [less than or equal to] [[log.sub.2](n)J, is denoted by [W.sub.[DELTA],n]. The vertices of [W.sub.[DELTA],n] are the pairs (i, j) with i = 1, 2 and 0 [less than or equal to] j [less than or equal to] [n/2] - 1. For every 0 [less than or equal to] j [less than or equal to] [n/2] - 1, there is an edge between vertex (1, j) and every vertex (2, j + [2.sup.k] - 1 (mod [n/2])), for k = 0, 1, 2,..., [DELTA] - 1. It is a bipartite graph containing the jump 1-factors [2.sup.k]-1, k = 0, 1, 2,...,[DELTA]-1.

For each k, 0 [less than or equal to] k [less than or equal to] [DELTA]-1, the edges (1, j)(2, j + [2.sup.k] -1 (mod [n/2])), 0 [less than or equal to] j [less than or equal to] [n/2] -1, induce a 1-factor of jump [2.sup.k]-1 in [W.sub.[DELTA],n].

The union of the 1-factors of jumps 0 and 1 from X to Y of [W.sub.[DELTA],n] is a Hamilton cycle, where we assume that X = {(1, j) |0 [less than or equal to] j [less than or equal to] [n/2] - 1} and Y = {(2, j) | 0 [less than or equal to] j [less than or equal to] [n/2] - 1} are the bipartition of [W.sub.[DELTA],n]. It is known that the graphs [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], are Hamilton cycle decomposable, see [8]. Based on this observation the following problem is raised in [8].

Problem 2.1 [8] Is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Hamilton cycle decomposable for any k [greater than or equal to] 2?

In this paper, we prove that the k-regular Knodel graph [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], k > 6 has [k/2] - 1 edge disjoint Hamilton cycles.

Definition 2.2 (Bipartite incident graph [8]). Let [??] = (V, A) be a digraph of order n, with V = {0, 1,... , n- 1}. The bipartite incident graph of [??] is the (undirected) bipartite graph H = ([V.sub.1], [V.sub.2], E) of order 2n, where [V.sub.i] = {[0.sub.i], [1.sub.i],... , [(n- 1).sub.i]}, i = 1, 2, and that for any arc [??] of [??], there corresponds an edge [i.sub.1][j.sub.2] [member of] E(H) with [i.sub.1] [member of] [V.sub.1] and [j.sub.2] [member of] [V.sub.2] and for each i [member of] V, there is an edge [i.sub.1][i.sub.2] [member of] E(H), where [i.sub.1] [member of] [V.sub.i] and [i.sub.2] [member of] [V.sub.2] in H.

[FIGURE 2 OMITTED]

From the Definition 2.2, it is easy to see that the Knodel graph [W.sub.[DELTA], n] is the bipartite incident graph of the circulant digraph [??] with vertex set {0, 1, 2,... , [n/2] - 1} and arc set consists of the arcs of distance l, l [member of] L = {[2.sup.k] - 1, 0 [less than or equal to] k [less than or equal to] [DELTA] - 1}. In otherwords, [W.sub.[DELTA], n] is the underlying graph of [??] x [[??].sub.2], where [[??].sub.2] denotes an arc.

Let [[??].sub.k] denote the circulant digraph [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where L = {[2.sup.j] - 1|1 [less than or equal to] j [less than or equal to] k - 1} and let [[??]'.sub.k] denote the graph obtained from [[??].sub.k] by attaching a directed loop at each of its vertices, that is, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], see Figure 2. Clearly, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is isomorphic to the underlying graph of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Definition 2.3 [3] Let [??] be a 2-diregular digraph which does not have a pair of arcs having the same tail and head, but may have directed loops. IfG admits an uniformly odd aneulerian tour (UOAT), that is, an aneulerian tour in which no proper closed subtrail is of even length, then G is called an UOAT digraph (in fact, one can check that if a 2-diregular digraph admits an aneulerian tour T, then each proper closed subtrail of T is of odd length).

The proof of the following theorem is similar to the proof of Theorem 2.1 of [3].

Theorem 2.1 Let [??] be a 2-diregular digraph which does not have a pair of arcs having the same tail and head, but may have directed loops. Then the underlying graph of the digraph [??] x [[??].sub.2] is a Hamilton cycle if and only if [??] is an UOAT digraph.

Proof: Let [??] = (V, A) with V([??]) = {[v.sub.0], [v.sub.1], [v.sub.2],... , [v.sub.n]}. Let [K.sub.2] = [??]. To each arc [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], possibly with i = j, in [??] there corresponds an unique arc [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in [??] x [[??].sub.2] and similarly corresponding to each arc [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], possibly with r = s, in [??] x [[??].sub.2] there corresponds an arc [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], may be a directed loop, in [??]. Clearly, [??] = [??] x [[??].sub.2] is bipartite digraph with bipartition (X, Y), where X = V([??]) x x = {([v.sub.i], x)|[v.sub.i] [member of] V([??])} and Y = V([??]) x y = {([v.sub.i], y)|[v.sub.i] [member of] V([??])}. In [??] all the vertices in X have only outdegree, namely 2, and all the vertices in Y have only indegree 2. Hence the underlying graph of [??] x [[??].sub.2] is a 2-regular graph. First assume that the underlying graph of [??] x [[??].sub.2] is a spanning cycle C. As each vertex in X has only outdegree and each vertex in Y has only indegree, while we trace along C the corresponding arcs in [??] trace an anti-directed tour T. We claim that T is an aneulerian tour. Observe that if ([v.sub.i], x)([v.sub.i], y) is an edge of C, then its corresponding arc in T is a directed loop at [v.sub.i], see Figure 3. We claim that no proper closed subtrail of T is of even length. Let [v.sub.k] be the origin of a proper closed subtrail [T.sub.1] of T. Without loss of generality assume that C visits ([v.sub.k], x) prior to ([v.sub.k], y). Hence [T.sub.1] arises out of the ([v.sub.k], x)-([v.sub.k], y) section of C and this section is of odd length as [??] x [[??].sub.2] is a bipartite digraph. Hence T1 is of odd length. Hence T is an aneulerian tour. Thus [??] is an UOAT digraph.

Conversely, assume that [??] is an UOAT digraph. Let T be an aneulerian tour of [??] with the origin [v.sub.0]. Now we describe a Hamilton cycle in the underlying graph of [??] x [[??].sub.2] from the vertex ([v.sub.0], x) as follows: If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the first arc of T, then take the edge ([v.sub.0], x)([v.sub.1], y) in the underlying graph of [??] x [[??].sub.2] for the Hamilton cycle. The second arc of T would be [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then take the edge ([v.sub.1], y)([v.sub.2], x) in the underlying graph of [??] x [[??].sub.2]. As we move along T, the corresponding edges of the underlying graph of [??] x [[??].sub.2] induce a Hamilton cycle in the underlying graph of [??] x [[??].sub.2]; for otherwise, the corresponding arcs of an nonspanning even cycle in the underlying graph of [??] x [[??].sub.2] would yield a proper closed subtrail of even length in T, a contradiction. Hence as we trace along T, the corresponding edges of the underlying graph of [??] x [[??].sub.2] induce a Hamilton cycle.

[FIGURE 3 OMITTED]

This completes the proof of the theorem. []

Theorem 2.2 Let [??] be a 2-diregular digraph which does not have a pair of arcs having the same tail and head, but may have directed loops. Then the underlying graph of [??] x [[??].sub.2] is a Hamilton cycle if and only if [??] is bieulerian.

Proof: First assume that the underlying graph [??] x [[??].sub.2] is a Hamilton cycle C. Then by Theorem 2.1 [??] has an UOAT. As [??] is diregular, [??] is eulerian. Thus [??] is bieulerian.

Conversely, assume that [??] is bieulerian. Let T be an aneulerian tour of [??]. If we proceed as in the proof of Theorem 2.1, when we move along the aneulerian tour T, the corresponding edges in the underlying graph of [??] x [[??].sub.2] induce a Hamilton cycle.

This completes the proof of the theorem. []

3 Edge Disjoint Hamilton Cycles of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In this section we prove that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] contains [k/2] - 1 edge disjoint Hamilton cycles.

The following Theorem 3.1 is proved in [8].

Theorem 3.1 [8] For any even m and 1 [less than or equal to] [DELTA] [less than or equal to] [[log.sub.2](m)], it is possible to construct [W.sub.[DELTA]+1,2m] by taking two disjoint copies of [W.sub.[DELTA],m] and linking the vertices of the copies by a certain perfect matching. []

Next we decompose the digraph [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where L = {[2.sup.j] - 1|1 [less than or equal to] j [less than or equal to] k - 1}, into two digraphs in the following way to proceed further. Let V([[??].sub.k] ) = {0, 1, 2,... , [2.sup.k-1] - 1}. First we decompose [[??].sub.k] into two digraphs [[??].sub.k,e] and [[??].sub.k,o], where [[??].sub.k,e] (resp. [[??].sub.k,o]) is the spanning subdigraph of [[??].sub.k] in which the indegree of each of the even (resp. odd) vertices, namely, 0, 2,... , [2.sup.k-1] - 2 (resp. 1, 3,... , [2.sup.k-1] -1), is zero. That is [[??].sub.k, e] (resp. [[??].sub.k,o]) is the spanning subdigraph of [[??].sub.k] obtained by deleting the set of arcs having their tails at the odd (resp. even) vertices of [[??].sub.k]. Each arc of [[??].sub.k,e] is directed from an even vertex to an odd vertex and each arc of [[??].sub.k, o] is directed from an odd vertex to an even vertex (see Figure 4 for k = 5).

[FIGURE 4 OMITTED]

Lemma 3.1 The underlying graphs of the digraphs [[??].sub.k,e] and [[??].sub.k,o] are isomorphic to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: [[??].sub.k, e] can be viewed as a bipartite graph by placing the even vertices, in the increasing order, in the partite set X and the odd vertices, in the increasing order, in the other partite set Y. Then the arcs of distance [2.sup.l] - 1, 1 [less than or equal to] l [less than or equal to] k - 1, in [[??].sub.k,e], considering it as a subdigraph of [[??].sub.k], become the arcs of jump [2.sup.l-1] - 1 from X to Y in [[??].sub.k, e] in the bipartite structure of it and thus the underlying graph of [[??].sub.k, e] is isomorphic to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], see Figure 5(a), when k = 5. To prove the underlying graph of [[??].sub.k,o] is isomorphic to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we establish an isomorphism between [[??].sub.k, e] and [G.sub.k, o] by mapping the vertex i of [[??].sub.k, e] to i + 1, where the addition is taken modulo [2.sup.k-1], of [[??].sub.k, o] . []

Recall that [[??]'.sub.k] is the digraph obtained from [[??].sub.k] by adding a loop at each of its vertices and, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is isomorphic to the underlying graph of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

First we explain the proof technique of Theorem 3.2 and the lemmas used in its proof. By Theorem 2.2, finding [k/2] - 1 Hamilton cycles of Knodel graph [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is equivalent to finding [k/2] - 1 arc-disjoint spanning 2-diregular subdigraphs of [[??]'.sub.k] so that each of the subdigraphs is bieulerian. Hence we shall obtain [k/2] - 1 arc-disjoint spanning 2-diregular subdigraphs of [[??]'.sub.k] such that each of which is bieulerian, if k is even, and with a directed 1-factor (that is, [d.sup.+] (v) = [d.sup.-] (v) = 1 for each v) if k is odd. To establish this, in Lemma 3.2, first we shall obtain [k/2] - 1 subdigraphs [[??].sub.i,e], 1 [less than or equal to] i [less than or equal to] [k/2] - 1, and another [k/2] - 1, subdigraphs [[??].sub.i,o], 1 [less than or equal to] i [less than or equal to] [k/2] - 1 out of [[??].sub.k,e] and [[??].sub.k,o], respectively. Obtain the digraph [[??].sub.i] = [[??].sub.ie] [union] [[??].sub.i,o], 1 [less than or equal to] i [less than or equal to] [k/2] - 1. We shall prove that [[??].sub.i], 1 [less than or equal to] i [less than or equal to] [k/2] - 1, together with some "appropriate" directed loops at some of its vertices is a spanning 2-diregular bieulerian subdigraph of [[??]'.sub.k], see Lemma 3.3. Using this, in Theorem 3.2, we prove the existence of [k/2] - 1 edge disjoint Hamilton cycles in [??].

We shall prove what we have told above in the rest of the paper.

[FIGURE 5 OMITTED]

Remark 3.1 Let G be a bipartite graph with bipartition (X, Y) and | X | = |Y | = n. Let Fi(X, Y) and [F.sub.j](X, Y), i [not equal to] j, be two 1-factors of jump i and j, respectively, from X to Y in G. Let H = Fi(X, Y) [union] [F.sub.j](X, Y). Note that [F.sub.j](X, Y) = [F.sub.n-j](Y, X). If gcd (n, i + n-j (mod n)) = k, then H is the union of k disjoint cycles of same length. We shall use this fact in the proof of the next lemma; in particular, if gcd(n, i + n - j (mod n)) = 1, then [F.sub.i](X, Y) [union] [F.sub.j](X, Y) is a Hamilton cycle of G.

Lemma 3.2 There exist [k/2] - 1 arc-disjoint spanning subdigraphs [[??].sub.j,e],1 [less than or equal to] j [less than or equal to] [n/2] - 1, of [[??].sub.k,e], where each [[??].sub.j, e] is the union of [2.sup.j-1] disjoint anti-directedpaths whose origins and termini be denoted by [A.sub.j] (c V([G.sub.k])), and, also there exists [k/2] - 1 arc-disjoint spanning subdigraphs [[??].sub.j,o], 1 [less than or equal to] j [less than or equal to] [k/2] - 1, of [[??].sub.k, o], where each [[??].sub.j, o] is the union of [2.sup.j-1] disjoint anti-directed paths whose origins and termini are also [A.sub.j]; that is, the set of origins and termini of the anti-directed paths of [[??].sub.j,e] is the same as the set of origins and termini of the anti-directed paths of [[??].sub.j,o]; moreover [A.sub.i] [intersection] [A.sub.j] = [??] for i [not equal to] j.

Proof: [[??].sub.k] is the circulant digraph with distance set {[2.sup.j] - 1|1 [less than or equal to] j [less than or equal to]k - 1}. Let [[??].sub.k,e] and [[??].sub.k,o] be the spanning subdigraphs of [[??].sub.k] defined as above.

Partition the distance set {[2.sup.j] - 1|1 [less than or equal to] j [less than or equal to] k - 2} of [[??].sub.k] into [k/2] - 1 2-subsets {[a.sub.j] = [2.sup.j] - 1, [b.sub.j] = [2.sup.k-1-j] - 1},1 [less than or equal to] j [less than or equal to] [k/2] - 1, if k is even and, with one more singleton subset having only one distance, namely [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], if k is odd. For each of these pairs of distances, we shall obtain a pair of spanning subdigraphs [[??].sub.j, e] and [[??].sub.j, o] of [[??].sub.k, e] and [[??].sub.k, o], respectively, such that each of the digraphs [[??].sub.j,e] and [[??].sub.j,o] is the union of [2.sup.j-1] vertex disjoint anti-directed paths.

Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], 1 [less than or equal to] j [less than or equal to] [k/2] - 1, be the spanning subdigraph of [[??].sub.ke], witharcset [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The underlying graph of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], is a bipartite graph, by Lemma 3.1, with [2.sup.k-2] vertices on each of its partite sets and its edge set consists of the edges of jumps [2.sup.j-1] - 1 and [2.sup.k-j-2] - 1, from X to Y, where X = {0, 2,... , [2.sup.k-1] -2} and Y = {1, 3,... , [2.sup.k-1] - 1} (recall that an arc of distance [2.sup.l] - 1 in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] will become an arc of jump [2.sup.l-1] - 1 in the bipartite structure of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]). Clearly, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] consists of [2.sup.j-1] anti-directed cycles as gcd([2.sup.k-2], [2.sup.j-1] - 1 + [2.sup.k-2] - [2.sup.k-j-2] + 1 (mod [2.sup.k-2])) = [2.sup.j-1], see Remark 3.1.

We have [a.sub.j] = [2.sup.j] - 1 and b j = [2.sup.k-1-j] - 1; let [x.sub.j] = 2(j - 1). First we exhibit [2.sup.j-1] disjoint anti-directed cycles [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], to obtain the required number of anti-directed paths for [[??].sub.j.e].

In the following list of [2.sup.j-1] anti-directed cycles, the anti-directed cycle [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], 2 [less than or equal to] i [less than or equal to] [2.sup.j-1] is obtained from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by subtracting 2[b.sub.j] from each of its corresponding vertices and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is explicitly described; in the vertices of the following anti-directed cycles, the addition is taken modulo [2.sup.k-1] and [x.sub.j] = 2(j - 1). We list [2.sup.j-1] anti-directed cycles and then we prove that they are mutually disjoint.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the vertices 1, 3, 5,... , [2.sup.k-1] - 1 are called the odd vertices and 0, 2, 4,... , [2.sup.k-1] - 2 are called the even vertices. In [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the odd vertices and even vertices alternate and an odd vertex is obtained by adding aj to its preceding (even) vertex, along the anti-directed cycle, and an even vertex is obtained from its preceding (odd) vertex by adding (-bj) to it. We obtain the required [2.sup.j-1] anti-directed paths, denoted by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], 1 [less than or equal to] i [less than or equal to] [2.sup.j-1], from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], 1 [less than or equal to] i [less than or equal to] [2.sup.j-1], by deleting its last arc, namely, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The origins of the [2.sup.j-1] anti-directed paths [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], 1 [less than or equal to] i [less than or equal to] [2.sup.j-1], are the origins of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], namely, [x.sub.j], [x.sub.j] - 2[b.sub.j], [x.sub.j] - 4[b.sub.j],... , [x.sub.j] - ([2.sup.j] - 2)[b.sub.j]. The union of these [2.sup.j-1] anti-directed paths [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], is denoted by [[??].sub.j,e], that is, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Next we prove that the vertices of these anti-directed paths [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], form a partition of the vertex set of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (and hence that of [G.sub.k,e]).

Claim 1. The origins of the anti-directed paths [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], namely, ([x.sub.j] - 2[b.sub.j]), ([x.sub.j] - 4[b.sub.j]), ([x.sub.j] - 6[b.sub.j]),..., ([x.sub.j] - ([2.sup.j] - 2)[b.sub.j]) are all distinct from the even vertices of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

If [x.sub.j] - 2l[b.sub.j], the origin of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], is in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then, as [x.sub.j] - 2l[b.sub.j] is even, it should be of the form [x.sub.j] + r[a.sub.j] - r[b.sub.j], for some r [not equal to] 0 and r [less than or equal to] [2.sup.k-j-1] - 1; r [less than or equal to] [2.sup.k-j-1] - 1 follows from the fact that each anti-directed cycle is of length [2.sup.k-j] and among the vertices of the anti-directed cycle, only half of them can be even vertices and further the origin is an even vertex. Hence [x.sub.j] - 2l[b.sub.j] = [x.sub.j] + r[a.sub.j] - r[b.sub.j] (mod [2.sup.k-1]), that is,

r[b.sub.j]-r[a.sub.j]-2l[b.sub.j] [equivalent to] 0 (mod[2.sup.k-1]) r([b.sub.j] -[a.sub.j])- 2l[b.sub.j] = 0 (mod [2.sup.k-1]), a contradiction,

for, if the congruence holds then, as [2.sup.j] | [b.sub.j]-[a.sub.j] and [2.sup.j] | [2.sup.k-1], we must have [2.sup.j] | 2l[b.sub.j], but this is not the case as bj is odd and l [less than or equal to] [2.sup.j-1] - 1. This implies that the origins of the anti-directed paths [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are all distinct from the even vertices of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

This completes the proof of Claim 1.

Claim 2. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], l [not equal to] l' , areall disjoint.

It is enough to show that the set of even vertices of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and the even vertices of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are disjoint. Assume that u is an even vertex common to both [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some l' [not equal to] l. Without loss of generality assume that l' < l. As u is an even vertex in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], u = [x.sub.j] - 2l[b.sub.j] + r([a.sub.j] - [b.sub.j]) for some r [less than or equal to] [2.sup.k-j-1] - 1. As u is also in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the vertex [x.sub.j] - 2l[b.sub.j] must be in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], since the difference between two even vertices is a multiple of [a.sub.j] - [b.sub.j]; since [x.sub.j] - 2l'[b.sub.j] is the origin of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], both [x.sub.j] - 2l'[b.sub.j] and [x.sub.j] - 2l[b.sub.j] are in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and they cannot be equal as l [not equal to] l'. If we add 2l'[b.sub.j] to each vertex of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then the vertex [x.sub.j] - 2(l - l')[b.sub.j] is in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], a contradiction to Claim 1 as [x.sub.j] - 2(l - l')[b.sub.j] is the origin of the anti-directed path [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

This completes the proof of Claim 2.

Clearly, the arcs of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] which are not on the anti-directed paths [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], 1 [less than or equal to] i [less than or equal to] [2.sup.j-1], are the [2.sup.j-1] arcs [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] namely, the last arcs of the anti-directed cycles [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], 1 [less than or equal to] i [less than or equal to] [2.sup.j-1].

As [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], it can be verified that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. As [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] has [2.sup.j-1] disjoint anti-directed cycles, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] also has [2.sup.j-1] disjoint anti-directed cycles. Similar to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we obtain [2.sup.j-1] disjoint anti-directed cycles [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], 1 [less than or equal to] i [less than or equal to] [2.sup.j-1], in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Addition is taken modulo [2.sup.k-1] in the vertices of the following anti-directed cycles and in the following cycles also [x.sub.j] = 2(j - 1), [a.sub.j] = [2.sup.j]-1 and bj = [2.sup.k-j-1] - 1.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

The anti-directed cycle [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], is obtained from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by subtracting 2[b.sub.j] from each of its vertices corresponding vertices and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is explicitly described.

We obtain [2.sup.j-1] anti-directed paths, denoted by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by deleting its last arc, namely [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. We assume that the origin of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], is the origin of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; hence the origins are [x.sub.j], [x.sub.j] - 2[b.sub.j], [x.sub.j] - 4[b.sub.j],... , [x.sub.j] - ([2.sup.j] - 2)[b.sub.j].

Clearly the origin of the path [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is same as the origin of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], 1 [less than or equal to] i [less than or equal to] [2.sup.j-1]. Similarly the terminus of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the terminus of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for all i except for i = [2.sup.j-1]. But we want to reconstruct [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], suitably, as an anti-directed path such that the reconstructed path and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] have the same terminus.

Let [S.sub.j] and [T.sub.j] denote the sets of origins and termini of the anti-directed paths [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], 1 [less than or equal to] i [less than or equal to] [2.sup.j-1], respectively.

For the reconstruction of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we need to prove that the vertices [x.sub.j] + [a.sub.j] + [b.sub.j], [x.sub.j] + [b.sub.j], [x.sub.j] + 2[b.sub.j] and [x.sub.j] + [a.sub.j] + [b.sub.j] + 1 are on [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and the three vertices [x.sub.j] + [a.sub.j] + [b.sub.j], [x.sub.j] + [b.sub.j], [x.sub.j] + 2[b.sub.j] are consecutive vertices along [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. In [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the vertex ([x.sub.j] - [a.sub.j] - ([2.sup.j] - 2)[b.sub.j]) is the immediate next vertex of the origin ([x.sub.j] - ([2.sup.j] - 2)[b.sub.j]). Further, ([x.sub.j] - [a.sub.j] - ([2.sup.j] - 2)bj) = [x.sub.j] + 2[b.sub.j] + 1 (mod [2.sup.k-1]), since [a.sub.j]= [2.sup.j]-1, [b.sub.j]=[2.sup.k-j-1]-1,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Consequently, [x.sub.j] - [a.sub.j] - ([2.sup.j] - 2)[b.sub.j] = [x.sub.j] + 2[b.sub.j] + 1 (mod [2.sup.k-1]). Often we recall this congruence [x.sub.j] + 2[b.sub.j] + 1 = [x.sub.j] - [a.sub.j] - ([2.sup.j] - 2)[b.sub.j] (mod [2.sup.k-1]) in the future. In many places we write [x.sub.j] + 2[b.sub.j] + 1 instead of [x.sub.j] - [a.sub.j] - ([2.sup.j] -2)[b.sub.j].

It is enough to show that [x.sub.j] + [b.sub.j] is in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], since by adding [b.sub.j] (resp. [a.sub.j]) to an odd vertex we get its succeeding (resp. preceding) vertex, namely [x.sub.j] + 2[b.sub.j] (resp. [x.sub.j] + [a.sub.j] + [b.sub.j]), in the anti-directed cycle. Now we prove that [x.sub.j] + [b.sub.j] is in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Clearly, [b.sub.j] - [a.sub.j] = 0 (mod [2.sup.j]) as j [less than or equal to] [k/2] - 1; let [b.sub.j] - [a.sub.j] = m[2.sup.j], where m is odd.

Now [a.sub.j][b.sub.j] + [a.sub.j] + [b.sub.j] + 1 = ([a.sub.j] + 1)([b.sub.j] + 1) = ([2.sup.j])([2.sup.k-j-1]) = [2.sup.k-1][equivalent to] 0 (mod[2.sup.k-1])

Hence

[b.sub.j]+[2.sup.j] = [b.sub.j] + [a.sub.j] + 1 [equivalent to] -[a.sub.j][b.sub.j](mod [2.sup.k-1]) (2)

As [x.sub.j] is even, [x.sub.j] + [b.sub.j] and the last vertex [x.sub.j] - ([2.sup.j] - 1)[b.sub.j] = [x.sub.j] - [a.sub.j][b.sub.j] of the anti-directed cycle [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are odd. Hence the vertex [x.sub.j] + [b.sub.j] is in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] if and only if [x.sub.j] + [b.sub.j] + l([b.sub.j] -[a.sub.j]) [equivalent to] [x.sub.j] -[a.sub.j][b.sub.j] (mod [2.sup.k-1]), for some l < [2.sup.k-j-1], since the difference between two odd vertices along [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a multiple of [b.sub.j] - [a.sub.j] and there can be only [2.sup.k-j-1] odd vertices in an anti-directed cycles.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

As [b.sub.j] - [a.sub.j] = m[2.sup.j] and [b.sub.j] - [a.sub.j] are known, m is known. Thus (3) gives that [x.sub.j] + [b.sub.j] is in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] if and only if the congruence in (3) has a solution. As m is odd and gcd(m, [2.sup.k-j-1]) = 1, the congruence in (3) has a unique solution. Thus [x.sub.j] + [b.sub.j] must be in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

[FIGURE 6 OMITTED]

Clearly, the vertex next to [x.sub.j] + [b.sub.j] along [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is [x.sub.j] + 2[b.sub.j]; therefore, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] must be of the form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

Hence the reconstructed last anti-directed path [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is obtained from (4) by deleting the first arc [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and the arc [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and, adding the arc [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] recall that ([x.sub.j] - [a.sub.j] - ([2.sup.j] - 2)[b.sub.j]) [equivalent to] ([x.sub.j] + 2[b.sub.j] + 1) (mod [2.sup.k-1]); see Figure 6. In fact, the arc [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is never used in the previous anti-directed paths [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], 1 [less than or equal to] i [less than or equal to] [2.sup.j-1] - 1, as it is an arc of distance [2.sup.k-1] - 1 in [[??].sub.k], which is neither in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] nor in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], 1 [less than or equal to] j [less than or equal to] [k/2] - 1, see Figure 6, that is,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

In (5) note that the vertex ([x.sub.j] - [a.sub.j] - ([2.sup.j] - 2)[b.sub.j]) [equivalent to] ([x.sub.j] + 2[b.sub.j] + 1) (mod [2.sup.k-1]). For all our future reference [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] will refer to the reconstructed anti-directed path in (5).

This path contains the arc [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] which is an arc of distance [2.sup.k - 1] of [[??].sub.k]. Consequently, the arcs of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] which are not on the anti-directed paths [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], 1 [less than or equal to] i [less than or equal to] [2.sup.j-1] are the [2.sup.j-1] + 1 arcs [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], that is, these are the last arcs of the [2.sup.j-1] - 1 anti-directed cycles [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], 1 < i < [2.sup.j-1] - 1, and the two arcs deleted from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] to obtain the reconstructed [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Let the union of these [2.sup.j-1] anti-directed paths [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], 1 [less than or equal to] i [less than or equal to] [2.sup.j-1], be denoted by [[??].sub.j,o], that is, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Thus for each pair of distances ([a.sub.j] = [2.sup.j] - 1, [b.sub.j] = [2.sup.k-j-1] - 1) of [[??].sub.k] and [x.sub.j] = 2(j - 1), we have the pair of digraphs [[??].sub.j,e] and [[??].sub.j, o], 1 [less than or equal to] j [less than or equal to] [k/2] - 1.

Recall that [S.sub.j] and [T.sub.j] denote the origins and termini of the anti-directed paths [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], respectively, and also they are the origins and termini of the anti-directed paths of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Let [A.sub.j] = [S.sub.j] [union] [T.sub.j] and set t = [k/2] - 1.

Next we prove that [A.sub.j], 1 [less than or equal to] j [less than or equal to] [k/2] - 1 are mutually disjoint. We know that the origin and terminus of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], 1 [less than or equal to] i [less than or equal to] [2.sup.j-1], are [x.sub.j] - (i - 1)2[b.sub.j] and [x.sub.j] - (i - 1)2[b.sub.j] + [b.sub.j] (= [x.sub.j] - (2i - 3)[b.sub.j]), respectively, and they are independent of [a.sub.j].

By our choice [x.sub.j] = 2(j - 1), [x.sub.j-1] = 2(j - 1 - 1) = 2(j - 1) - 2 = [x.sub.j] - 2; thus, recursively we can write [x.sub.l] in terms of [x.sub.j] for all l < j. Further, as [a.sub.j] = [2.sup.j] - 1, [a.sub.j-1] = [2.sup.j-1] - 1 = [[[2.sup.j]- 2]/2] = [[[a.sub.j]- 1]/2] and [b.sub.j] = [2.sup.k-j-1] - 1 implies [b.sub.j-1] = [2.sup.k-j] - 1 = 2.[2.sup.k-j-1] - 1 = 2([2.sup.k-j-1] - 1) + 1 = 2[b.sub.j] + 1. Thus, recursively we can write both [a.sub.l] and [b.sub.l] in terms of [a.sub.j] and [b.sub.j], respectively, for all l < j. Hence all [x.sub.j] 's [b.sub.j] 's and [a.sub.j]'s can be written in terms of [x.sub.t], [b.sub.t] and [a.sub.t], respectively, where t = [k/2]-1.If j =t - r for some r > 0, then [x.sub.j] = [x.sub.t-r] = [x.sub.t-r+1] - 2. Again [x.sub.t-r+1] = [x.sub.t-r+2] - 2, thus [x.sub.j] = [x.sub.t-r] = [x.sub.t-r+1] - 2 = [x.sub.t-r+2] - 4. Proceeding like this, we get [x.sub.j] = [x.sub.t-r] = [x.sub.t] - 2r. Similarly for j = t - r, recursively applying the above relation, we get [b.sub.j] = [b.sub.t-r] = 2[b.sub.t-r+1] +1 = 2(2[b.sub.t-r+2] +1) + 1 = 4[b.sub.t-r+2] + 3 = 4(2[b.sub.t-r+3] +1) + 3 = 8[b.sub.t-r+3] + 7, etc. Proceeding like this, we get [b.sub.j] = [b.sub.t-r] = [2.sup.r][b.sub.t] + [2.sup.r] - 1. Also for j = t -r, recursively applying the above relation, we get [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] etc. Proceeding like this, we get [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

For our convenience, we shall denote the origin and terminus of an anti-directed path [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] by the ordered pair (r, s) where r is the origin and s is the terminus of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], respectively. For t = [k/2] - 1, by the above notation, the ordered pairs ([x.sub.t], [x.sub.t] + [b.sub.t]), ([x.sub.t]-2[b.sub.t], [x.sub.t]-[b.sub.t]), ([x.sub.t]-4[b.sub.t], [x.sub.t]-3[b.sub.t]), ([x.sub.t]-6[b.sub.t], [x.sub.t]- 5[b.sub.t]), ...([x.sub.t]- ([2.sup.t] - 4)[b.sub.t], [x.sub.t] - ([2.sup.t] - 5)[b.sub.t]), ([x.sub.t] - ([2.sup.t] - 2)[b.sub.t], [x.sub.t] - ([2.sup.t] - 3)[b.sub.t]) denote the origins and termini of the anti-directed paths [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], 1 [greater than or equal to] i [greater than or equal to] [2.sup.t-1], in [[??].sub.t,e]. Similarly, ([x.sub.t-1], [x.sub.t-1] + [b.sub.t-1]), ([x.sub.t-1] - 2[b.sub.t-1], [x.sub.t-1] - [b.sub.t-1]), ([x.sub.t-1] - 4[b.sub.t-1], [x.sub.t-1] - 3[b.sub.t-1]), ([x.sub.t-1] - 6[b.sub.t-1], [x.sub.t-1] - 5[b.sub.t-1]),... ([x.sub.t-1] - ([2.sup.t-1] -4) [b.sub.t-1], [x.sub.t-1] - ([2.sup.t-1] - 5)[b.sub.t-1]), ([x.sub.t-1] - ([2.sup.t-1] - 2)[b.sub.t-1], [x.sub.t-1] - ([2.sup.t-1] - 3)[b.sub.t-1]) denote the origins and termini of the anti-directed paths [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], 1 [less than or equal to] i [less than or equal to] [2.sup.t-2], in [[??].sub.t-1,e]. But we have seen above that [b.sub.t-1] = 2[b.sub.t] + 1 and [x.sub.t-1] = [x.sub.t - 2]. If we write [x.sub.t-1] and [b.sub.t-1] in terms of [x.sub.t] and [b.sub.t] to the origins and termini of the anti-directed paths of [[??].sub.t -1 e], the origins and termini of the anti-directed paths in [[??].sub.t -1 e] are ([x.sub.t] - 2, [x.sub.t] + 2[b.sub.t] - 1), ([x.sub.t] - 4[b.sub.t] - 4, [x.sub.t] - 2[b.sub.t] - 3), ([x.sub.t] - 8[b.sub.t] - 6, [x.sub.t] - 6[b.sub.t] - 5), ([x.sub.t] - 12[b.sub.t] -8, [x.sub.t] - 10[b.sub.t] - 7),... , ([x.sub.t] - ([2.sup.t] - 8)[b.sub.t] - [2.sup.t-1] + 2, [x.sub.t] - ([2.sup.t] - 10)[b.sub.t] - [2.sup.t-1] + 3), ([x.sub.t] - ([2.sup.t] - 4)[b.sub.t] -[2.sup.t-1], [x.sub.t] - ([2.sup.t] - 6)[b.sub.t] - [2.sup.t-1] + 1). Proceeding as above, the origin and terminal vertices of each of the anti-direted paths of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can be given in terms of xt and [b.sub.t].

In general, the origins and termini of anti-directed paths of [[??].sub.j,e] are ([x.sub.j], [x.sub.j] + [b.sub.j]), ([x.sub.j] - 2[b.sub.j], [x.sub.j] - [b.sub.j]), ([x.sub.j]-4[b.sub.j], [x.sub.j]-3[b.sub.j]),... , ([x.sub.j]-(i-1)2[b.sub.j], [x.sub.j]-(2i-3)[b.sub.j]),... , ([x.sub.j] -([2.sup.j] -2)[b.sub.j], [x.sub.j] -([2.sup.j] -3)[b.sub.j]). If j = t - r, then by the relation obtained above, [x.sub.j] = [x.sub.t] - 2r and [b.sub.j] = [2.sup.r][b.sub.t] + [2.sup.r] - 1. Thus the origins and termini of anti-directed paths of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in terms of [x.sub.t] and [b.sub.t] are given by the ordered pairs ([x.sub.t] - 2r, [x.sub.t]-2r + [2.sup.r][b.sub.t] + [2.sup.r] - 1), ([x.sub.t] - 2r - 2([2.sup.r][b.sub.t] + [2.sup.r] - 1), [x.sub.t] - 2r - ([2.sup.r][b.sub.t] + [2.sup.r] - 1)), ([x.sub.t] -2r - 4 ([2.sup.r][b.sub.t] + [2.sup.r]- 1), [x.sub.t]-2r- 3([2.sup.r][b.sub.t] + [2.sup.r] - 1)),... , ([x.sub.t] - 2r - (i - 1)2([2.sup.r][b.sub.t] + [2.sup.r] - 1), [x.sub.t]-2r-(2i - 3) ([2.sup.r][b.sub.t] + [2.sup.r] - 1)),... ,([x.sub.t]-2r- ([2.sup.j] - 2)([2.sup.r][b.sub.t] + [2.sup.r] - 1), [x.sub.t] - 2r - ([2.sup.j] - 3)([2.sup.r][b.sub.t] + [2.sup.r] - 1)). Hereafter we shall represent the elements of Aj in terms of xt and [b.sub.t].

We list the elements of Aj, 1 [less than or equal to] j [less than or equal to] [k/2] - 1, in terms of [x.sub.t] and [b.sub.t], in ordered pairs in the Table 1 below with the elements of [A.sub.t] appearing in the first column, the elements of [A.sub.t-1] in the second column etc., and the last column contains the elements of [A.sub.1].

Next we shall prove that [A.sub.i] [intersection] Aj = [??], i [not equal to] j; the intersection here is the intersection of elements of [A.sub.i] and Aj (but not as intersection of ordered pairs of [A.sub.i] and Aj described in the Table 1). For this it is enough to prove that the even vertices in the Table 1 are distinct. For, let i < j with i = t - s and j =t - r; hence r < s. By the above recursive relations we get [x.sub.j] = [x.sub.t] - 2r, [x.sub.i] = [x.sub.t] - 2s, [b.sub.j] = [2.sup.r][b.sub.t] + [2.sup.r] - 1 and bi = [2.sup.s][b.sub.t] + [2.sup.s] - 1. Suppose the origins in the (l + 1)th pair of [A.sub.j] in Table 1, that is, [x.sub.j] - 2l[b.sub.j] and the (l' + 1)th pair of Ai, that is, xi - 2l'bi are same then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

However, we shall show that this congruence does not hold. We assume that the congurence holds and we obtain a contradicition. Observe that as0 [less than or equal to] r [less than or equal to] s [less than or equal to] [k/2]-1 and t = [k/2] -1, we have r + k - t < [k/2] - 2 + k - [k/2] + 1 = k - 1.

First we suppose that A is odd. Since A is odd, as [2.sup.r+k-t] divides both A[2.sup.r+k-t] and [2.sup.k-1], then it must divide 2[r - s + l' - l], that is, 2[r - s + l' - l] = 0 (mod [2.sup.r+k-t]), which is a contradiction, as 0 [less than or equal to] r [less than or equal to] s [less than or equal to] [k/2] - 1, 0 [less than or equal to] l [less than or equal to] [2.sup.t-r-1] - 1 and0 [less than or equal to] l' < [2.sup.t-s-1] - 1.

Next we suppose that A is even. Let d be the maximum integer such that [2.sup.d] | A[2.sup.r+k-t]. Now we consider the case d [less than or equal to] k - 1; then the proof follows similar to the case when A is odd by replacing r + k - t by d. Next we assume that d > k - 1. Since d > k - 1, [2.sup.k-1] | [2.sup.d]. Then [2.sup.k-1] divides 2[r - s + l' - l], that is, 2[r-s+l'-l] = 0 (mod [2.sup.k-1]), which is a contradiction, as 0 [less than or equal to] r < s [less than or equal to] [k/2] -1, 0 [less than or equal to] l [less than or equal to] [2.sup.t-r-1]-1 and 0 [less than or equal to] l' [less than or equal to] [2.sup.t-s-1]-1.

Hence irrespective of the parity of A, the congruence does not hold. Thus the origins, that is, the even vertices of the ordered pairs listed in the columns [A.sub.i] and [A.sub.j], i [not equal to] j, of Table 1, are distinct and hence the odd vertices of the ordered pairs listed in the columns [A.sub.i] and [A.sub.j], i [not equal to] j, of Table 1 are also distinct. This completes the proof of the lemma. []

Lemma 3.3 There exist [k/2] - 1 arc disjoint 2-diregular bieulerian digraphs [[??].sub.j], 1 [less than or equal to] j [less than or equal to] [k/2] - 1, each of which is a spanning subdigraph of [[??]'.sub.k].

[FIGURE 7 OMITTED]

Proof: By Lemma 3.2, there exist [k/2] - 1 arc disjoint spanning subdigraphs [[??].sub.j,e] and [[??].sub.j,o], 1 [less than or equal to] j [less than or equal to] [k/2] - 1, of [[??].sub.k, e] and [[??].sub.k, o], respectively. Clearly, each of the digraphs [[??].sub.j,e] and [[??].sub.j, o] consists of union of [2.sup.j-1] anti-directed paths with their origins and termini at [A.sub.j] = [S.sub.j] [union] [T.sub.j].

Next we construct [k/2] - 1 spanning 2-diregular bieulerian digraphs using [[??].sub.j,e] and [[??].sub.j,o], 1 [less than or equal to] j [less than or equal to] [k/2]- 1. For a fixed j, we construct a spanning 2-diregular bieulerian digraph from [[??].sub.j, e] and [[??].sub.j, o] by concatenating the anti-directed paths of them appropriately and adding some appropriate loops to it. That is, the spanning bieulerian digraph is [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] {directed loops at each of the vertices of [A.sub.j] }, see Figure 7. We denote the graph [[??].sub.j,e] [union] [[??].sub.j,o] together with directed loops added at the vertices of [A.sub.j] by [[??].sub.j], see Figure 7. Clearly, [[??].sub.j] is eulerian and, [[??].sub.j] is aneulerian follows by moving along the anti-directed paths of [[??].sub.j,e] and [[??].sub.j,o], alternately, and the directed loops at the vertices of [A.sub.j]; while obtaining an aneulerian tour, as and when a directed loop of [A.sub.j] is encountered when we visit through [[??].sub.j,e] or [[??].sub.j,o], the directed loop is visited in the clockwise or anticlockwise direction according to the requirement for the existence of an aneulerian tour.

This completes the proof of the lemma. []

Next we prove that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], k [greater than or equal to] 6, has [k/2] - 1 edge disjoint Hamilton cycles.

Theorem 3.2 [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] contains [k/2] - 1 edge disjoint Hamilton cycles.

Proof: By Lemma 3.3, [[??]'.sub.k] has [k/2] - 1 arc disjoint 2-diregular spanning bieulerian subdigraphs [[??].sub.j,1] [less than or equal to] j [less than or equal to] [k/2] - 1. Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Now [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. But the underlying graph of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], is a Hamilton cycle, by Theorem 2.2. Thus the underlying graph of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is Hamilton cycle decomposable. As H is a spanning subdigraph of [G'.sub.k] and the underlying graph of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is isomorphic to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] contains [k/2] - 1 edge disjoint Hamilton cycles. []

To prove the existence of a Hamilton cycle decomposition of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], it is enough to prove that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], when k is even or, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], where F stands for the set of arcs of distance [[k+1]/2] of [[??]'.sub.k], when k is odd, is a bieulerian digraph. If [[??]'.sub.k] is bieulerian, then by Theorem 2.2, the underlying graph of [[??]'.sub.k] x [K.sub.2] is Hamiltonian. The following remark explains the difficulty in proving that [[??]'.sub.k] is bieulerian.

Remark 3.2 In fact, we know a method by which we can prove that [[??]'.sub.k] is bieulerian. But proving [[??]'.sub.k] is bieulerian is complicated and too long and hence we have omitted the proof. A sketch of the proof of [[??]'.sub.k] is bieulerian using a "reduction technique "is described in the Appendix I of the Ph.D. thesis of the second author, see [24]. Also, using the technique described therein, we have proved that [G".sub.8] is bieulerian, see Appendix II of [24]. This proves that [W.sub.8,28] is Hamilton cycle decomposable. Using the method described in the Appendix I mentioned above, and Lemma 3.3, of this paper, here we obtain three arc disjoint spanning bieulerian subdigraphs of [G'.sub.6], see Figures 8, 9 and 10. Thus [W.sub.6, 26] = [W.sub.6,64] is Hamilton cycle decomposable, by Theorem 2.2. We have not given the arc disjoint bieulerian subdigraphs of [G'.sub.k] for some smaller values of k [greater than or equal to] 7 as they have too many vertices and edges to draw. []

We present three edge disjoint Hamilton cycles of [W.sub.6,26], where we assume that (X, Y) is the bipartition with X = {(1, j) | 0 [less than or equal to] j [less than or equal to] 31} and Y = {(2, j) | 0 [less than or equal to] j [less than or equal to] 31}. The three Hamilton cycles [H.sub.1], [H.sub.2] and [H.sub.3] of [W.sub.6,64] given below are obtained using the arc disjoint bieulerian subdigraphs (shown in Figures 8 to 10) of [G'.sub.6].

[H.sub.1] = (1, 0)(2, 7)(1, 4)(2, 11)(1, 8)(2, 15)(1, 12)(2, 19)(1, 16)(2, 23)(1, 20)(2, 20)(1, 13)(2, 16) (1, 17)(2, 24)(1, 21)(2, 28)(1, 25)(2, 0)(1, 29)(2, 4)(1, 1)(2, 8)(1, 5)(2, 12)(1, 9)(2, 9)(1, 6) (2, 13)(1, 10)(2, 17)(1, 14)(2, 21)(1, 18)(2, 25)(1, 22)(2, 29)(1, 26)(2, 1)(1, 30)(2, 5)(1, 2) (2, 2)(1, 31)(2, 6)(1, 3)(2, 10)(1, 7)(2, 14)(1, 11)(2, 18)(1, 15)(2, 22)(1, 19)(2, 26)(1, 23) (2, 30)(1, 27)(2, 27)(1, 24)(2, 31)(1, 28)(2, 3)(1, 0).

[H.sub.2] = (1, 0)(2, 1)(1, 18)(2, 19)(1, 4)(2, 5)(1, 22)(2, 23)(1, 8)(2, 9)(1, 26)(2, 27)(1, 12)(2, 13) (1, 30)(2, 31)(1, 16)(2, 17)(1, 2)(2, 3)(1, 20)(2, 21)(1, 6)(2, 7)(1, 24)(2, 25)(1, 10)(2, 11) (1, 28)(2, 29)(1, 14)(2, 15)(1, 15)(2, 16)(1, 1)(2, 2)(1, 19)(2, 20)(1, 5)(2, 6)(1, 23)(2, 24) (1, 9)(2, 10)(1, 27)(2, 28)(1, 13)(2, 14)(1, 31)(2, 30)(1, 29)(2, 12)(1,11)(2, 26)(1, 25) (2, 8)(1, 7)(2, 22)(1, 21)(2, 4)(1, 3)(2, 18)(1, 17)(2, 0)(1, 0).

[H.sub.3] = (1, 0)(2, 31)(1, 31)(2, 0)(1, 1)(2, 1)(1, 2)(2, 9)(1, 10)(2, 10)(1, 11)(2, 11)(1, 12)(2, 12)(1, 13) (2, 13)(1, 14)(2, 14)(1, 15)(2, 30)(1, 30)(2, 29)(1, 29)(2, 28)(1, 28)(2, 27)(1, 20)(2, 19)(1, 19) (2, 18)(1, 18)(2, 17)(1, 17)(2, 20)(1, 21)(2, 21)(1, 22)(2, 22)(1, 23)(2, 23)(1, 24)(2, 24)(1, 25) (2, 25)(1, 26)(2, 26)(1, 27)(2, 2)(1, 3)(2, 3)(1, 4)(2, 4)(1, 5)(2, 5)(1, 6)(2, 6)(1, 7)(2, 7)(1, 8) (2, 8)(1, 9)(2, 16)(1, 16)(2, 15)(1, 0).

[FIGURE 8 OMITTED]

Acknowledgements

The second author would like to thank the Department of Science and Technology, Government of India, New Delhi and Annamalai University for awarding Junior Research Fellowship under the PURSE Programme. The second author also thank the Management and Principal, SSN College of Engineering, Chennai.

References

[1] R. Ahlswede, L. Gargano, H.S. Haroutunian and L.H. Khachatrian, Fault-Tolerant Minimum Broadcast Networks, Networks 27 (1996) 293-307.

[2] R. Balakrishnan and K. Ranganathan, A Textbook of Graph Theory, Second Edition, Springer, New York, 2012.

[FIGURE 9 OMITTED]

[3] R. Balakrishnan and P. Paulr[a.sub.j]a, Hamilton cycles in tensor product of graphs, Discrete Math. 186 (1998) 1-13.

[4] R. Balakrishnan, P. Paulr[a.sub.j]a, W. So and Vinay, The automorphism group of the Knodel graph [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (submitted).

[5] J.-C. Bermond, H. A. Harutyunyan, A. L. Liestman and S. Perennes, A Note on the Dimensionality of Modified Knodel Graphs, Int. J. Found. Comput. Sci. 8 (1997) 109-116.

[6] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, The MacMillan Press Ltd., London, 1976.

[FIGURE 10 OMITTED]

[7] P. Fraigniaud and J.G. Peters, Minimum linear gossip graphs and maximal linear ([DELTA], k)-gossip graphs, Networks 38 (2001) 150-162.

[8] G. Fertin and A. Raspaud, A survey on Knodel graphs, Discrete Appl. Math. 137 (2004) 173-195.

[9] G. Fertin, A. Raspaud, H. Schroder, O. Sykora, and I. Vrt'o, Diameter of the Knodel graph. In U. Brandes and D. Wagner, editors, Proc. 26th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2000), Vol. 1928 of LNCS, pp. 149-160. Springer, Berlin, 2000.

[10] G. Fertin and A. Raspaud, Families of graphs having broadcasting and gossiping properties, in: Proceedings of the 24th International Workshop on Graph-Theoretic Concepts in Computer Science (WG' 98), Vol. 1517, Smolenice, LNCS, 1998, pp. 63-77.

[11] G. Gauyacq, Routages uniformes dans les graphes sommet-transitifs, 1995.

[12] H. Grigoryan and H. A. Harutyunyan, Tight Bound on the Diameter of the Knodel Graph, IWOCA 2013,206-215.

[13] H. Grigoryan and H. A. Harutyunyan, The shortest path problem in the Knodel graph, J. Discrete Algorithms 31 (2015) 40-47.

[14] H.A. Harutyunyan, Minimum multiple message Broadcast graphs, Networks 47 (2006) 218-224.

[15] H. A. Harutyunyan, Multiple message broadcasting in modified Knodel graph, SIROCCO 2000, 157-165.

[16] H. A. Harutyunyan and C. D. Morosan, The spectra of Knodel graphs, Informatica 30 (2006) 295-299.

[17] H. A. Harutyunyan and C. D. Morosan, On the minimum path problem in Knodel graphs, Networks 50 (2007) 86-91.

[18] H.A. Harutyunyan and A.L. Liestman, Upper bounds on the broadcast function using minimum dominating sets, Discrete Math. 312 (2012) 2992-2996.

[19] S.M. Hedetniemi, S.T. Hedetniemi and A.L. Liestman, A survey of gossiping and broadcasting in communication networks. 18 (1988) 319-349.

[20] J. Hromkovic, R. Klasing, B. Monien and R. Peine, Dissemination of information in interconnection networks (broadcasting and gossiping). In, D.-Z. Du and D.F. Hsu, Editors, Combinatorial Network Theory, pp. 125-212, Kluwer Academic Publishers, 1996.

[21] L.H. Khachatrian and H.S. Haroutunian, Construction of new classes of minimal broadcast networks, Proceedings of the Third International Colloquium on Coding Theory, 1990, pp. 69-77.

[22] W Knodel, New gossips and telephones, Discrete Math. 13 (1975) 95.

[23] R. Labahn, Some minimum gossip graphs, Networks 23 (1993) 333-341.

[24] S. Sampath Kumar, Decompositions of Graphs into Trails and Cycles, Ph.D. thesis, Annamalai University, India, 2013.

P. Paulraja (1*) S. Sampath Kumar (2[dagger])

(1) Department of Mathematics, Kalasalingam University, Krishnankoil, India

(2) Department of Mathematics, SSN College of Engineering, Kalavakkam, India

received 31st July 2014, revised 3rdAug. 2015, 24th June 2016, accepted 7th July 2016.

(*) ppr[a.sub.j][a.sub.5]6@gmail.com

([dagger]) sampathkumars@ssn.edu.in
COPYRIGHT 2016 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2016 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Paulraja, P.; Kumar, S. Sampath
Publication:DMTCS Proceedings
Article Type:Report
Date:Jan 1, 2016
Words:11278
Previous Article:Traceability of locally hamiltonian and locally traceable graphs.
Next Article:Energy-optimal algorithms for computing aggregative functions in random networks.
Topics:

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