|
EXAMPLE
|
a(0) = 2 since {} and {0} are independent vertex sets of Q_0, which is the graph consisting of a single vertex labeled 0.
a(1) = 3 since Q_1 = 0---1 has independent vertex sets {}, {0}, {1}.
Independent vertex set (resp. vertex cover) of graph G: vertex subset of G such that at most (resp. at least) one vertex 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.
a(2) = 7 since Q_2 is
00---01
| |
10---11
with vertex adjacency submatrix M_2 =
M_1
I_2 M_1
for 0 <= i <= 3 and 0 <= j < i
00 01 10 11
___________
00 |
01 | 1
10 | 1 0
11 | 0 1 1
yielding the 1 + 4 trivial: { } and {00}, {01}, {10}, {11};
the 2 (= 0 + (4 - 2) + 0) pairs with adjacency 0: {10, 01}, {11, 00};
for a total of 7 = 1 + 2^2 + 2 independent vertex sets.
a(3) = 35 since Q_3 is
000---------001
| \ / |
| 100---101 |
| | | |
| 110---111 |
| / \ |
010---------011
with vertex adjacency submatrix M_3 =
M_2
I_4 M_2
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
yielding the 1 + 8 trivial: { } and
{000}, {001}, {010}, {011}, {100}, {101}, {110}, {111};
the 16 (= 2 + (16 - 4) + 2) 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 triples whose subset pairs are all among the above 16 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};
the 2 quadruples whose subset triples are all among the above 8 triples:
{10, 01} & 1 union {11, 00} & 0 =
{110, 101, 011, 000} and
{10, 01} & 0 union {11, 00} & 1 =
{111, 100, 010, 001};
for a total of 35 = 1 + 2^3 + 16 + 8 + 2 independent vertex sets. (End)
The above 2 quadruples represent a vertex 2-coloring of Q_3. - Daniel Forgues, Feb 17 2015
a(4) = 743 since Q_4 is (...) with vertex adjacency submatrix M_4 =
M_3
I_8 M_3
for 0 <= i <= 15 and 0 <= j < i (...) yielding the 1 + 16 trivial: (...);
the 88 (= 16 + (64 - 8) + 16) pairs with adjacency 0: (...);
the 208 triples: (...); the 228 quadruples: (...);
the 128 quintuples: (...); the 56 sextuples: (...);
the 16 (= 2 * (8 choose 7)) septuples: (...);
and the 2 octuples (representing a vertex 2-coloring of Q_4):
{110, 101, 011, 000} & 1 union {111, 100, 010, 001} & 0 =
{1101, 1011, 0111, 0001, 1110, 1000, 0100, 0010} and
{110, 101, 011, 000} & 0 union {111, 100, 010, 001} & 1 =
{1100, 1010, 0110, 0000, 1111, 1001, 0101, 0011}.
|