Embedding hypercubes into cylinders, snakes and caterpillars for minimizing wirelength

We consider the problem of embedding hypercubes into cylinders to minimize the wirelength. Further, we show that the edge isoperimetric problem solves the wirelength problem of regular graphs and, in particular, hypercubes into triangular snakes and caterpillars.     

Exact solution of the 2-dimensional grid arrangement problem

Given an undirected graph $G=(V,E)$, we consider injective mappings of its vertices to the $k$-dimensional Cartesian integer grid. Among such embeddings we are interested in those that minimize the sum of the resulting edge lengths, where the length of an edge is defined by the $L_1$-metric. The case $k=1$ is the well-known Minimum Linear Arrangement Problem. We prove that the general problem is NP-hard for any fixed grid dimension. Our computational study focuses on the case $k=2$. We present as a first exact optimization algorithm a branch-and-cut scheme for sparse graphs. Several classes of valid inequalities are introduced and analyzed for facet defining properties of two corresponding polyhedra. Finally, computational results from a successful real-world application of the problem at the German Cancer Research Center (DKFZ) are presented.     

Minimal cones on hypercubes

It is shown that in dimension greater than four, the minimal area hypersurface separating the faces of a hypercube is the cone over the edges of the hypercube. This constrasts with the cases of two and three dimensions, where the cone is not minimal. For example, a soap film on a cubical frame has a small rounded square in the center. In dimensions over 6, the cone is minimal even if the area separating opposite faces is given zero weight. The proof uses the maximal flow problem that is dual to the minimal surface problem.     

On a heterochromatic number for hypercubes

The neighbourhood heterochromatic numbernh_c(G) of a non-empty graph G is the smallest integer l such that for every colouring of G with exactly l colours, G contains a vertex all of whose neighbours have different colours. We prove that lim_n→∞(nh_c(Gⁿ)-1)/|V(Gⁿ)|=1 for any connected graph G with at least two vertices. We also give upper and lower bounds for the neighbourhood heterochromatic number of the 2ⁿ-dimensional hypercube.     

Recursive mesh refinement on hypercubes

Adaptive methods for PDEs can be viewed as a graph problem. An efficient parallel implementation of adaptive PDE methods then requires distributing the nodes of the associated graph uniformly across the processors so that the resulting cost of communication between processors is low.We solve this problem in two phases: labeling of graph nodes and subsequent mapping of these labels onto processors. We describe a new form of Gray-code which we call aninterleaved Gray-code that allows easy labeling of graph nodes when the maximal level of refinement is unknown, allows easy determination of nearby nodes in the graph, is completely deterministic, and often (in a well-defined sense) distributes the graph uniformly across a hypercube. The theoretical results are supported by computational experiments on the Connection Machine.The work presented in this paper was supported by the Office of Naval Research under contract N00014-85-K-0461, by the Army Research Office under contract DAAL03-86-K-0158, by the Office of Naval Research under contract number N00014-86-K-0310 and the National Science Foundation under contract number DCR 8521451. Part of this work was performed while the second author was in residence at the Computer Science and Systems Division of Harwell Laboratory, United Kingdom.     

Retracts of hypercubes

An induced subgraph G of a graph H is a retract of H if there is an edge-preserving map f from H onto G such that f|_G is the identity map on G. A median graph is a connected graph such that for any three vertices u,v and w, there exists a unique vertex x which lies simultaneously on some shortest (u,v)-, (v,w)-, and (w,u)-paths. It is shown that a graph G is a retract of some hypercube if and only if G is a median graph.     

Distance-preserving subgraphs of hypercubes

We give a characterization of connected subgraphs G of hypercubes H such that the distance in G between any two vertices a, b?G is the same as their distance in H. The hypercubes are graphs which generalize the ordinary cube graph.     

Symmetric edge-decompositions of hypercubes

We call a set of edgesE of the n-cubeQ _n a fundamental set for Q _n if for some subgroupG of the automorphism group ofQ _n , theG-translates ofE partition the edge set ofQ _n .Q _n possesses an abundance of fundamental sets. For example, a corollary of one of our main results is that if |E| =n and the subgraph induced byE is connected, then if no three edges ofE are mutually parallel,E is a fundamental set forQ _n . The subgroupG is constructed explicitly. A connected graph onn edges can be embedded intoQ _n so that the image of its edges forms such a fundamental set if and only if each of its edges belongs to at most one cycle.We also establish a necessary condition forE to be a fundamental set. This involves a number-theoretic condition on the integersa _j (E), where for 1 j n, a _j (E) is the number of edges ofE in thej ^th direction (i.e. parallel to thej ^th coordinate axis).     

The carvingwidth of hypercubes

The notion of the carvingwidth of a graph was introduced by Seymour and Thomas [Call routing and the ratcatcher, Combinatorica 14 (1994) 217-241]. In this note, we show that the carvingwidth of a d-dimensional hypercube equals 2^d-1.     

A note on orthogonal sets of hypercubes

Mutually orthogonal sets of hypercubes are higher dimensional generalizations of mutually orthogonal sets of Latin squares. For Latin squares, it is well known that the Cayley table of a group of order n is a Latin square, which has no orthogonal mate if n is congruent to 2 modulo 4. We will prove an analogous result for hypercubes. © 1997 John Wiley & Sons, Inc. J Combin Designs 5: 231–233, 1997     

Hexagon-free subgraphs of hypercubes

It is shown (for all n ≥ 3) that the edges of the n-cube can be 3-colored in such a way that there is no monochromatic 4-cycle or 6-cycle. © 1993 John Wiley & Sons, Inc.     

Induced subgraphs of hypercubes

Let _Qk$Q_k$ denote the k$k$-dimensional hypercube on 2^k$2^k$ vertices. A vertex in a subgraph of _Qk$Q_k$ is full   if its degree is k$k$. We apply the Kruskal–Katona Theorem to compute the maximum number of full vertices an induced subgraph on n≤2^k$n\le 2^k$ vertices of _Qk$Q_k$ can have, as a function of k$k$ and n$n$. This is then used to determine min(max(|V(_H1)|,|V(_H2)|))$min(max(\left|V\left(H_1\right)\right|,\left|V\left(H_2\right)\right|))$ where (i) _H1$H_1$ and _H2$H_2$ are induced subgraphs of _Qk$Q_k$, and (ii) together they cover all the edges of _Qk$Q_k$, that is E(_H1)∪E(_H2)=E(_Qk)$E\left(H_1\right)\cup E\left(H_2\right)=E\left(Q_k\right)$.     

Distance monotone graphs and a new characterization of hypercubes

The aim of this paper is to study the class of s.c. distance monotone graphs which arise naturally when investigating some intersection properties of graphs. A new characterization of hypercubes is also obtained.     

Improved book-embeddings of incomplete hypercubes

In this paper, we show that any incomplete hypercube with, at most, 2ⁿ+2ⁿ⁻¹+2ⁿ⁻² vertices can be embedded in n−1 pages for all n≥4. For the case n≥4, this result improves Fang and Lai’s result that any incomplete hypercube with, at most, 2ⁿ+2ⁿ⁻¹ vertices can be embedded in n−1 pages for all n≥2.Besides this, we show that the result can be further improved when n is large — e.g., any incomplete hypercube with at most 2ⁿ+2ⁿ⁻¹+2ⁿ⁻²+2ⁿ⁻⁷ (respectively, 2ⁿ+2ⁿ⁻¹+2ⁿ⁻²+2ⁿ⁻⁷+2ⁿ⁻²³⁰) vertices can be embedded in n−1 pages for all n≥9 (respectively, n≥232).     

1-vertex-fault-tolerant cycles embedding on folded hypercubes

In this paper, we focus on a hypercube-like structure, the folded hypercube, which is basically a standard hypercube with some extra links between its nodes. Let f be a faulty vertex in an n-dimensional folded hypercube FQ_n. We show that FQ_n−{f} contains a fault-free cycle of every even length from 4 to 2ⁿ−2 if n≥3 and, furthermore, every odd length from n+1 to 2ⁿ−1 if n≥2 and n is even.