<p>Let <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(G=(V,E)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>=</mo> <mo stretchy="false">(</mo> <mi>V</mi> <mo>,</mo> <mi>E</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> be a simple graph of size <i>m</i> and <i>L</i> a set of <i>m</i> distinct real numbers. An <i>L</i>-<i>labeling</i> of <i>G</i> is a bijection <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\phi : E \rightarrow L\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ϕ</mi> <mo>:</mo> <mi>E</mi> <mo stretchy="false">→</mo> <mi>L</mi> </mrow> </math></EquationSource> </InlineEquation>. We say that <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\phi \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ϕ</mi> </math></EquationSource> </InlineEquation> is an <i>antimagic </i><i>L</i><i>-labeling</i> if the induced <i>vertex sum</i> <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\phi _+: V \rightarrow {\mathbb {R}}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>ϕ</mi> <mo>+</mo> </msub> <mo>:</mo> <mi>V</mi> <mo stretchy="false">→</mo> <mi mathvariant="double-struck">R</mi> </mrow> </math></EquationSource> </InlineEquation> defined as <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(\phi _+(u)=\sum _{uv\in E}\phi (uv)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>ϕ</mi> <mo>+</mo> </msub> <mrow> <mo stretchy="false">(</mo> <mi>u</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <msub> <mo>∑</mo> <mrow> <mi>u</mi> <mi>v</mi> <mo>∈</mo> <mi>E</mi> </mrow> </msub> <mi>ϕ</mi> <mrow> <mo stretchy="false">(</mo> <mi>u</mi> <mi>v</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is injective. Similarly, <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\phi \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ϕ</mi> </math></EquationSource> </InlineEquation> is a <i>product antimagic L-labeling</i> of <i>G</i> if the induced <i>vertex product</i> <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\phi _{\circ }: V \rightarrow {\mathbb {R}}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>ϕ</mi> <mo>∘</mo> </msub> <mo>:</mo> <mi>V</mi> <mo stretchy="false">→</mo> <mi mathvariant="double-struck">R</mi> </mrow> </math></EquationSource> </InlineEquation> defined as <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(\phi _{\circ }(u)=\prod _{uv\in E}\phi (uv)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>ϕ</mi> <mo>∘</mo> </msub> <mrow> <mo stretchy="false">(</mo> <mi>u</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <msub> <mo>∏</mo> <mrow> <mi>u</mi> <mi>v</mi> <mo>∈</mo> <mi>E</mi> </mrow> </msub> <mi>ϕ</mi> <mrow> <mo stretchy="false">(</mo> <mi>u</mi> <mi>v</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is injective. A graph <i>G</i> is <i>antimagic</i> (resp. <i>product antimagic</i>) if it has an antimagic (resp. a product antimagic) <i>L</i>-labeling for <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(L=\{1,2,\dots ,m\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>L</mi> <mo>=</mo> <mo stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <mi>m</mi> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>. Hartsfield and Ringel conjectured that every simple connected graph distinct from <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(K_2\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation> is antimagic, but the conjecture remains widely open. We prove, among other results, that every connected graph of size <i>m</i>, <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(m \ge 3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>m</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>, admits an antimagic <i>L</i>-labeling for every arithmetic sequence <i>L</i> of <i>m</i> positive real numbers, if every vertex of degree at least three is a support vertex. As a corollary, we derive that these graphs are antimagic, reinforcing the veracity of the conjecture by Hartsfield and Ringel. Moreover, these graphs admit also a product antimagic <i>L</i>-labeling provided that the smallest element of <i>L</i> is at least one. The proof is constructive.</p>

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

Antimagic and Product Antimagic Graphs with Pendant Edges

  • Mercè Mora,
  • Joaquín Tey

摘要

Let \(G=(V,E)\) G = ( V , E ) be a simple graph of size m and L a set of m distinct real numbers. An L-labeling of G is a bijection \(\phi : E \rightarrow L\) ϕ : E L . We say that \(\phi \) ϕ is an antimagic L-labeling if the induced vertex sum \(\phi _+: V \rightarrow {\mathbb {R}}\) ϕ + : V R defined as \(\phi _+(u)=\sum _{uv\in E}\phi (uv)\) ϕ + ( u ) = u v E ϕ ( u v ) is injective. Similarly, \(\phi \) ϕ is a product antimagic L-labeling of G if the induced vertex product \(\phi _{\circ }: V \rightarrow {\mathbb {R}}\) ϕ : V R defined as \(\phi _{\circ }(u)=\prod _{uv\in E}\phi (uv)\) ϕ ( u ) = u v E ϕ ( u v ) is injective. A graph G is antimagic (resp. product antimagic) if it has an antimagic (resp. a product antimagic) L-labeling for \(L=\{1,2,\dots ,m\}\) L = { 1 , 2 , , m } . Hartsfield and Ringel conjectured that every simple connected graph distinct from \(K_2\) K 2 is antimagic, but the conjecture remains widely open. We prove, among other results, that every connected graph of size m, \(m \ge 3\) m 3 , admits an antimagic L-labeling for every arithmetic sequence L of m positive real numbers, if every vertex of degree at least three is a support vertex. As a corollary, we derive that these graphs are antimagic, reinforcing the veracity of the conjecture by Hartsfield and Ringel. Moreover, these graphs admit also a product antimagic L-labeling provided that the smallest element of L is at least one. The proof is constructive.