Induced Subgraphs of Johnson Graphs

Details Induced Subgraphs of Johnson Graphs Induced Subgraphs of Johnson Graphs

2010-08-03

arxiv.org/abs/1008.0595v1

Mathematics

Combinatorics

13 pages, 4 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Induced Subgraphs of Johnson Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Induced Subgraphs of Johnson Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Induced Subgraphs of Johnson Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-615382