On Induced Subgraphs of Johnson Graphs and Move, Rotation, and Jump Graphs

Abstract

A graph is a set of vertices (points) and edges (lines) connecting some of the vertices to each other. We study how different two graphs are by measuring various "distances" between them, e.g., the number of edges that must be added and removed to transform one graph into another. We also construct counterexamples to two conjectures in this field, dating back to 1990 and 1997.