Resumen
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≡sH, 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.
| Idioma original | English |
|---|---|
| Páginas (desde-hasta) | 966-977 |
| Número de páginas | 12 |
| Publicación | Discrete Mathematics |
| Volumen | 311 |
| N.º | 12 |
| DOI | |
| Estado | Published - jun 28 2011 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
Huella
Profundice en los temas de investigación de 'On graph equivalences preserved under extensions'. En conjunto forman una huella única.Citar esto
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver