<p>A Hamiltonian path in the complete graph&#xa0;<InlineEquation ID="IEq1"> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mi>v</mi> </msub> </math></EquationSource> <EquationSource Format="TEX">$K_{v}$</EquationSource> </InlineEquation> whose vertices are labeled with the integers&#xa0;<InlineEquation ID="IEq2"> <EquationSource Format="MATHML"><math> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo>,</mo> <mo>…</mo> <mo>,</mo> <mi>v</mi> <mo>−</mo> <mn>1</mn> </math></EquationSource> <EquationSource Format="TEX">$0,1,\ldots ,v-1$</EquationSource> </InlineEquation> is a <i>linear realization</i> for the multiset <InlineEquation ID="IEq3"> <EquationSource Format="MATHML"><math> <mi>L</mi> </math></EquationSource> <EquationSource Format="TEX">$L$</EquationSource> </InlineEquation> of the linear edge-lengths, given by <InlineEquation ID="IEq4"> <EquationSource Format="MATHML"><math> <mo stretchy="false">|</mo> <mi>x</mi> <mo>−</mo> <mi>y</mi> <mo stretchy="false">|</mo> </math></EquationSource> <EquationSource Format="TEX">$|x-y|$</EquationSource> </InlineEquation> for the edge between vertices&#xa0;<InlineEquation ID="IEq5"> <EquationSource Format="MATHML"><math> <mi>x</mi> </math></EquationSource> <EquationSource Format="TEX">$x$</EquationSource> </InlineEquation> and&#xa0;<InlineEquation ID="IEq6"> <EquationSource Format="MATHML"><math> <mi>y</mi> </math></EquationSource> <EquationSource Format="TEX">$y$</EquationSource> </InlineEquation>, of the edges in the path. A linear realization is <i>standard</i> if an end-point is&#xa0;0 and <i>perfect</i> if the end-points are&#xa0;0 and&#xa0;<InlineEquation ID="IEq7"> <EquationSource Format="MATHML"><math> <mi>v</mi> <mo>−</mo> <mn>1</mn> </math></EquationSource> <EquationSource Format="TEX">$v-1$</EquationSource> </InlineEquation>. Linear realizations are useful in the study of the Buratti-Horak-Rosa Conjecture on the existence of <i>cyclic realizations</i>, where cyclic edge-lengths are given by distance modulo <InlineEquation ID="IEq8"> <EquationSource Format="MATHML"><math> <mi>v</mi> </math></EquationSource> <EquationSource Format="TEX">$v$</EquationSource> </InlineEquation>, for given multisets. In this paper, we focus on multisets of the form&#xa0;<InlineEquation ID="IEq9"> <EquationSource Format="MATHML"><math> <mo stretchy="false">{</mo> <msup> <mn>1</mn> <mi>a</mi> </msup> <mo>,</mo> <msup> <mrow> <mo stretchy="false">(</mo> <mi>y</mi> <mo>−</mo> <mi>k</mi> <mo stretchy="false">)</mo> </mrow> <mi>b</mi> </msup> <mo>,</mo> <msup> <mi>y</mi> <mi>c</mi> </msup> <mo stretchy="false">}</mo> </math></EquationSource> <EquationSource Format="TEX">$\{1^{a}, (y-k)^{b}, y^{c}\}$</EquationSource> </InlineEquation>. Using core perfect linear realizations for supports of size 2 (which have the forms <InlineEquation ID="IEq10"> <EquationSource Format="MATHML"><math> <mo stretchy="false">{</mo> <msup> <mi>x</mi> <mrow> <mi>y</mi> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo>,</mo> <msup> <mi>y</mi> <mrow> <mi>x</mi> <mo>+</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">}</mo> </math></EquationSource> <EquationSource Format="TEX">$\{x^{y-1},y^{x+1}\}$</EquationSource> </InlineEquation> whenever&#xa0;<InlineEquation ID="IEq11"> <EquationSource Format="MATHML"><math> <mo movablelimits="false">gcd</mo> <mo stretchy="false">(</mo> <mi>x</mi> <mo>,</mo> <mi>y</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mn>1</mn> </math></EquationSource> <EquationSource Format="TEX">$\gcd (x,y)=1$</EquationSource> </InlineEquation>), we construct standard linear realizations (with&#xa0;<InlineEquation ID="IEq12"> <EquationSource Format="MATHML"><math> <mi>a</mi> <mo>=</mo> <mi>k</mi> <mo>−</mo> <mn>1</mn> </math></EquationSource> <EquationSource Format="TEX">$a=k-1$</EquationSource> </InlineEquation>, <InlineEquation ID="IEq13"> <EquationSource Format="MATHML"><math> <mi>b</mi> <mo>=</mo> <mi>j</mi> <mo stretchy="false">(</mo> <mi>y</mi> <mo>−</mo> <mi>k</mi> <mo stretchy="false">)</mo> </math></EquationSource> <EquationSource Format="TEX">$b=j(y-k)$</EquationSource> </InlineEquation>, <InlineEquation ID="IEq14"> <EquationSource Format="MATHML"><math> <mi>c</mi> <mo>=</mo> <mi>j</mi> <mi>y</mi> </math></EquationSource> <EquationSource Format="TEX">$c=jy$</EquationSource> </InlineEquation>) when&#xa0;<InlineEquation ID="IEq15"> <EquationSource Format="MATHML"><math> <mi>k</mi> <mo stretchy="false">∣</mo> <mi>y</mi> </math></EquationSource> <EquationSource Format="TEX">$k\mid y$</EquationSource> </InlineEquation> or <InlineEquation ID="IEq16"> <EquationSource Format="MATHML"><math> <mi>k</mi> <mo>≤</mo> <mn>4</mn> </math></EquationSource> <EquationSource Format="TEX">$k \leq 4$</EquationSource> </InlineEquation>. When&#xa0;<InlineEquation ID="IEq17"> <EquationSource Format="MATHML"><math> <mi>k</mi> <mo>=</mo> <mn>2</mn> </math></EquationSource> <EquationSource Format="TEX">$k=2$</EquationSource> </InlineEquation>, these allow us to show that there is a linear realization whenever&#xa0;<InlineEquation ID="IEq18"> <EquationSource Format="MATHML"><math> <mi>a</mi> <mo>≥</mo> <mi>y</mi> </math></EquationSource> <EquationSource Format="TEX">$a \geq y$</EquationSource> </InlineEquation>. This is in line with the known results for the case of&#xa0;<InlineEquation ID="IEq19"> <EquationSource Format="MATHML"><math> <mi>k</mi> <mo>=</mo> <mn>1</mn> </math></EquationSource> <EquationSource Format="TEX">$k=1$</EquationSource> </InlineEquation>. We also supplement these results for&#xa0;<InlineEquation ID="IEq20"> <EquationSource Format="MATHML"><math> <mi>k</mi> <mo>=</mo> <mn>1</mn> </math></EquationSource> <EquationSource Format="TEX">$k=1$</EquationSource> </InlineEquation> by constructing linear realizations whenever&#xa0;<InlineEquation ID="IEq21"> <EquationSource Format="MATHML"><math> <mi>b</mi> <mo>+</mo> <mi>c</mi> <mo>&lt;</mo> <mi>y</mi> </math></EquationSource> <EquationSource Format="TEX">$b+c &lt; y$</EquationSource> </InlineEquation> and <InlineEquation ID="IEq22"> <EquationSource Format="MATHML"><math> <mi>a</mi> <mo>≥</mo> <mi>y</mi> <mo>−</mo> <mo movablelimits="false">min</mo> <mo stretchy="false">(</mo> <mi>b</mi> <mo>,</mo> <mi>c</mi> <mo stretchy="false">)</mo> </math></EquationSource> <EquationSource Format="TEX">$a \geq y - \min (b,c)$</EquationSource> </InlineEquation>, from which the coprime version of the conjecture, which requires that&#xa0;<InlineEquation ID="IEq23"> <EquationSource Format="MATHML"><math> <mi>v</mi> </math></EquationSource> <EquationSource Format="TEX">$v$</EquationSource> </InlineEquation> is coprime with each element of the multiset, follows for&#xa0;<InlineEquation ID="IEq24"> <EquationSource Format="MATHML"><math> <mi>k</mi> <mo>=</mo> <mn>1</mn> </math></EquationSource> <EquationSource Format="TEX">$k=1$</EquationSource> </InlineEquation> when&#xa0;<InlineEquation ID="IEq25"> <EquationSource Format="MATHML"><math> <mi>y</mi> <mo>≤</mo> <mn>16</mn> </math></EquationSource> <EquationSource Format="TEX">$y \leq 16$</EquationSource> </InlineEquation>. Our methods show promise for constructing linear realizations for arbitrary <InlineEquation ID="IEq26"> <EquationSource Format="MATHML"><math> <mi>k</mi> </math></EquationSource> <EquationSource Format="TEX">$k$</EquationSource> </InlineEquation>, in the direction of a resolution of the conjecture for supports of size 3.</p>

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

Construction Techniques for Linear Realizations of Multisets with Small Support

  • Onur Ağırseven,
  • M. A. Ollis

摘要

A Hamiltonian path in the complete graph  K v $K_{v}$ whose vertices are labeled with the integers  0 , 1 , , v 1 $0,1,\ldots ,v-1$ is a linear realization for the multiset L $L$ of the linear edge-lengths, given by | x y | $|x-y|$ for the edge between vertices  x $x$ and  y $y$ , of the edges in the path. A linear realization is standard if an end-point is 0 and perfect if the end-points are 0 and  v 1 $v-1$ . Linear realizations are useful in the study of the Buratti-Horak-Rosa Conjecture on the existence of cyclic realizations, where cyclic edge-lengths are given by distance modulo v $v$ , for given multisets. In this paper, we focus on multisets of the form  { 1 a , ( y k ) b , y c } $\{1^{a}, (y-k)^{b}, y^{c}\}$ . Using core perfect linear realizations for supports of size 2 (which have the forms { x y 1 , y x + 1 } $\{x^{y-1},y^{x+1}\}$ whenever  gcd ( x , y ) = 1 $\gcd (x,y)=1$ ), we construct standard linear realizations (with  a = k 1 $a=k-1$ , b = j ( y k ) $b=j(y-k)$ , c = j y $c=jy$ ) when  k y $k\mid y$ or k 4 $k \leq 4$ . When  k = 2 $k=2$ , these allow us to show that there is a linear realization whenever  a y $a \geq y$ . This is in line with the known results for the case of  k = 1 $k=1$ . We also supplement these results for  k = 1 $k=1$ by constructing linear realizations whenever  b + c < y $b+c < y$ and a y min ( b , c ) $a \geq y - \min (b,c)$ , from which the coprime version of the conjecture, which requires that  v $v$ is coprime with each element of the multiset, follows for  k = 1 $k=1$ when  y 16 $y \leq 16$ . Our methods show promise for constructing linear realizations for arbitrary k $k$ , in the direction of a resolution of the conjecture for supports of size 3.