This site is supported by donations to The OEIS Foundation.

Hypercube graph Q n

From OeisWiki
Jump to: navigation, search


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 2n 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.

{?, ...}