%0 Journal Article
%T 树的反魔幻标号<br>Anti-Magic Labeling of Trees
%A 许慧敏
%J Pure Mathematics
%P 120-126
%@ 2160-7605
%D 2025
%I Hans Publishing
%R 10.12677/pm.2025.153083
%X 一个简单图<math display='inline' xmlns='http://www.w3.org/1998/Math/MathML'>
 <mrow>
  <mi>G</mi><mo>=</mo><mrow><mo>(</mo>
   <mrow>
    <mi>V</mi><mo>,</mo><mi>E</mi></mrow>
  <mo>)</mo></mrow></mrow>
</math>

的反魔幻标号是一个双射<math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mrow>
  <mi>f</mi><mo>:</mo><mi>E</mi><mo>&#x2192;</mo><mrow><mo>{</mo> <mrow>
   <mn>1</mn><mo>,</mo><mn>2</mn><mo>,</mo><mo>&#x22EF;</mo><mo>,</mo><mrow><mo>|</mo> <mi>E</mi> <mo>|</mo></mrow></mrow> <mo>}</mo></mrow></mrow>
</math>

&#65292;使得任意顶点所关联的边的标号之和互不相同。如果一个图存在魔幻标号&#65292;则称其为反魔幻图。Hartsfield和Ringel猜想除<math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mrow>
  <msub>
   <mi>K</mi>
   <mn>2</mn>
  </msub>
  </mrow>
</math>

以外的所有树图都是反魔幻的。令<i>T</i>是一个非<math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mrow>
  <msub>
   <mi>K</mi>
   <mn>2</mn>
  </msub>
  </mrow>
</math>

的树图&#65292;<math display='inline' xmlns='http://www.w3.org/1998/Math/MathML'>
 <mrow>
  <msub>
   <mi>V</mi>
   <mn>2</mn>
  </msub>
  <mrow><mo>(</mo>
   <mi>T</mi>
  <mo>)</mo></mrow></mrow>
</math>

是<i>T</i>中所有顶点度为2的顶点集合。Liang&#65292;Wong和Zhu证明了若由<math display='inline' xmlns='http://www.w3.org/1998/Math/MathML'>
 <mrow>
  <msub>
   <mi>V</mi>
   <mn>2</mn>
  </msub>
  <mrow><mo>(</mo>
   <mi>T</mi>
  <mo>)</mo></mrow></mrow>
</math>

所得的诱导子图是一条路径<i>P</i>&#65292;且<i>T</i>中所有不属于<math display='inline' xmlns='http://www.w3.org/1998/Math/MathML'>
 <mrow>
  <msub>
   <mi>V</mi>
   <mn>2</mn>
  </msub>
  <mrow><mo>(</mo>
   <mi>T</mi>
  <mo>)</mo></mrow></mrow>
</math>

里的顶点的度均为奇数&#65292;则<i>T</i>是反魔幻图。令<math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mrow>
  <msub>
   <mi>v</mi>
   <mi>s</mi>
  </msub>
  </mrow>
</math>

是路径<i>P</i>的中间点&#65292;且<i>v</i>是不属于<i>T</i>的一个新的顶点。设<i>T'</i>是通过连接<math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mrow>
  <msub>
   <mi>v</mi>
   <mi>s</mi>
  </msub>
  </mrow>
</math>

和<i>v</i>由<i>T</i>所构造的新树。本文证明了<i>T'</i>仍保持反魔幻性。<br>Let <math display='inline' xmlns='http://www.w3.org/1998/Math/MathML'>
 <mrow>
  <mi>G</mi><mo>=</mo><mrow><mo>(</mo>
   <mrow>
    <mi>V</mi><mo>,</mo><mi>E</mi></mrow>
  <mo>)</mo></mrow></mrow>
</math>

 be a simple graph. A bijection <math xmlns='http://www.w3.org/1998/Math/MathML'>
 <mrow>
  <mi>f</mi><mo>:</mo><mi>E</mi><mo>&#x2192;</mo><mrow><mo>{</mo> <mrow>
   <mn>1</mn><mo>,</mo><mn>2</mn><mo>,</mo><mo>&#x22EF;</mo><mo>,</mo><mrow><mo>|</mo> <mi>E</mi> <mo>|</mo></mrow></mrow> <mo>}</mo></mrow></mrow>
</math>

 is called anti-magic if the sum of labels of the edges incident to any vertex is distinct. A graph is called anti-magic if there exists
%K 边标号&#65292
%K 反魔幻标号&#65292
%K 树<br>Edge Labeling
%K Anti-Magic Labeling
%K Tree
%U http://www.hanspub.org/journal/PaperInformation.aspx?PaperID=109264