|
|||||
 |
|
|
|
|
|
Induced subgraphs
of Johnson graphs
Ramin Naimi and Jeffrey Shaw
Vol. 5 (2012), No. 1, 25–37
|
Abstract |
|
The Johnson graph is defined as the graph whose vertices are the -subsets of the set , where two vertices are adjacent if they share exactly 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 is an induced subgraph of for some . 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
|
Mathematical Subject Classification 2000
Primary: 05C62
|
Milestones
Received: 4 August 2010
Revised: 1 July 2011
Accepted: 9 July 2011
Published: 28 April 2012
Communicated by Jerrold Griggs
|
Authors |
| Ramin Naimi | |
| Department of Mathematics Occidental College 1600 Campus Road Los Angeles, CA 90041-3314 United States |
|
| Jeffrey Shaw | |
| Department of Mathematics Occidental College 1600 Campus Road Los Angeles, CA 90041-3314 United States |
|
|
