Papers › Graphs isomorphisms under edge-replacements and the family of amoebas
Graphs isomorphisms under edge-replacements and the family of amoebas
Yair Caro, Adriana Hansberg, Amanda Montejano
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
This paper offers a systematic study of a family of graphs called amoebas. Amoebas recently emerged from the study of forced patterns in $2$-colorings of the edges of the complete graph in the context of Ramsey-Turan theory and played an important role in extremal zero-sum problems. Amoebas are graphs with a unique behavior with regards to the following operation: Let G be a graph and let e∈E(G) and e′∈E(G). If the graph G′=G-e+e′ is isomorphic to G, we say G′ is obtained from G by performing a \emph{feasible edge-replacement}. We call G a \emph{local amoeba} if, for any two copies G₁, G₂ of G on the same vertex set, G₁ can be transformed into G₂ by a chain of feasible edge-replacements. On the other hand, G is called \emph{global amoeba} if there is an integer t₀ ≥0 such that G ∪tK₁ is a local amoeba for all t ≥t₀. To model the dynamics of the feasible edge-replacements of G, we define a group Fer(G) that satisfies that G is a local amoeba if and only if Fer(G) ≅Sₙ, where n is the order of G. Via this algebraic setting, a deeper understanding of the structure of amoebas and their intrinsic properties comes into light. Moreover, we present different constructions that prove the richness of these graph families showing, among other things, that any connected graph can be a connected component of a global amoeba, that global amoebas can be very dense and that they can have, in proportion to their order, large clique and chromatic numbers. Also, a family of global amoeba trees with a Fibonacci-like structure and with arbitrary large maximum degree is constructed.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections