An exchanged hypercube is a spanning subgraph of a hypercube. It retains a large number of desirable properties of the hypercube, yet maintains a reduced interconnection complexity. This paper shows that the graph is isomorphic to an induced subgraph of the hypercube of the least possible size. Further, the minimal hypercube consists of two factors, each of which comprises as many vertex-disjoint copies of the induced subgraph. The result is seamlessly inherited by the dual-cube that is known to be a special case of the exchanged hypercube.

Abstract The quad-cube is a special case of the metacube that itself is derivable from the hypercube. It is amenable to an application as a network topology, especially when the node size exceeds several million. This paper presents the following welcome properties of the graph, relating to its structure: (1) vertex transitivity that facilitates the working of an algorithm meant for a “local” context in the global context as well, and (2) an exact formula for the distance metric, which leads to a precise result on the distance-wise vertex distribution of the graph and an exact formula for the average vertex distance. Remarkably, the vertex distribution of the quad-cube resembles, to a large extent, the vertex distribution of the twin copies of a hypercube. In a parallel study, the author recently reported similar results with respect to the dual-cube (Jha in J Supercomput 78:17758–17775, 2022)

A vertex subset$S$of a graph$G$constitutes a 1-perfect code if the one-balls centered at the nodes in$S$effect a vertex partition of$G$. This paper considers the quad-cube$CQ_{m}$that is a connected$(m+2)$-regular spanning subgraph of the hypercube$Q_{4m+2}$, and shows that$CQ_{m}$admits a vertex partition into 1-perfect codes iff$m=2^{k}-3$, where$k\ge 2$. The scheme for that purpose makes use of a procedure by Jha and Slutzki that constructs Hamming codes using a Latin square. The result closely parallels the existence of a 1-perfect code over the dual-cube, which is another derivative of the hypercube.

Abstract The dual-cube, derivable from the hypercube, admits a number of good properties that render it as a good network topology, especially when the node size exceeds several million. This paper presents several other welcome characteristics of the graph. Prominent among them are: (1) vertex transitivity that facilitates the working of an algorithm meant for a “local” context in the global context as well, (2) an exact formula for the distance between two nodes, which leads to a precise result on the distance-wise node distribution of the graph and an exact formula for the average node distance, and (3) a hypercube-like hierarchical structure of the graph that is amenable to an inductive treatment.

A 1-perfect code of a graph G is a set C ⊆ V(G) such that the 1-balls centered at the vertices in C constitute a partition of V(G). In this paper, we consider the dual-cube D Qmthat is a connected (m + 1)-regular spanning subgraph of the hypercube Q2m+1, and show that it admits a 1-perfect code if and only if m = 2k- 2, k ≥ 2. The result closely parallels the existence of Hamming codes over the hypercube. The algorithm for that purpose employs a scheme by Jha and Slutzki for a vertex partition of Qm+1into Hamming codes using a Latin square, and carefully allocates those codes among various m-cubes in D Qm. The result leads to tight bounds on domination numbers of the dual-cube and the exchanged hypercube.

A major result relating to the Hamiltonian decomposition presented by Anantha, Bose, and AlBdaiwi [1], is actually a special case of a more general result already known in the literature.

We show that the 2a\times a rectangular twisted torus introduced by Cámara et al. [5] is edge decomposable into two Hamiltonian cycles. In the process, the 2a × a × a prismatic twisted torus is edge decomposable into three Hamiltonian cycles, and the 2a × a × a prismatic doubly twisted torus admits two edge-disjoint Hamiltonian cycles.

A counterexample is presented to disprove Tang and Padubidri's (1994) claim about the bisection width of a diagonal mesh.