On graph equivalences preserved under extensions

• Published in: Discrete mathematics 2011-06, Vol.311 (12), p.966-977
• Main Authors: Lonc, Zbigniew, Truszczyński, Mirosław
• Format: Article
• Language: English
• Subjects: Computational complexity; Connectivity; Equivalence; General graph properties; Graphs; Mathematical analysis; Strengthening; Strong equivalence of graphs; Theorems
• ISSN: 0012-365X; 1872-681X
• DOI: 10.1016/j.disc.2011.02.029

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