3
$\begingroup$

For positive integers $n \geq k$, the Hamming graph $H(n,k)$ is constructed on the vertex set $\{0,1\}^n$ in the following manner. For $x,y \in \{0,1\}^n$ the Hamming distance of $x,y$ is the number of elements of the set $\{ i \in \{0, ..., n-1\} : x(i) \neq y(i)\}$ (i.e. we count the positions on which $x$ and $y$ do not agree), and denote that number by $d_H(x,y)$. Let the edge set of $H(n,k)$ be given by $$E\big(H(n,k)\big) := \big\{\{x,y\}: x\neq y \in \{0,1\}^n \text{ and }d_H(x,y)\leq k\big\}.$$

It is known that for every simple, finite, undirected graph $G=(V,E)$ there are integers $n\geq k$, such that $G$ is isomorphic to an induced subgraph of $H(n,k)$. Let $\text{h}(G)$ denote the smallest positive integer $n$ such that there is a positive integer $k\leq n$ such that $G$ is isomorphic to some induced subgraph of $H(n,k)$.

As an example, the complete graph $K_{2^n}$ is isomorphic to $H(n,n)$, and so we get $\text{h}(K_{2^n}) = n$.

Question. Is there a positive integer $n_0$ such that we have $\text{h}(G) \leq |V(G)|$ for every finite simple undirected graph $G$ with at least $n_0$ vertices?

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .