A New Distance Measure between Graphs

Let \(G_1\) and \(G_2\) be two graphs of the same size such that \(V(G_1) = V(G_2)\), and let \(H\) be a connected graph of order at least \(3\). The graphs \(G_1\) and \(G_2\) are \(H\)-adjacent if \(G_1\) and \(G_2\) contain copies \(H_1\) and \(H_2\) of \(H\), respectively, such that \(H_1\) and \(H_2\) share some but not all edges and \(G_2 = G_1 – E(H_1) + E(H_2)\). The graphs \(G_1\) and \(G_2\) are \(H\)-connected if \(G_1\) can be obtained from \(G_2\) by a sequence of \(H\)-adjacencies. The relation \(H\)-connectedness is an equivalence relation on the set of all graphs of a fixed order and fixed size. The resulting equivalence classes are investigated for various choices of the graph \(H\).