<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 5 Issue 1" %>
Short Dominating Paths and Cycles in the Binary Hypercube
Uri Blass1, Iiro Honkala2, Mark G. Karpovsky3, and Simon Litsyn4
1Department of Electrical Engineering-Systems Tel-Aviv University, Ramat-Aviv 69978, Israel
blass_n@netvision.net.il
2Department of Mathematics, University of Turku, 20014 Turku, Finland
honkala@utu.fi
3College of Engineering, Boston University, Boston, MA 02215, USA
markkar@bu.edu
4Department of Electrical Engineering-Systems, Tel-Aviv University, Ramat-Aviv 69978, Israel
litsyn@eng.tau.ac.il
Annals of Combinatorics 5(1) p.51-59 March, 2001
AMS Subject Classification: 05C69 (94B75, 94B65, 68R10, 05C70, 05C38)
Abstract:
A sequence of binary words of length n is called a cube dominating path, if the Hamming distance between two consecutive words is always one, and every binary word of length n is within Hamming distance one from at least one of these words. If also the first and last words are Hamming distance one apart, the sequence is called a cube dominating cycle. Bounds on the cardinality of such sequences are given, and it is shown that asymptotically the shortest cube dominating path and cycle consist of 2n(1+o(1))/n words.
Keywords: domination, path, cycle, binary hypercube, Hamming distance

References:

1.  P. Ash and B. Jackson, Dominating cycles in bipartite graphs, In: Progress in Graph Theory, J.A. Bondy, Ed., Academic Press, Waterloo, Ontario, 1982, pp. 81每87.

2.  K. Chakrabarty, M.G. Karpovsky, and L.B. Levitin, Fault isolation and diagnosis in multiprocessor systems with point-to-point connections, In: Fault Tolerant Parallel and Distributed Systems, Kluwer, Boston, 1998, pp. 285每301.

3.  B.N. Clark, C.J. Colbourn, and P. Erdös, A conjecture on dominating cycles, Congr. Numer. 47 (1985) 189每197.

4.  G. Cohen, I. Honkala, S. Litsyn, and A. Lobstein, Covering Codes, Elsevier, Amsterdam, 1997.

5.  G. Cohen, S. Litsyn, and G. Zémor, On the traveling salesman problem in binary Hamming spaces, IEEE Trans. Info. Theory 42 (1996) 1274每1276.

6.  C.J. Colbourn and L.K. Stewart, Dominating cycles in series-parallel graphs, Ars Combin. 19 A (1985) 107每112.

7.  K. Deimer, Some new bounds for the maximum length of circuit codes, IEEE Trans. Inform. Theory 30 (1984) 754每756.

8.  P. Fraisse, Dominating cycles and paths, Notices Amer. Math. Soc. 5 (1984) 231.

9.  J.P. Hayes, T.N. Mudge, Q.F. Stout, S. Colley, and J. Palmer, Architecture of a hypercube supercomputer, In: Proc. Int. Conf. Parallel Processing, 1986, pp. 653每660.

10.  S.M. Hedetniemi, S.T. Hedetniemi, and R.C. Laskar, Domination in trees: models and algorithms, In: Graph Theory with Applications to Algorithms and Computer Science, Y. Alavi et al., Eds., Wiley, New York, 1985, pp. 423每442.

11.  G.A. Kabatyanskii and V.I. Panchenko, Unit sphere packings and coverings of the Hamming space, Problemy Peredachi Informatsii 24 (1988) 3每16.

12.  L.B. Levitin and M.G. Karpovsky, Traveling salesman problem in the space of binary vectors, In: Proceedings of 1994 IEEE Symposium on Information Theory, 1994, pp. 316.

13.  K.G. Paterson and J. Tuliani, Some new circuit codes, IEEE Trans. Inform. Theory 44 (1998) 1305每1309.

14.  A. Proskurowski, Minimum dominating cycles in 2-trees, Internat. J. Comput. Inform. Sci. 8 (1979) 405-417.

15.  C.L. Seitz, The cosmic cube, Commun. ACM 28 (1) (1985) 22每33.

16.  Y. Shih and J. Fier, Hypercube systems and key applications, In: Parallel Processing for Supercomputing and Artificial Intelligence, McGraw-Hill, New York, 1989, pp. 203每244.

17.  J. Simonis, On generator matrices of codes, IEEE Trans. Inform. Theory 38 (1992) 516.

18.  H.J. Veldman, Existence of dominating cycles and paths, Discrete Math. 43 (1983) 281每296.

19.  A.J. van Zanten, Minimal-change order and separability in linear codes, IEEE Trans. Inform. Theory 39 (1993) 1988每1989.