Narrow Results

We give a result that implies an improvement by a factor of log log n in the hypercube bounds for the geometric problems of batched planar point location, trapezoidal decomposition, and polygon triangulation. The improvements are achieved through a better solution to the multisearch problem on a hypercube, a parallel search problem where the elements in the data structure S to be searched are totally ordered, but where it is not possible to compare in constant time any two given queries q and q′. Whereas the previous best solution to this problem took O(log n(log log n)³) time on an n-processor hypercube, the solution given here takes O(log n(log log n)²) time on an n-processor hypercube. The hypercube model for which we claim our bounds is the standard one, SIMD, with O(1) memory registers per processor, and with one-port communication. Each register can store O(log n) bits, so that a processor knows its ID.

We will prove that some weighted graphs on the distance-k graph of hypercubes approximate the q-Hermite polynomial of a q-gaussian variable by providing an appropriate matrix model.

An antimedian of a profile π = (x₁, x₂, …, x_k) of vertices of a graph G is a vertex maximizing the sum of the distances to the elements of the profile. The antimedian function is defined on the set of all profiles on G and has as output the set of antimedians of a profile. It is a typical location function for finding a location for an obnoxious facility. The 'converse' of the antimedian function is the median function, where the distance sum is minimized. The median function is well studied. For instance it has been characterized axiomatically by three simple axioms on median graphs. The median function behaves nicely on many classes of graphs. In contrast the antimedian function does not have a nice behavior on most classes. So a nice axiomatic characterization may not be expected. In this paper such a characterization is obtained for two classes of graphs on which the antimedian is well behaved: paths and hypercubes.

In this paper, we consider the problem of decomposing the edge set of the hypercube Q_n into two spanning, regular, connected, bipancyclic subgraphs. We prove that if n = n₁ + n₂ with n₁ ≥ 2 and n₂ ≥ 2, then the edge set of Q_n can be decomposed into two spanning, bipancyclic subgraphs H₁ and H₂ such that H_i is n_i-regular and n_i-connected for i = 1, 2.

It is known that the $n$-dimensional hypercube $Q_n,$ for $n=n_1+n_2$ with $n_i\ge 2,$ can be decomposed into two spanning bipancyclic subgraphs $G_1$ and $G_2$ such that $G_i$ is $n_i$-regular and $n_i$-connected for $i=1,2.$ In this paper, we prove that if $n=n_1+n_2+\cdots +n_k$ with $n_i\ge 2$ and at most one $n_i$ odd, then $Q_n$ can be decomposed into $k$ spanning subgraphs $G_1$, $G_2,\dots ,G_k$ such that $G_i$ is $n_i$-regular and $n_i$-connected for $i=1,2,\dots ,k.$

We consider the problem of determining the possible orders for $k$-regular, $k$-connected and bipancyclic subgraphs of the hypercube $Q_n.$ For $k=2$ and $k=3,$ the solution to the problem is known. In this paper, we solve the problem for $k=4$ by proving that $Q_n$ has a 4-regular, 4-connected and bipancyclic subgraph on $l$ vertices if and only if $l=16$ or $l$ is an even integer such that $24\le l\le 2^n.$ Further, by improving a result of Ramras, we prove that a $k$-regular subgraph of $Q_n$ is either isomorphic to $Q_k$ or has at least $2^k+2^{k-1}$ vertices. We also improve a result of Mane and Waphare regarding the existence of a $k$-regular, $k$-connected and bipancyclic subgraph of $Q_n.$ Some applications of our results are given.

Let $A(n,d)$ be the size of the maximum binary code of length $n$ and minimum Hamming distance $d$. $A(n,d,w)$ is defined similarly for binary code with constant weight $w$. Obviously, finding the value of $A(n,d)$ is equivalent to finding the maximum independent set of the $d-1$th-power of $n$-dimensional hypercube. Based on this, this paper obtains that $A(3m,2m)=4$, $A(\frac{m(m+1)}{2},2m-2,m)=m+1$, $A(2^{m+1}-2,2^m-1)=2^{m+1}$, and explores the structure of the maximum code of length $2^{m+2}$ and minimum Hamming distance $2^{m+1}$, where $m$ is an integer.

The sunlet graph of order eight, denoted by $L_8,$ is the graph obtained by adding a pendant edge to each vertex of a cycle of length $4.$ We prove that the $n$-dimensional hypercube $Q_n$ can be decomposed into the copies of the graph $L_8$ if and only if $n$ is 4 or $n\ge 6.$

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 a sequence of graphs, leading up to the quad-cube, where the graphs in the sequence are important in their own right. For example, they exhibit hypercube-like low diameters and efficient domination parameters, and most of them admit a Hamiltonian cycle. The hierarchy is likely to be useful in the future.