Skip to main content
added definition
Source Link
Carlo Beenakker
  • 188.2k
  • 18
  • 448
  • 651

The Hamming graph $H(n,d)$ has $2^n$ vertices labeled by the binary vectors of length $n$, two vertices being joined by an edge if and only if the Hamming distance between the corresponding vectors is at least $d$. More generally $H_q(n,d)$ refers to $q^n$ vertices labeled by $q$-ary vectors of length $n$.

  • N.J.A. Sloane, Unsolved Problems in Graph Theory Arising from the Study of Codes (1989)

The independence number $\alpha(H_q(n,d))$ of the Hamming graph $H_q(n,d)$ is determined by the maximum number $N_q(n,s)$ of $q$-ary sequences of length $n$ that intersect pairwise, i.e., have the same entries, in at least $s=n-d+1$ positions.

You want the binary case $q=2$. Closed-form expressions for the number $N_q(n,s)$ exist, see cited references and Theorem 2 of

The independence number $\alpha(H_q(n,d))$ of the Hamming graph $H_q(n,d)$ is determined by the maximum number $N_q(n,s)$ of $q$-ary sequences of length $n$ that intersect pairwise, i.e., have the same entries, in at least $s=n-d+1$ positions.

You want the binary case $q=2$. Closed-form expressions for the number $N_q(n,s)$ exist, see cited references and Theorem 2 of

The Hamming graph $H(n,d)$ has $2^n$ vertices labeled by the binary vectors of length $n$, two vertices being joined by an edge if and only if the Hamming distance between the corresponding vectors is at least $d$. More generally $H_q(n,d)$ refers to $q^n$ vertices labeled by $q$-ary vectors of length $n$.

  • N.J.A. Sloane, Unsolved Problems in Graph Theory Arising from the Study of Codes (1989)

The independence number $\alpha(H_q(n,d))$ of the Hamming graph $H_q(n,d)$ is determined by the maximum number $N_q(n,s)$ of $q$-ary sequences of length $n$ that intersect pairwise, i.e., have the same entries, in at least $s=n-d+1$ positions.

You want the binary case $q=2$. Closed-form expressions for the number $N_q(n,s)$ exist, see cited references and Theorem 2 of

reference
Source Link
Carlo Beenakker
  • 188.2k
  • 18
  • 448
  • 651

The independence number $\alpha(H_q(n,d))$ of the Hamming graph $H_q(n,d)$ is determined by the maximum number $N_q(n,s)$ of $q$-ary sequences of length $n$ that intersect pairwise, i.e., have the same entries, in at least $s=n-d+1$ positions.

You want the binary case $q=2$ and for this case closed. Closed-form expressions for thisthe number $N_2(n,s)$$N_q(n,s)$ exist (see, see cited references). and Theorem 2 of

The independence number $\alpha(H_q(n,d))$ of the Hamming graph $H_q(n,d)$ is determined by the maximum number $N_q(n,s)$ of $q$-ary sequences of length $n$ that intersect pairwise, i.e., have the same entries, in at least $s=n-d+1$ positions.

You want the binary case $q=2$ and for this case closed-form expressions for this number $N_2(n,s)$ exist (see cited references).

The independence number $\alpha(H_q(n,d))$ of the Hamming graph $H_q(n,d)$ is determined by the maximum number $N_q(n,s)$ of $q$-ary sequences of length $n$ that intersect pairwise, i.e., have the same entries, in at least $s=n-d+1$ positions.

You want the binary case $q=2$. Closed-form expressions for the number $N_q(n,s)$ exist, see cited references and Theorem 2 of

Source Link
Carlo Beenakker
  • 188.2k
  • 18
  • 448
  • 651

The independence number $\alpha(H_q(n,d))$ of the Hamming graph $H_q(n,d)$ is determined by the maximum number $N_q(n,s)$ of $q$-ary sequences of length $n$ that intersect pairwise, i.e., have the same entries, in at least $s=n-d+1$ positions.

You want the binary case $q=2$ and for this case closed-form expressions for this number $N_2(n,s)$ exist (see cited references).