Induced subgraphs of Johnson graphs

DOI10.2140/INVOLVE.2012.5.25zbMATH Open1246.05048arXiv1008.0595OpenAlexW3099093673MaRDI QIDQ444598FDOQ444598

Ramin Naimi, Jeffrey Shaw

Publication date: 15 August 2012

Published in: Involve (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1008.0595

Recommendations

• Some results on induced subgraphs of Johnson graphs
• The graph \(\Delta_{2n - 1}\) is an induced subgraph of a Johnson graph
• Distance-preserving subgraphs of Johnson graphs
• The Johnson graphs satisfy a distance extension property
• A problem of Shapozenko on Johnson graphs

zbMATH Keywords

Johnson graphdistance graphinduced subgraphs of Johnson graphsJIS: intersection graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Distance in graphs (05C12) Graph representations (geometric and intersection representations, etc.) (05C62)

Cited In (7)

• Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs
• On the ensemble of optimal identifying codes in a twin-free graph
• On the structure of \(S_2\)-ifications of complete local rings
• On the ensemble of optimal dominating and locating-dominating codes in a graph
• The Johnson graphs satisfy a distance extension property
• Which graphs occur as \(\gamma\)-graphs?
• The graphs G(n,k) of the Johnson schemes are unique for n\(\geq 20\)

This page was built for publication: Induced subgraphs of Johnson graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q444598)