We quantify why, as designers, we should prefer clique-based hypercubes (K-cubes) over traditional hypercubes based on cycles (C-cubes). Reaping fresh analytic results, we find that K-cubes minimize ...the wirecount and, simultaneously, the latency of hypercube architectures that tolerate failure of any f nodes. Refining the graph model of Hayes (1976), we pose the feasibility of configuration as a problem in multivariate optimization: What (f+1)-connected n-vertex graphs with fewest edges n(f+1)/2 minimize the maximum a) radius or b) diameter of subgraphs (i.e., quorums) induced by deleting up to f vertices? We solve (1) for f that is superlogarithmic but sublinear in n and, in the process, prove: 1) the fault tolerance of K-cubes is proportionally greater than that of C-cubes; 2) quorums formed from K-cubes have a diameter that is asymptotically convergent to the Moore Bound on radius; 3) under any conditions of scaling, by contrast, C-cubes diverge from the Moore Bound. Thus, K-cubes are optimal, while C-cubes are suboptimal. Our exposition furthermore: 4) counterexamples, corrects, and generalizes a mistaken claim by Armstrong and Gray (1981) concerning binary cubes; 5) proves that K-cubes and certain of their quorums are the only graphs which can be labeled such that the edge distance between any two vertices equals the Hamming distance between their labels; and 6) extends our results to K-cube-connected cycles and edges. We illustrate and motivate our work with applications to the synthesis of multicomputer architectures for deep space missions.
Hamming graphs are simply Cartesian products of complete graphs. Several characterizations of these graphs involve the notion of intervals in a graph and related topics. The notion of interval ...distance monotonicity has already been used in order to obtain a characterization of hypercubes. Here, we revisit this notion and use it to obtain a new characterization of Hamming graphs by performing a combination of the hypercube characterization and the interval hypercube characterization.
Let G be a t-uniform s-regular linear hypergraph with r vertices. It is shown that the number of independent sets $\IS(\hgraph)$ in $\hgraph$ satisfies \ \log_2 \IS(\hgraph) \le \frac{r}{t} \left( 1 ...+ O \biggl( \frac{\log^2(ts)}{s} \biggr) \right) . \ This leads to an improvement of a previous bound by Alon obtained for t = 2 (i.e., for regular ordinary graphs). It is also shown that for the Hamming graph $\Hamming(n,q)$ (with vertices consisting of all n-tuples over an alphabet of size q and edges connecting pairs of vertices with Hamming distance $1$), \ \frac{\log_2 \IS(\Hamming(n,q))}{q^n} = \frac{1}{q} + O \biggl(\frac{\log^2 (q n)}{q n} \biggr). \ The latter result is then applied to show that the Shannon capacity of the n-dimensional $(d,\infty)$-runlength-limited (RLL) constraint converges to 1/(d+1) as n goes to infinity.
Hamming Graphs and Permutation Codes Barta, Janos; Montemanni, Roberto
2017 Fourth International Conference on Mathematics and Computers in Sciences and in Industry (MCSI),
2017-Aug.
Conference Proceeding
A permutation code can be represented as a graph, in which the nodes correspond to the permutation codewords and the weights on the edges are the Hamming distances between the codewords. Graphs ...belonging to this class are called permutation Hamming graphs. This paper explores the Maximum Permutation Code Problem (MPCP), a well-known optimization problem in coding theory, by means of a graph theoretical approach. Permutation Hamming graphs turn out to satisfy strong regularity properties, such as vertex transitivity and r-partiteness. In addition, exact formulas for the degree of the vertices and for the number of the edges are presented. Furthermore, a remarkable similarity between permutation Hamming graphs and Turán graphs is enlightened. The new link with Turán graphs might help to improve current results on the MPCP.
We consider the graphs
H
a
n
defined as the Cartesian products of n complete graphs with a vertices each. Let an edge cut partition the vertex set of a graph into k subsets
A
1,…,
A
k
with ||
A
i
|−|
...A
j
||⩽1. We consider the problem of determining the minimal size of such a cut for the graphs defined above and present bounds and asymptotic results for some specific values of k.
We prove that a hypergraph is a product of a finite number of edges if and only if it is interval-regular, satisfies the gated-edge property and has a vertex of finite degree. As a consequence, we ...get a characterization of Hamming graphs.
Hamming graphs are, by definition, the Cartesian product of complete graphs. In the bipartite case these graphs are hypercubes. We present an algorithm recognizing Hamming graphs in linear time and ...space. This improves a previous algorithm which was linear in time but not in space. This also favorably compares to the general decomposition algorithms of graphs with respect to the Cartesian product, none of which is linear.
PDF
