Johnson graph

• Both $J(n,1)$ and $J(n,n-1)$ are the complete graph {{mvar|K_n}}.
• $J(4,2)$ is the octahedral graph.{{citation

| last = Stanić | first = Zoran

| year = 2017

| title = Regular Graphs: A Spectral Approach

| url = https://books.google.com/books?id=igLEDgAAQBAJ&pg=PA63

| page = 63–64

| publisher = de Gruyter

| isbn = 978-3-11-035135-4

}}

• $J(5,2)$ is the complement of the Petersen graph, hence the line graph of {{math|K₅}}. More generally, for all $n$, the Johnson graph $J(n,2)$ is the line graph of {{mvar|K_n}} and the complement of the Kneser graph $K(n,2).$

• $J(n,k)$ is isomorphic to $J(n,n-k).$
• For all $0\; \backslash leq\; j\; \backslash leq\; \backslash operatorname\{diam\}(J(n,k))$, any pair of vertices at distance $j$ share $k-j$ elements in common.
• $J(n,k)$ is Hamilton-connected, meaning that every pair of vertices forms the endpoints of a Hamiltonian path in the graph. In particular this means that it has a Hamiltonian cycle.{{citation|last=Alspach|first=Brian|title=Johnson graphs are Hamilton-connected| year=2013| authorlink=Brian Alspach|journal=Ars Mathematica Contemporanea|volume=6|issue=1|pages=21–23|doi=10.26493/1855-3974.291.574|doi-access=free}}.
• It is also known that the Johnson graph $J(n,k)$ is $k(n-k)$-vertex-connected.{{citation|title=On Connectivity of the Facet Graphs of Simplicial Complexes|year=2015|last1=Newman|last2=Rabinovich|first1=Ilan|first2=Yuri|arxiv=1502.02232|bibcode=2015arXiv150202232N}}.
• $J(n,k)$ forms the graph of vertices and edges of an (n − 1)-dimensional polytope, called a hypersimplex.{{citation|last=Rispoli|first=Fred J.|title=The graph of the hypersimplex|year=2008|arxiv=0811.2981|bibcode=2008arXiv0811.2981R}}.
• the clique number of $J(n,k)$ is given by an expression in terms of its least and greatest eigenvalues: $\backslash omega(J(n,k))\; =\; 1\; -\; \backslash lambda\_\{\backslash max\}/\backslash lambda\_\{\backslash min\}.$
• The chromatic number of $J(n,k)$ is at most $n,\; \backslash chi(J(n,k))\; \backslash leq\; n.${{citation|url=https://www.win.tue.nl/~aeb/graphs/Johnson.html|title=Johnson|website=www.win.tue.nl|access-date=2017-07-26}}
• Each Johnson graph is locally grid, meaning that the induced subgraph of the neighbors of any vertex is a rook's graph. More precisely, in the Johnson graph $J(n,k)$, each neighborhood is a $k\backslash times\; (n-k)$ rook's graph.{{citation

| last = Cohen | first = Arjeh M.

| editor1-last = Kantor | editor1-first = William M.

| editor2-last = Liebler | editor2-first = Robert A.

| editor3-last = Payne | editor3-first = Stanley E.

| editor4-last = Shult | editor4-first = Ernest E.

| contribution = Local recognition of graphs, buildings, and related geometries

| contribution-url = https://pure.tue.nl/ws/files/1882013/588207.pdf

| mr = 1072157

| pages = 85–94

| publisher = Oxford University Press

| series = Oxford Science Publications

| title = Finite Geometries, Buildings, and Related Topics: Papers from the Conference on Buildings and Related Geometries held in Pingree Park, Colorado, July 17–23, 1988

| year = 1990}}; see in particular pp. 89–90

There is a distance-transitive subgroup of $\backslash operatorname\{Aut\}(J(n,k))$ isomorphic to $\backslash operatorname\{Sym\}(n)$. In fact, $\backslash operatorname\{Aut\}(J(n,k))\; \backslash cong\; \backslash operatorname\{Sym\}(n)$, except that when $n\; =\; 2k\; \backslash geq\; 4$, $\backslash operatorname\{Aut\}(J(n,k))\; \backslash cong\; \backslash operatorname\{Sym\}(n)\; \backslash times\; C\_2$.{{citation|title=Distance-Regular Graphs|last=Brouwer |first=Andries E.|date=1989|publisher=Springer Berlin Heidelberg|others=Cohen, Arjeh M., Neumaier, Arnold.|isbn=9783642743436|location=Berlin, Heidelberg|oclc=851840609}}

As a consequence of being distance-transitive, $J(n,k)$ is also distance-regular. Letting $d$ denote its diameter, the intersection array of $J(n,k)$ is given by

:$\backslash left\backslash \{\; b\_\{0\},\; \backslash ldots,\; b\_\{d-1\},\; c\_\{1\},\; \backslash ldots\; c\_\{d\}\; \backslash right\; \backslash \}$

where:

:$\backslash begin\{align\}$

b_{j} &= (k - j)(n - k - j) && 0 \leq j < d \\

c_{j} &= j^2 && 0 < j \leq d

\end{align}

It turns out that unless $J(n,k)$ is $J(8,2)$, its intersection array is not shared with any other distinct distance-regular graph; the intersection array of $J(8,2)$ is shared with three other distance-regular graphs that are not Johnson graphs.

• The characteristic polynomial of $J(n,k)$ is given by

::$\backslash phi(x)\; :=\; \backslash prod\_\{j=0\}^\{\backslash operatorname\{diam\}(J(n,k))\}\; \backslash left\; (x-A\_\{n,k\}(j)\backslash right\; )^\{\backslash binom\{n\}\{j\}\; -\; \backslash binom\{n\}\{j-1\}\}.$

:where $A\_\{n,k\}(j)\; =\; (k-j)(n-k-j)-j.$

• The eigenvectors of $J(n,k)$ have an explicit description.{{citation|last=Filmus|first=Yuval|title=An Orthogonal Basis for Functions over a Slice of the Boolean Hypercube|journal=The Electronic Journal of Combinatorics |year=2014|volume=23 |doi=10.37236/4567 |arxiv=1406.0142|bibcode=2014arXiv1406.0142F|s2cid=7416206 }}.

The Johnson graph $J(n,k)$ is closely related to the Johnson scheme, an association scheme in which each pair of {{mvar|k}}-element sets is associated with a number, half the size of the symmetric difference of the two sets.{{citation|last=Cameron|first=Peter J.|title=Permutation Groups|url=https://books.google.com/books?id=4bNj8K1omGAC&pg=PA95|year=1999|series=London Mathematical Society Student Texts|volume=45|page=95|publisher=Cambridge University Press|isbn=9780521653787}}. The Johnson graph has an edge for every pair of sets at distance one in the association scheme, and the distances in the association scheme are exactly the shortest path distances in the Johnson graph.The explicit identification of graphs with association schemes, in this way, can be seen in {{citation | last = Bose | first = R. C.

| journal = Pacific Journal of Mathematics | mr = 0157909 | pages = 389–419 | title = Strongly regular graphs, partial geometries and partially balanced designs | volume = 13 | issue = 2 | year = 1963 | doi=10.2140/pjm.1963.13.389| doi-access = free }}.

The Johnson scheme is also related to another family of distance-transitive graphs, the odd graphs, whose vertices are $k$-element subsets of an $(2k+1)$-element set and whose edges correspond to disjoint pairs of subsets.

The vertex-expansion properties of Johnson graphs, as well as the structure of the corresponding extremal sets of vertices of a given size, are not fully understood. However, an asymptotically tight lower bound on expansion of large sets of vertices was recently obtained.{{citation|title=An Approximate Vertex-Isoperimetric Inequality for $r$-sets |year=2013 |last1=Christofides |last2=Ellis |last3=Keevash |first1=Demetres |first2=David |first3=Peter|journal=The Electronic Journal of Combinatorics|volume=4|issue=20}}.

In general, determining the chromatic number of a Johnson graph is an open problem.{{citation|title=Erdős-Ko-Rado theorems : algebraic approaches|last1=Godsil |first1=C. D.|last2=Meagher |first2=Karen |isbn=9781107128446|location=Cambridge, United Kingdom|oclc=935456305|year = 2016}}

• Grassmann graph

{{reflist}}

• {{mathworld|title=Johnson Graph|urlname=JohnsonGraph|mode=cs2}}
• {{citation| url = http://www.win.tue.nl/~aeb/graphs/Johnson.html| title = Johnson graphs| first = Andries E.| last = Brouwer| authorlink = Andries E. Brouwer}}

Category:Parametric families of graphs

Category:Regular graphs