Switching Distance Graphs

Abstract

Let $S$ be a set of graphs on which a measure of distance (a metric) has been defined. The distance graph $D(S)$ of $S$ is that graph with vertex set $S$ such that two vertices $G$ and $H$ are adjacent if and only if the distance between $G$ and $H$ (according to this metric) is $1$. A basic question is the determination of which graphs are distance graphs. We investigate this question in the case of a metric which we call the switching distance. The question is answered in the affirmative for a number of classes of graphs, including trees and all cycles of length at least $4$. We establish that the union and Cartesian product of two switching distance graphs are switching distance graphs. We show that each of $K_3$, $K_{2,4}$ and $K_{3,3}$ is not a switching distance graph.