There are no approved revisions of this page, so it may
not have been
reviewed.
This article page is a stub, please help by expanding it.
The
-hypercube graph is the
graph with vertices at each corner of the unit
-dimensional
hypercube and edges between vertices which are distant by one unit. This graph is undirected and has no loops.
Hypercube graph
The
-hypercube graph has 2
n vertices.
Hypercube graph
The 0-hypercube graph
has 2
0 = 1 vertex.
0
Hypercube graph
The 1-hypercube graph
has 2
1 = 2 vertices and 1 edge.
0 -- 1
Hypercube graph
The 2-hypercube graph
(square graph) has 2
2 = 4 vertices and 4 edges.
00 -- 01
| |
10 -- 11
Hypercube graph
The 3-hypercube graph
(cube graph) has 2
3 = 8 vertices and 12 edges.
000 ------- 001
| \ / |
| 100---101 |
| | | |
| 110---111 |
| / \ |
010 ------- 011
Hypercube graph
The
-hypercube graph
(tesseract graph) has 2
4 = 16 vertices.
Adjacency matrices
Vertex adjacency matrix
Since the
-hypercube graph
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.
The
vertex adjacency submatrix for 0 ≤ i ≤ 1 and 0 ≤ j < i
0 1
_____
0 |
1 | 1
The
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
The
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 -hypercube graph
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
are the 1 + 2
0 = 2 [trivial]
- { { }, {0} }.
The 3 independent vertex sets of
are the 1 + 2
1 = 3 [trivial]
- { { }, {0}, {1} }.
The 7 independent vertex sets of
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
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 -hypercube graph
A?????? Number of independent edge sets in the n-hypercube graph Q_n.
- {?, ...}