Papers › New recursive constructions of amoebas and their balancing number
New recursive constructions of amoebas and their balancing number
Laura Eslava, Adriana Hansberg, Tonatiuh Matos Wiederhold, Denae Ventura
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.
The definition of amoeba graphs is based on iterative \emph{feasible edge-replacements}, where, at each step, an edge from the graph is removed and placed in an available spot in a way that the resulting graph is isomorphic to the original graph. Broadly speaking, amoebas are graphs that, by means of a chain of feasible edge-replacements, can be transformed into any other copy of itself on a given vertex set (which is defined according to whether these are local or global amoebas). Global amoebas were born as examples of \emph{balanceable} graphs, which are graphs that appear with half of their edges in each color in any 2-edge coloring of a large enough complete graph with a sufficient amount of edges in each color. The least amount of edges required in each color is called the \emph{balancing number} of G. In a work by Caro et al., an infinite family of global amoeba trees with arbitrarily large maximum degree is presented, and the question if they were also local amoebas is raised. In this paper, we provide a recursive construction to generate very diverse infinite families of local and global amoebas, by which not only this question is answered positively, it also yields an efficient algorithm that, given any copy of the graph on the same vertex set, provides a chain of feasible edge-replacements that one can perform in order to move the graph into the aimed copy. All results are illustrated by applying them to three different families of local amoebas, including the Fibonacci-type trees. Concerning the balancing number of a global amoeba G, we are able to express it in terms of the extremal number of a class of subgraphs of G. By means of this, we give a general lower bound for the balancing number of a global amoeba G, and we provide linear (in terms of order) lower and upper bounds for the balancing number of our three case studies.
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