Scholarlink

<p>Amoeba graphs are based on iterative <i>feasible edge-replacements</i>, where, at each step, an edge from the graph is removed and placed in an available spot so 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 (depending on which they are defined as local or global amoebas). Global amoebas were born as examples of <i>balanceable</i> graphs, which 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 <i>k</i> in each color. The minimum value of <i>k</i> is called the <i>balancing number</i> of <i>G</i>. We provide a recursive construction to generate very diverse infinite families of local and global amoebas, which not only answers a question posed by Caro et al. but also yields an efficient algorithm that provides a chain of feasible edge-replacements that one can perform in order to move a local amoeba into an aimed copy in the same vertex set. All results are illustrated by three different families of local amoebas, including the Fibonacci-type trees. We express the balancing number of a global amoeba <i>G</i> in terms of the extremal number of a class of subgraphs of <i>G</i> and give a general lower bound. We provide linear lower and upper bounds for the balancing number of our three case studies.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

New recursive constructions of amoebas and their balancing number

  • 期刊论文

  • 发表日期：

    2025年4月10日

查看全文
  • Laura Eslava,
  • Adriana Hansberg,
  • Tonatiuh Matos-Wiederhold,
  • Denae Ventura

摘要

Amoeba graphs are based on iterative feasible edge-replacements, where, at each step, an edge from the graph is removed and placed in an available spot so 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 (depending on which they are defined as local or global amoebas). Global amoebas were born as examples of balanceable graphs, which 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 k in each color. The minimum value of k is called the balancing number of G. We provide a recursive construction to generate very diverse infinite families of local and global amoebas, which not only answers a question posed by Caro et al. but also yields an efficient algorithm that provides a chain of feasible edge-replacements that one can perform in order to move a local amoeba into an aimed copy in the same vertex set. All results are illustrated by three different families of local amoebas, including the Fibonacci-type trees. We express the balancing number of a global amoeba G in terms of the extremal number of a class of subgraphs of G and give a general lower bound. We provide linear lower and upper bounds for the balancing number of our three case studies.