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 defined by means of the following operation: Let $G$ be a graph and let $e\in E(G)$ and $e'\in E(\overline{G})$. If the graph $G'=G-e+e'$ is isomorphic to $G$, we say $G'$ is obtained from $G$ by performing a feasible edge-replacement. We call $G$ a local amoeba if, for any two copies $G_1$, $G_2$ of $G$ on the same vertex set, $G_1$ can be transformed into $G_2$ by a chain of feasible edge-replacements. On the other hand, $G$ is called global amoeba if there is an integer $t_0 \ge 0$ such that $G \cup tK_1$ is a local amoeba for all $t \ge t_0$. To model the dynamics of the feasible edge-replacements of $G$, we define a group $\rm{Fer}(G)$ that satisfies that $G$ is a local amoeba if and only if $\rm{Fer}(G) \cong S_n$, 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.
@article{10_37236_11876,
author = {Yair Caro and Adriana Hansberg and Amanda Montejano},
title = {Graphs isomorphisms under edge-replacements and the family of amoebas},
journal = {The electronic journal of combinatorics},
year = {2023},
volume = {30},
number = {3},
doi = {10.37236/11876},
zbl = {1519.05175},
url = {http://geodesic.mathdoc.fr/articles/10.37236/11876/}
}
TY - JOUR
AU - Yair Caro
AU - Adriana Hansberg
AU - Amanda Montejano
TI - Graphs isomorphisms under edge-replacements and the family of amoebas
JO - The electronic journal of combinatorics
PY - 2023
VL - 30
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/11876/
DO - 10.37236/11876
ID - 10_37236_11876
ER -
%0 Journal Article
%A Yair Caro
%A Adriana Hansberg
%A Amanda Montejano
%T Graphs isomorphisms under edge-replacements and the family of amoebas
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/11876/
%R 10.37236/11876
%F 10_37236_11876
Yair Caro; Adriana Hansberg; Amanda Montejano. Graphs isomorphisms under edge-replacements and the family of amoebas. The electronic journal of combinatorics, Tome 30 (2023) no. 3. doi: 10.37236/11876
