Switching Distance Graphs

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.