×

Induced subgraphs of Johnson graphs. (English) Zbl 1246.05048

Summary: The Johnson graph \(J(n,N)\) is defined as the graph whose vertices are the \(n\)-subsets of the set \(\{1,2,\dots,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 \leq 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.

MSC:

05C12 Distance in graphs
05C62 Graph representations (geometric and intersection representations, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI arXiv Link