On graph equivalences preserved under extensions

Let GG be the set of finite graphs whose vertices belong to some fixed countable set, and let ≡≡ be an equivalence relation on GG. By the strengthening   of ≡≡ we mean an equivalence relation ≡s≡s such that G≡sHG≡sH, where G,H∈GG,H∈G, if for every F∈GF∈G, G∪F≡H∪FG∪F≡H∪F. The most important case that we study in this paper concerns equivalence relations defined by graph properties. We write G≡ΦHG≡ΦH, where ΦΦ is a graph property and G,H∈GG,H∈G, if either both GG and HH have the property ΦΦ, or both do not have it. We characterize the strengthening of the relations ≡Φ≡Φ for several graph properties ΦΦ. For example, if ΦΦ is the property of being a kk-connected graph, we find a polynomially verifiable (for kk fixed) condition that characterizes the pairs of graphs equivalent with respect to ≡sΦ. We obtain similar results when ΦΦ is the property of being kk-colorable, edge 22-colorable, Hamiltonian, or planar, and when ΦΦ is the property of containing a subgraph isomorphic to a fixed graph HH. We also prove several general theorems that provide conditions for ≡s≡s to be of some specific form. For example, we find a necessary and sufficient condition for the relation ≡s≡s to be the identity. Finally, we make a few observations on the strengthening in a more general case when GG is the set of finite subsets of some countable set.