Home » Keyword index

hypercube


Graph Theory » Extremal G.T.

Weak saturation of the cube in the clique ★

Author(s): Morrison; Noel

Problem  

Determine $ \text{wsat}(K_n,Q_3) $.

Keywords: bootstrap percolation; hypercube; Weak saturation

Posted by Jon Noel
updated April 6th, 2016
add new comment
Combinatorics

Turán Problem for $10$-Cycles in the Hypercube ★★

Author(s): Erdos

Problem   Bound the extremal number of $ C_{10} $ in the hypercube.

Keywords: cycles; extremal combinatorics; hypercube

Posted by Jon Noel
updated September 20th, 2015
add new comment
Combinatorics

Extremal $4$-Neighbour Bootstrap Percolation in the Hypercube ★★

Author(s): Morrison; Noel

Problem   Determine the smallest percolating set for the $ 4 $-neighbour bootstrap process in the hypercube.

Keywords: bootstrap percolation; extremal combinatorics; hypercube; percolation

Posted by Jon Noel
updated September 20th, 2015
add new comment
Combinatorics

Saturation in the Hypercube ★★

Author(s): Morrison; Noel; Scott

Question   What is the saturation number of cycles of length $ 2\ell $ in the $ d $-dimensional hypercube?

Keywords: cycles; hypercube; minimum saturation; saturation

Posted by Jon Noel
updated September 20th, 2015
add new comment
Graph Theory » Coloring » Vertex coloring

Coloring squares of hypercubes ★★

Author(s): Wan

If $ G $ is a simple graph, we let $ G^{(2)} $ denote the simple graph with vertex set $ V(G) $ and two vertices adjacent if they are distance $ \le 2 $ in $ G $.

Conjecture   $ \chi(Q_d^{(2)}) = 2^{ \lfloor \log_2 d \rfloor + 1} $.

Keywords: coloring; hypercube

Posted by mdevos
updated December 10th, 2008
1 comment
Graph Theory » Basic G.T. » Matchings

Matchings extend to Hamiltonian cycles in hypercubes ★★

Author(s): Ruskey; Savage

Question   Does every matching of hypercube extend to a Hamiltonian cycle?

Keywords: Hamiltonian cycle; hypercube; matching

Posted by Jirka
updated September 28th, 2007
add new comment
Graph Theory » Topological G.T. » Crossing numbers

The Crossing Number of the Hypercube ★★

Author(s): Erdos; Guy

The crossing number $ cr(G) $ of $ G $ is the minimum number of crossings in all drawings of $ G $ in the plane.

The $ d $-dimensional (hyper)cube $ Q_d $ is the graph whose vertices are all binary sequences of length $ d $, and two of the sequences are adjacent in $ Q_d $ if they differ in precisely one coordinate.

Conjecture   $ \displaystyle \lim \frac{cr(Q_d)}{4^d} = \frac{5}{32} $

Keywords: crossing number; hypercube

Posted by Robert Samal
updated July 18th, 2008
1 comment
Syndicate content