Vol. 5, No. 1, 2012

Download this article
Download this article For screen
For printing
Recent Issues

Volume 11
Issue 2, 181–359
Issue 1, 1–179

Volume 10, 5 issues

Volume 9, 5 issues

Volume 8, 5 issues

Volume 7, 6 issues

Volume 6, 4 issues

Volume 5, 4 issues

Volume 4, 4 issues

Volume 3, 4 issues

Volume 2, 5 issues

Volume 1, 2 issues

The Journal
About the Journal
Subscriptions
Editorial Board
Editors’ Addresses
Editors’ Interests
Scientific Advantages
Submission Guidelines
Submission Form
Ethics Statement
Editorial Login
Author Index
Coming Soon
Contacts
 
ISSN: 1944-4184 (e-only)
ISSN: 1944-4176 (print)
Induced subgraphs of Johnson graphs

Ramin Naimi and Jeffrey Shaw

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

The Johnson graph J(n,N) is defined as the graph whose vertices are the n-subsets of the set {1,2,,N}, 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(m,2n) for some m 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
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