Another Antimagic Conjecture
An antimagic labeling of a graph <i>G</i> is a bijection <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>f</mi><mo>:</mo><mi>E</mi><mo stretchy="...
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | article |
| Lenguaje: | EN |
| Publicado: |
MDPI AG
2021
|
| Materias: | |
| Acceso en línea: | https://doaj.org/article/fe2912b6e6bc4431a5b5750faee174b3 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| Sumario: | An antimagic labeling of a graph <i>G</i> is a bijection <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>f</mi><mo>:</mo><mi>E</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo><mo>→</mo><mo>{</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mo>|</mo><mi>E</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo><mo>|</mo><mo>}</mo></mrow></semantics></math></inline-formula> such that the weights <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>w</mi><mrow><mo stretchy="false">(</mo><mi>x</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><msub><mo>∑</mo><mrow><mi>y</mi><mo>∼</mo><mi>x</mi></mrow></msub><mi>f</mi><mrow><mo stretchy="false">(</mo><mi>y</mi><mo stretchy="false">)</mo></mrow></mrow></semantics></math></inline-formula> distinguish all vertices. A well-known conjecture of Hartsfield and Ringel (1990) is that every connected graph other than <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>K</mi><mn>2</mn></msub></semantics></math></inline-formula> admits an antimagic labeling. For a set of distances <i>D</i>, a <i>D</i>-antimagic labeling of a graph <i>G</i> is a bijection <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>f</mi><mo>:</mo><mi>V</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo><mo>→</mo><mo>{</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mo>|</mo><mi>V</mi><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo><mo>|</mo><mo>}</mo></mrow></semantics></math></inline-formula> such that the <i>weight</i><inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>ω</mi><mrow><mo stretchy="false">(</mo><mi>x</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><msub><mo>∑</mo><mrow><mi>y</mi><mo>∈</mo><msub><mi>N</mi><mi>D</mi></msub><mrow><mo stretchy="false">(</mo><mi>x</mi><mo stretchy="false">)</mo></mrow></mrow></msub><mi>f</mi><mrow><mo stretchy="false">(</mo><mi>y</mi><mo stretchy="false">)</mo></mrow></mrow></semantics></math></inline-formula> is distinct for each vertex <i>x</i>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>N</mi><mi>D</mi></msub><mrow><mo stretchy="false">(</mo><mi>x</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mrow><mo>{</mo><mi>y</mi><mo>∈</mo><mi>V</mi><mrow><mo stretchy="false">(</mo><mi>G</mi><mo stretchy="false">)</mo></mrow><mo>|</mo><mi>d</mi><mrow><mo stretchy="false">(</mo><mi>x</mi><mo>,</mo><mi>y</mi><mo stretchy="false">)</mo></mrow><mo>∈</mo><mi>D</mi><mo>}</mo></mrow></mrow></semantics></math></inline-formula> is the <i>D</i>-neigbourhood set of a vertex <i>x</i>. If <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>N</mi><mi>D</mi></msub><mrow><mo stretchy="false">(</mo><mi>x</mi><mo stretchy="false">)</mo></mrow><mo>=</mo><mi>r</mi></mrow></semantics></math></inline-formula>, for every vertex <i>x</i> in <i>G</i>, a graph <i>G</i> is said to be <i><inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo stretchy="false">(</mo><mi>D</mi><mo>,</mo><mi>r</mi><mo stretchy="false">)</mo></mrow></semantics></math></inline-formula>-regular</i>. In this paper, we conjecture that a graph admits a <i>D</i>-antimagic labeling if and only if it does not contain two vertices having the same <i>D</i>-neighborhood set. We also provide evidence that the conjecture is true. We present computational results that, for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>D</mi><mo>=</mo><mo>{</mo><mn>1</mn><mo>}</mo></mrow></semantics></math></inline-formula>, all graphs of order up to 8 concur with the conjecture. We prove that the set of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo stretchy="false">(</mo><mi>D</mi><mo>,</mo><mi>r</mi><mo stretchy="false">)</mo></mrow></semantics></math></inline-formula>-regular <i>D</i>-antimagic graphs is closed under union. We provide examples of disjoint union of symmetric <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo stretchy="false">(</mo><mi>D</mi><mo>,</mo><mi>r</mi><mo stretchy="false">)</mo></mrow></semantics></math></inline-formula>-regular that are <i>D</i>-antimagic and examples of disjoint union of non-symmetric non-<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo stretchy="false">(</mo><mi>D</mi><mo>,</mo><mi>r</mi><mo stretchy="false">)</mo></mrow></semantics></math></inline-formula>-regular graphs that are <i>D</i>-antimagic. Furthermore, lastly, we show that it is possible to obtain a <i>D</i>-antimagic graph from a previously known distance antimagic graph. |
|---|