Return to Question

• The vertices are all (ordered) $k$-tuples with distinct components from a universe of size $n$.
• Two vertices are adjacent if their Hamming distance is 1 (i.e. if they differ in exactly one component).

Notice that this graph has $\frac{n!}{(n-k)!}$ vertices. Each vertex has $k(n-k)$ edges of the first kind and $\binom{k}{2}$ edges of the second kind. Thus, this is a regular graph with parameter $\frac{k(2n - k - 1)}{2}$.

Does the graph have a name?

A closely related graph is the Hamming graph (denoted by $H(n,k)$), which does not exclude the tuples with duplicate components. It has $k^n$ vertices. It is closely related because the graph I am looking for is the induced subgraph of $H(n,k)$ after removing the vertices corresponding to tuples with repeat components.

Another similar graph is the Johnson graph, whose vertices are all subsets of size $k$ from a universe of size n with an edge between two vertices if their set intersection is $n-1$. It has $\binom{n}{k}$ vertices.

The Kneser graph (and its generalization) have similar definitions as well, but like the Johnson graph, they also have $\binom{n}{k}$ vertices.

• The vertices are all (ordered) $k$-tuples with distinct components from a universe of size $n$.
• Two vertices are adjacent if their Hamming distance is 1 (i.e. if they differ in exactly one component).

Notice that this graph has $\frac{n!}{(n-k)!}$ vertices. It is an $k(n-k)$-regular graph.

Does the graph have a name?

A closely related graph is the Hamming graph (denoted by $H(n,k)$), which does not exclude the tuples with duplicate components. It has $k^n$ vertices. It is closely related because the graph I am looking for is the induced subgraph of $H(n,k)$ after removing the vertices corresponding to tuples with repeat components.

Another similar graph is the Johnson graph, whose vertices are all subsets of size $k$ from a universe of size n with an edge between two vertices if their set intersection is $n-1$. It has $\binom{n}{k}$ vertices.

The Kneser graph (and its generalization) have similar definitions as well, but like the Johnson graph, they also have $\binom{n}{k}$ vertices.

• The vertices are all (ordered) $k$-tuples with distinct components from a universe of size $n$.
• Two vertices are adjacent if their Hamming distance is 1 (i.e. if they differ in exactly one component).

Notice that this graph has $\frac{n!}{(n-k)!}$ vertices.

Does the graph have a name?

A closely related graph is the Hamming graph (denoted by $H(n,k)$), which does not exclude the tuples with duplicate components. It has $k^n$ vertices. It is closely related because the graph I am looking for is the induced subgraph of $H(n,k)$ after removing the vertices corresponding to tuples with repeat components.

Another similar graph is the Johnson graph, whose vertices are all subsets of size $k$ from a universe of size n with an edge between two vertices if their set intersection is $n-1$. It has $\binom{n}{k}$ vertices.

The Kneser graph (and its generalization) have similar definitions as well, but like the Johnson graph, they also have $\binom{n}{k}$ vertices.

• The vertices are all (ordered) $k$-tuples with distinct components from a universe of size $n$.
• Two vertices are adjacent if their Hamming distance is 1 (i.e. if they differ in exactly one component).

Notice that this graph has $\frac{n!}{(n-k)!}$ vertices. Each vertex has $k(n-k)$ edges of the first kind and $\binom{k}{2}$ edges of the second kind. Thus, this is a regular graph with parameter $\frac{k(2n - k - 1)}{2}$.

Does the graph have a name?

A closely related graph is the Hamming graph (denoted by $H(n,k)$), which does not exclude the tuples with duplicate components. It has $k^n$ vertices. It is closely related because the graph I am looking for is the induced subgraph of $H(n,k)$ after removing the vertices corresponding to tuples with repeat components.

Another similar graph is the Johnson graph, whose vertices are all subsets of size $k$ from a universe of size n with an edge between two vertices if their set intersection is $n-1$. It has $\binom{n}{k}$ vertices.

The Kneser graph (and its generalization) have similar definitions as well, but like the Johnson graph, they also have $\binom{n}{k}$ vertices.

• The vertices are all (ordered) $k$-tuples with distinct components from a universe of size $n$.
• Two vertices are adjacent if their Hamming distance is 1 (i.e. if they differ in exactly one component).

Notice that this graph has $\frac{n!}{(n-k)!}$ vertices.

Does the graph have a name?

A closely related graph is the Hamming graph, which does not exclude the tuples with duplicate components. It has $k^n$ vertices.

Another similar graph is the Johnson graph, whose vertices are all subsets of size $k$ from a universe of size n with an edge between two vertices if their set intersection is $n-1$. It has $\binom{n}{k}$ vertices.

The Kneser graph (and its generalization) have similar definitions as well, but like the Johnson graph, they also have $\binom{n}{k}$ vertices.

• The vertices are all (ordered) $k$-tuples with distinct components from a universe of size $n$.
• Two vertices are adjacent if their Hamming distance is 1 (i.e. if they differ in exactly one component).

Notice that this graph has $\frac{n!}{(n-k)!}$ vertices.

Does the graph have a name?

A closely related graph is the Hamming graph (denoted by $H(n,k)$), which does not exclude the tuples with duplicate components. It has $k^n$ vertices. It is closely related because the graph I am looking for is the induced subgraph of $H(n,k)$ after removing the vertices corresponding to tuples with repeat components.

Another similar graph is the Johnson graph, whose vertices are all subsets of size $k$ from a universe of size n with an edge between two vertices if their set intersection is $n-1$. It has $\binom{n}{k}$ vertices.

The Kneser graph (and its generalization) have similar definitions as well, but like the Johnson graph, they also have $\binom{n}{k}$ vertices.