<p>According to a study by Erdős et al. in 1975, the anti-Ramsey number of a graph <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(G\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>G</mi> </math></EquationSource> </InlineEquation>, denoted as <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(AR(n, G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>A</mi> <mi>R</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, is defined as the maximum number of colors that can be used in an edge-coloring of the complete graph <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(K_n\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mi>n</mi> </msub> </math></EquationSource> </InlineEquation> without creating a rainbow copy of <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(G\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>G</mi> </math></EquationSource> </InlineEquation>. In this paper, we investigate the anti-Ramsey number under edge deletion and demonstrate that both decreasing and unchanging are possible outcomes. For three non-negative integers <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(k\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>k</mi> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(t\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>t</mi> </math></EquationSource> </InlineEquation>, and <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(n\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>n</mi> </math></EquationSource> </InlineEquation>, let <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(G = kP_4 \cup tP_2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>=</mo> <mi>k</mi> <msub> <mi>P</mi> <mn>4</mn> </msub> <mo>∪</mo> <mi>t</mi> <msub> <mi>P</mi> <mn>2</mn> </msub> </mrow> </math></EquationSource> </InlineEquation>. Let <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(E'\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>E</mi> <mo>′</mo> </msup> </math></EquationSource> </InlineEquation> be a subset of the edge set <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(E(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>E</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> such that every endpoint of these edges has a degree of two in <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(G\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>G</mi> </math></EquationSource> </InlineEquation>. We prove that if one of the conditions (i) <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(t \ge k + 1 \ge 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>≥</mo> <mi>k</mi> <mo>+</mo> <mn>1</mn> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(n \ge 8k + 2t - 4\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>8</mn> <mi>k</mi> <mo>+</mo> <mn>2</mn> <mi>t</mi> <mo>-</mo> <mn>4</mn> </mrow> </math></EquationSource> </InlineEquation>; (ii) <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(k, t \ge 1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>,</mo> <mi>t</mi> <mo>≥</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq15"> <EquationSource Format="TEX">\(n = 4k + 2t\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>=</mo> <mn>4</mn> <mi>k</mi> <mo>+</mo> <mn>2</mn> <mi>t</mi> </mrow> </math></EquationSource> </InlineEquation>; (iii) <InlineEquation ID="IEq16"> <EquationSource Format="TEX">\(k = 1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>=</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq17"> <EquationSource Format="TEX">\(t \ge 1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>≥</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, and <InlineEquation ID="IEq18"> <EquationSource Format="TEX">\(n \ge 2t + 4\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>2</mn> <mi>t</mi> <mo>+</mo> <mn>4</mn> </mrow> </math></EquationSource> </InlineEquation>, occurs then the behavior of the anti-Ramsey number remains consistent when the edges in <InlineEquation ID="IEq19"> <EquationSource Format="TEX">\(E'\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>E</mi> <mo>′</mo> </msup> </math></EquationSource> </InlineEquation> are removed from <InlineEquation ID="IEq20"> <EquationSource Format="TEX">\(G\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>G</mi> </math></EquationSource> </InlineEquation>, i.e., <InlineEquation ID="IEq21"> <EquationSource Format="TEX">\(AR(n, G) = AR(n, G - E')\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>A</mi> <mi>R</mi> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mi>A</mi> <mi>R</mi> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>G</mi> <mo>-</mo> <msup> <mi>E</mi> <mo>′</mo> </msup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. However, this is not the case when <InlineEquation ID="IEq22"> <EquationSource Format="TEX">\(k \ge 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq23"> <EquationSource Format="TEX">\(t = 0\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>=</mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation>, and <InlineEquation ID="IEq24"> <EquationSource Format="TEX">\(n=4k\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>=</mo> <mn>4</mn> <mi>k</mi> </mrow> </math></EquationSource> </InlineEquation>. As a result, we calculate <InlineEquation ID="IEq25"> <EquationSource Format="TEX">\(AR(n,kP_4 \cup tP_2)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>A</mi> <mi>R</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>k</mi> <msub> <mi>P</mi> <mn>4</mn> </msub> <mo>∪</mo> <mi>t</mi> <msub> <mi>P</mi> <mn>2</mn> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> for the cases: (i) <InlineEquation ID="IEq26"> <EquationSource Format="TEX">\(t \ge k + 1 \ge 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>≥</mo> <mi>k</mi> <mo>+</mo> <mn>1</mn> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq27"> <EquationSource Format="TEX">\(n \ge 8k + 2t - 4\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>8</mn> <mi>k</mi> <mo>+</mo> <mn>2</mn> <mi>t</mi> <mo>-</mo> <mn>4</mn> </mrow> </math></EquationSource> </InlineEquation>; (ii) <InlineEquation ID="IEq28"> <EquationSource Format="TEX">\(k, t \ge 1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>,</mo> <mi>t</mi> <mo>≥</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq29"> <EquationSource Format="TEX">\(n = 4k + 2t\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>=</mo> <mn>4</mn> <mi>k</mi> <mo>+</mo> <mn>2</mn> <mi>t</mi> </mrow> </math></EquationSource> </InlineEquation>; (iii) <InlineEquation ID="IEq30"> <EquationSource Format="TEX">\(k = 1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>=</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq31"> <EquationSource Format="TEX">\(t \ge 0\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>≥</mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation>, and <InlineEquation ID="IEq32"> <EquationSource Format="TEX">\(n \ge 2t + 4\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>2</mn> <mi>t</mi> <mo>+</mo> <mn>4</mn> </mrow> </math></EquationSource> </InlineEquation>; (iv) <InlineEquation ID="IEq33"> <EquationSource Format="TEX">\(k \ge 1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>≥</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq34"> <EquationSource Format="TEX">\(t = 0\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>=</mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation>, and <InlineEquation ID="IEq35"> <EquationSource Format="TEX">\(n = 4k\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>=</mo> <mn>4</mn> <mi>k</mi> </mrow> </math></EquationSource> </InlineEquation>.</p>

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

On the Anti-Ramsey Number Under Edge Deletion

  • Ali Ghalavand,
  • Qing Jie,
  • Zemin Jin,
  • Xueliang Li,
  • Linshu Pan

摘要

According to a study by Erdős et al. in 1975, the anti-Ramsey number of a graph \(G\) G , denoted as \(AR(n, G)\) A R ( n , G ) , is defined as the maximum number of colors that can be used in an edge-coloring of the complete graph \(K_n\) K n without creating a rainbow copy of \(G\) G . In this paper, we investigate the anti-Ramsey number under edge deletion and demonstrate that both decreasing and unchanging are possible outcomes. For three non-negative integers \(k\) k , \(t\) t , and \(n\) n , let \(G = kP_4 \cup tP_2\) G = k P 4 t P 2 . Let \(E'\) E be a subset of the edge set \(E(G)\) E ( G ) such that every endpoint of these edges has a degree of two in \(G\) G . We prove that if one of the conditions (i) \(t \ge k + 1 \ge 2\) t k + 1 2 and \(n \ge 8k + 2t - 4\) n 8 k + 2 t - 4 ; (ii) \(k, t \ge 1\) k , t 1 and \(n = 4k + 2t\) n = 4 k + 2 t ; (iii) \(k = 1\) k = 1 , \(t \ge 1\) t 1 , and \(n \ge 2t + 4\) n 2 t + 4 , occurs then the behavior of the anti-Ramsey number remains consistent when the edges in \(E'\) E are removed from \(G\) G , i.e., \(AR(n, G) = AR(n, G - E')\) A R ( n , G ) = A R ( n , G - E ) . However, this is not the case when \(k \ge 2\) k 2 , \(t = 0\) t = 0 , and \(n=4k\) n = 4 k . As a result, we calculate \(AR(n,kP_4 \cup tP_2)\) A R ( n , k P 4 t P 2 ) for the cases: (i) \(t \ge k + 1 \ge 2\) t k + 1 2 and \(n \ge 8k + 2t - 4\) n 8 k + 2 t - 4 ; (ii) \(k, t \ge 1\) k , t 1 and \(n = 4k + 2t\) n = 4 k + 2 t ; (iii) \(k = 1\) k = 1 , \(t \ge 0\) t 0 , and \(n \ge 2t + 4\) n 2 t + 4 ; (iv) \(k \ge 1\) k 1 , \(t = 0\) t = 0 , and \(n = 4k\) n = 4 k .