Independent domination in hypercubes. (English) Zbl 0780.05031

Summary: The use of hypercube graphs as the underlying architecture in many commercial parallel computers has stimulated interest in this family of graphs. We hope to further stimulate this interest by introducing a tantalizing unsolved problem that is based on dominating sets for this very regularly structured family.


05C35 Extremal problems in graph theory
94C15 Applications of graph theory to circuits and networks
Full Text: DOI


[1] Harary, F., Graph theory, (1969), Addison-Wesley Reading · Zbl 0797.05064
[2] Harary, F.; Alavi, Y.; Chartrand, G.; Oellermann, O.R.; Schwent, A.J., Recent results and unsolved problems on hypercube theory, Graph theory, combinatorics, and applications, Vol. 2, 621-632, (1991) · Zbl 0840.05092
[3] Stanton, R.G.; Kalbfleisch, J.G., Covering problems for dichotomized matchings, Aequationes math., 1, 94-103, (1968) · Zbl 0159.03004
[4] Stanton, R.G.; Kalbfleisch, J.G., Intersection inequalities for the covering problem, SIAM J. appl. math., 17, 1311-1316, (1969) · Zbl 0188.04101
[5] Berlekamp, E.R., Algebraic coding theory, (1984), Aegean Park Press Laguna Hills, (revised) · Zbl 0199.54101
[6] Thompson, T.M., From error-correcting codes through sphere packings to simple groups, (1983), Math. Assoc. Amer Washington · Zbl 0545.94016
[7] van Wee, G.J.M., Improved sphere bounds on the covering radius of codes, IEEE trans. inform. theory, 34, 237-245, (1988) · Zbl 0653.94014
[8] C. Barefoot, F. Harary and K.F. Jones, What is the difference between the domination number and the independent domination number of a cubic graph?, Graphs and Combinatorics (to appear). · Zbl 0728.05033
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.