Hypercube graph Q n

This article page is a stub, please help by expanding it.

The  

n

-hypercube graph 

Qn

is the graph with vertices at each corner of the unit 

n

-dimensional hypercube and edges between vertices which are distant by one unit. This graph is undirected and has no loops.

Hypercube graph 

Qn

The 

n

-hypercube graph has 2 n vertices.

Hypercube graph 

Q0

The 0-hypercube graph 

Q0

has 2 0 = 1 vertex.

  0

Hypercube graph 

Q1

The 1-hypercube graph 

Q1

has 2 1 = 2 vertices and 1 edge.

  0 -- 1

Hypercube graph 

Q2

The 2-hypercube graph 

Q2

(square graph) has 2 2 = 4 vertices and 4 edges.

  00 -- 01

  |      |

  10 -- 11

Hypercube graph 

Q3

The 3-hypercube graph 

Q3

(cube graph) has 2 3 = 8 vertices and 12 edges.

  000 ------- 001

  | \         / |

  |  100---101  |

  |  |       |  |

  |  110---111  |

  | /         \ |

  010 ------- 011

Hypercube graph 

Q4

The 

4

-hypercube graph 

Q4

(tesseract graph) has 2 4 = 16 vertices.

Adjacency matrices

Vertex adjacency matrix

Since the 

n

-hypercube graph 

Qn

is undirected and has no loops, the vertex adjacency matrix is symmetrical with diagonal elements equal to 0, so we need only consider the elements of the lower triangular submatrix, i.e. for 0 ≤ i ≤ n and 0 ≤ j < i.

 

Q1

The 

Q1

vertex adjacency submatrix for 0 ≤ i ≤ 1 and 0 ≤ j < i

    0  1
   _____

0 |

1 | 1

 

Q2

The 

Q2

vertex adjacency submatrix for 0 ≤ i ≤ 3 and 0 ≤ j < i

    00 01 10 11
    ___________

00 |

01 | 1

10 | 1  0

11 | 0  1  1

 

Q3

The 

Q3

vertex adjacency submatrix for 0 ≤ i ≤ 7 and 0 ≤ j < i

     000 001 010 011 100 101 110 111
     ________________________________

000 |

001 |  1

010 |  1   0

011 |  0   1   1

100 |  1   0   0   0

101 |  0   1   0   0   1

110 |  0   0   1   0   1   0

111 |  0   0   0   1   0   1   1

Edge adjacency matrix

(...)

Independent vertex sets in the 

n

-hypercube graph 

Qn

An independent vertex set of graph G is a vertex subset of G such that no two vertices represent an edge of G. Vertices of Q_n are adjacent if and only if a single digit differs in the binary representation of their labels, ranging from 0 to 2^n - 1.

The 2 independent vertex sets of 

Q0

are the 1 + 2 0 = 2 [trivial]

{ { }, {0} }.

The 3 independent vertex sets of 

Q1

are the 1 + 2 1 = 3 [trivial]

{ { }, {0}, {1} }.

The 7 independent vertex sets of 

Q2

are the 1 + 2 2 = 5 [trivial]

{ { }, {00}, {01}, {10}, {11} }

and the 2 vertex pairs

{ {10, 01}, {11, 00} }.

The 35 independent vertex sets of 

Q3

are the 1 + 2 3 = 9 [trivial]

{ { }, {000}, {001}, {010}, {011}, {100}, {101}, {110}, {111} },

the 16 vertex pairs with adjacency 0

{ {010, 001}, {011, 000}, {100, 001}, {100, 010}, {100, 011}, {101, 000}, {101, 010}, {101, 011}, {110, 000}, {110, 001}, {110, 011}, {110, 101}, {111, 000}, {111, 001}, {111, 010}, {111, 100} },

the 8 vertex triples whose subset vertex pairs are all among the above 16 vertex pairs

{ {100, 010, 001}, {101, 011, 000}, {110, 011, 000}, {110, 101, 000}, {110, 101, 011}, {111, 010, 001}, {111, 100, 001}, {111, 100, 010} };

and the 2 vertex quadruples whose subset vertex triples are all among the above 8 vertex triples

{ {110, 101, 011, 000}, {111, 100, 010, 001} }.

A027624 Number of independent vertex sets in the n-hypercube graph Q_n.

{2, 3, 7, 35, 743, 254475, 19768832143, ...}

Independent edge sets in the 

n

-hypercube graph 

Qn

A?????? Number of independent edge sets in the n-hypercube graph Q_n.

{?, ...}