Shin, “Processor Allocation in an N-cube Multiprocessor using Gray Codes,” IEEE Transactions on Computer, Vol C-36, No. Murthy, “Graph Theory with Applications,” MacMillan Press Ltd., 1976. Sherwani, “On Optimal Embeddings into Incomplete Hypercubes,” to appear in the Proceedings of the Fifth International Parallel Processing Symposium, 1991. Williams, “Load Balancing and List Ranking on Compact Hypercubes,” manuscript, 1990.Ī. Lesniak-Foster, “Graphs and Digraphs,”, Prindle, Weber and Schmidt, Boston, 1979.Ī.
Lewis, “Efficient Serial and Parallel Subcube recognition in Hypercube,” To appear in the Proccedings of the First Great Lakes Computer Science Conference, 1989. This process is experimental and the keywords may be updated as the learning algorithm improves. These keywords were added by machine and not by the authors. We also present results on efficient representation and counting of compact hypercubes within a complete hypercube. We show that compact hypercubes exhibit many properties which are common with complete hypercubes. In this paper, we restrict our investigation to the graph properties and recognition algorithms for compact hypercubes. Development of algorithms on compact hypercubes further allow us to efficiently execute several algorithms concurrently on a complete hypercube. This concept allows the algorithms to work efficiently even if hypercubes are incomplete.
We show how to construct a hypercube like structure for any number n that can be easily upgraded to a complete hypercube. In order to alleviate this draw back, we define the concept of an n-node Compact Hypercube CH( n) which deals with the problem of computation with incomplete hypercubes. Of Integer Sequences." Referenced on Wolfram|Alpha Hypercube Graph Cite this as:įrom MathWorld-A Wolfram Web Resource.The binary hypercube, although a versatile multiprocessor network, has a draw back: its size must be a power of two. Skiena,ĭiscrete Mathematics: Combinatorics and Graph Theory with Mathematica. "On the Size of Optimal Binary Codes of Length 9 and Covering "Decomposition of Complete Graphs Into Isomorphic Cubes." J. "A Survey of the Theory of Hypercube Graphs."Ĭomput.
"On the Unit DistanceĮmbeddability of Connected Cubic Symmetric Graphs." Kolloquium über Kombinatorik. Gardner,ĭoughnuts and Other Mathematical Entertainments. "Dynamic Survey of Graph Labeling." Elec. "The Crossing Number of the -Cube." Not.Īmer. With Known or Bounded Crossing Numbers.". Cambridge, England: Cambridge University Press, p. 161,ġ993. Table of Binary/ternary Mixed Covering Codes." J. Of the NATO Advanced Research Workshop on Cycles and Rays: Basic Structures in FiniteĪnd Infinite Graphs held in Montreal, Quebec, May 3-9, 1987 (Ed. "Three Hamilton Decomposition Problems." University of Western Australia. Eggleton and Guy (1970) claimed to haveĭiscovered an upper bound for the graph crossing (2017) showed that dominationĪnd total domination numbers of the hypercube 2017) and as of April 2018, values are known onlyīertolo et al. Vertices in the original one, and repeating until the -hypercube graphĭetermining the domination number is intrinsicallyĭifficult (Azarija et al. Not used before), connecting the vertices in the translate with the corresponding The embedding by one unit in a direction not chosen in any of the steps before (onlyįinitely many unit translation vectors have been used, so there must be a direction Unit-distance embedding of the square graph, translating The -hypercube graph by starting with the Unit-distance (Gerbracht 2008), as illustratedĪbove for the first few hypercube graphs. In 1954, Ringel showed that the hypercube graphs admit Hamilton Hypercube graphs are distance-transitive, Special cases are summarized in the following table. Hypercube graphs may be computed in the Wolfram Language using the command HypercubeGraph,Īnd precomputed properties of hypercube graphs are implemented in the Wolfram To the upper vertex, while the other three connect to the lower vertex. In addition, three of the central edges connect Noteĭiagonal so that the top and bottom vertices coincide, and hence only seven of Using the first two of each vertex's set of coordinates. The above figures show orthographic projections of some small -hypercube graphs The -hypercube graph is also isomorphic to The graph of the -hypercube is given by the graph The -hypercube graph, also called the -cube graph and commonly denoted or, is the graphĪnd two vertices are adjacent iff the symbols differ in exactly