#### Vol. 5, No. 1, 2012

 Recent Issues
 The Journal About the Journal Editorial Board Editors’ Interests Subscriptions Submission Guidelines Submission Form Policies for Authors Ethics Statement ISSN: 1944-4184 (e-only) ISSN: 1944-4176 (print) Author Index Coming Soon Other MSP Journals
Induced subgraphs of Johnson graphs

### Ramin Naimi and Jeffrey Shaw

Vol. 5 (2012), No. 1, 25–37
##### Abstract

The Johnson graph $J\left(n,N\right)$ is defined as the graph whose vertices are the $n$-subsets of the set $\left\{1,2,\dots ,N\right\}$, where two vertices are adjacent if they share exactly $n-1$ elements. Unlike Johnson graphs, induced subgraphs of Johnson graphs (JIS for short) do not seem to have been studied before. We give some necessary conditions and some sufficient conditions for a graph to be JIS, including: in a JIS graph, any two maximal cliques share at most two vertices; all trees, cycles, and complete graphs are JIS; disjoint unions and Cartesian products of JIS graphs are JIS; every JIS graph of order $n$ is an induced subgraph of $J\left(m,2n\right)$ for some $m\le n$. This last result gives an algorithm for deciding if a graph is JIS. We also show that all JIS graphs are edge move distance graphs, but not vice versa.

##### Keywords
Johnson graph, intersection graph, distance graph
Primary: 05C62