Nonreversible trees having a removable edge

Abstract

© 2018, University of Nis. All rights reserved. A relational structure is said to be reversible iff every bijective homomorphism (condensation) of that structure is an automorphism. In the case of a binary structure 𝕏 = 〈X, ρ〉, that is equivalent to the following statement: whenever we remove finite or infinite number of edges from 𝕏, thus obtaining the structure 𝕏 ′ , we have that 𝕏 ′ ≇ 𝕏. In this paper, we prove that if a nonreversible tree 𝕏 = 〈X, ρ〉 has a removable edge (i.e. if there is 〈x, y〉 ∈ ρ such that 〈X, ρ〉 ≅ 〈X, ρ \ {〈x, y〉}〉, then it has infinitely many removable edges. We also show that the same is not true for arbitrary binary structure by constructing nonreversible digraphs having exactly n removable edges, for n ∈ ℕ.