Results 71 to 80 of about 5,839 (198)
Complete Sets of Mutually Orthogonal Hypercubes and Their Connections to Affine Resolvable Designs
, 2001 Recently, Laywine and Mullen proved several generalizations of Bose\u27s equivalence between the existence of complete sets of mutually orthogonal Latin squares of order n and the existence of affine planes of order n.
Morgan, Ilene H.
core +1 more source
Hunting rabbits on the hypercube
Discrete Mathematics, 2019 We explore the Hunters and Rabbits game on the hypercube. In the process, we find the solution for all classes of graphs with an isoperimetric nesting property and find the exact hunter number of $Q^n$ to be $1+\sum\limits_{i=0}^{n-2} \binom{i}{\lfloor i/2 \rfloor}$.
Jessalyn Bolkema, Corbin Groothuis
openaire +2 more sources
On Recursively Directed Hypercubes [PDF]
The Electronic Journal of Combinatorics, 2001 In this paper we introduce the recursively directed hypercubes, and analyze some of their structural properties. We show that every recursively directed hypercube is acyclic, and has a unique pair of source and sink nodes. The main contribution of the paper is an analysis of distances between the nodes in such a graph.
openaire +3 more sources
Randomly twisted hypercubes -- between structure and randomness [PDF]
, 2023 Twisted hypercubes are generalizations of the Boolean hypercube, obtained by iteratively connecting two instances of a graph by a uniformly random perfect matching. Dudek et al.
Dikstein, Yotam +3 more
core
CoRRFor an undirected graph $G$, a dominating broadcast on $G$ is a function $f : V(G) \rightarrow \mathbb{N}$ such that for any vertex $u \in V(G)$, there exists a vertex $v \in V(G)$ with $f(v) \geqslant 1$ and $d(u,v) \leqslant f(v)$. The cost of $f$ is $\sum_{v \in V} f(v)$.
Deepak Rajendraprasad +3 more
openaire +4 more sources
Optimal Dynamic Embeddings of Complete Binary Trees into Hypercubes
, 1998 The double-rooted complete binary tree is a complete binary tree where the root is replaced by an edge. It is folklore that the double-rooted complete binary tree is a spanning tree of the hypercube of the same size. Unfortunately, the usual construction
Ernst W. Mayr +2 more
core
Journal of Graph Algorithms and Applications, 2009 We settle an open problem mentioned in Diaz, Petit, and Serna: A survey of graph layout problems (ACM Computing Surveys 34:313-356, 2002). Of eight objectives considered in that survey, only the complexity status of minimum vertex bisection is listed as ...
Ulrik Brandes, Daniel Fleischer
doaj +1 more source
Hamilton Decompositions and (n/2)-Factorizations of Hypercubes
Journal of Graph Algorithms and Applications, 2003 Since Qn, the hypercube of dimension n, is known to have n link-disjoint paths between any two nodes, the links of Qn can be partitioned into multiple link-disjoint spanning subnetworks, or factors. We seek to identify factors which efficiently simulate
Douglas Bass, I. Hal Sudborough
doaj +1 more source
Realization of pipelined mesh algorithms on hypercubes
, 2012 [[abstract]]Presents efficient techniques for realisation of pipelined mesh algorithms on hypercubes. A mesh algorithm is an algorithm inherently suited to a mesh-connected iterative logic array. Previous treatment of the subject by other researchers was
LIN KJ;WU CW
core
Chic. J. Theor. Comput. Sci., 2014 In this paper, we investigate the validity of the Unique Games Conjecture when the constraint graph is the boolean hypercube. We construct an almost optimal integrality gap instance on the Hypercube for the Goemans-Williamson semidefinite program (SDP) for Max-2-LIN$(\mathbb{Z}_2)$.
Naman Agarwal +3 more
openaire +4 more sources