<p>For a connected graph <i>G</i>, an instance <i>I</i> is a set of pairs of vertices and a corresponding routing <i>R</i> is a set of paths specified for all vertex-pairs in <i>I</i>. Let <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2024_1255_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="23" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathfrak {R}_I\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="fraktur">R</mi> <mi>I</mi> </msub> </math></EquationSource> </InlineEquation> be the collection of all routings with respect to <i>I</i>. The undirected optical index of <i>G</i> with respect to <i>I</i> refers to the minimum integer <i>k</i> to guarantee the existence of a mapping <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2024_1255_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="157" /> </InlineMediaObject> <EquationSource Format="TEX">\(\phi :R\rightarrow \{1,2,\ldots ,k\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ϕ</mi> <mo>:</mo> <mi>R</mi> <mo stretchy="false">→</mo> <mo stretchy="false">{</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mo>…</mo> <mo>,</mo> <mi>k</mi> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>, such that <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2024_1255_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="99" /> </InlineMediaObject> <EquationSource Format="TEX">\(\phi (P)\ne \phi (P')\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ϕ</mi> <mrow> <mo stretchy="false">(</mo> <mi>P</mi> <mo stretchy="false">)</mo> </mrow> <mo>≠</mo> <mi>ϕ</mi> <mrow> <mo stretchy="false">(</mo> <msup> <mi>P</mi> <mo>′</mo> </msup> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> if <i>P</i> and <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2024_1255_Article_IEq4.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="20" /> </InlineMediaObject> <EquationSource Format="TEX">\(P'\)</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>P</mi> <mo>′</mo> </msup> </math></EquationSource> </InlineEquation> have common edge(s), over all routings <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2024_1255_Article_IEq5.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="57" /> </InlineMediaObject> <EquationSource Format="TEX">\(R\in \mathfrak {R}_I\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>R</mi> <mo>∈</mo> <msub> <mi mathvariant="fraktur">R</mi> <mi>I</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>. A natural lower bound of the undirected optical index is the edge-forwarding index, which is defined to be the minimum of the maximum edge-load over all possible routings. Let <i>w</i>(<i>G</i>,&#xa0;<i>I</i>) and <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2024_1255_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="54" /> </InlineMediaObject> <EquationSource Format="TEX">\(\pi (G,I)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>π</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo>,</mo> <mi>I</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> denote the undirected optical index and edge-forwarding index with respect to <i>I</i>, respectively. In this paper, we derive the inequality <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2024_1255_Article_IEq7.gif" Format="GIF" Height="22" Rendition="HTML" Resolution="72" Type="Linedraw" Width="151" /> </InlineMediaObject> <EquationSource Format="TEX">\(w(T,I_A)&lt;\frac{3}{2}\pi (T,I_A)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>w</mi> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo>,</mo> <msub> <mi>I</mi> <mi>A</mi> </msub> <mo stretchy="false">)</mo> </mrow> <mo>&lt;</mo> <mfrac> <mn>3</mn> <mn>2</mn> </mfrac> <mi>π</mi> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo>,</mo> <msub> <mi>I</mi> <mi>A</mi> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for any tree <i>T</i>, where <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2024_1255_Article_IEq8.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="210" /> </InlineMediaObject> <EquationSource Format="TEX">\(I_A:=\{\{x,y\}:\,x,y\in V(T)\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>I</mi> <mi>A</mi> </msub> <mo>:</mo> <mo>=</mo> <mrow> <mo stretchy="false">{</mo> <mrow> <mo stretchy="false">{</mo> <mi>x</mi> <mo>,</mo> <mi>y</mi> <mo stretchy="false">}</mo> </mrow> <mo>:</mo> <mspace width="0.166667em" /> <mi>x</mi> <mo>,</mo> <mi>y</mi> <mo>∈</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">}</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is the all-to-all instance.</p>

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

The undirected optical indices of trees

  • Yuan-Hsun Lo,
  • Hung-Lin Fu,
  • Yijin Zhang,
  • Wing Shing Wong

摘要

For a connected graph G, an instance I is a set of pairs of vertices and a corresponding routing R is a set of paths specified for all vertex-pairs in I. Let \(\mathfrak {R}_I\) R I be the collection of all routings with respect to I. The undirected optical index of G with respect to I refers to the minimum integer k to guarantee the existence of a mapping \(\phi :R\rightarrow \{1,2,\ldots ,k\}\) ϕ : R { 1 , 2 , , k } , such that \(\phi (P)\ne \phi (P')\) ϕ ( P ) ϕ ( P ) if P and \(P'\) P have common edge(s), over all routings \(R\in \mathfrak {R}_I\) R R I . A natural lower bound of the undirected optical index is the edge-forwarding index, which is defined to be the minimum of the maximum edge-load over all possible routings. Let w(GI) and \(\pi (G,I)\) π ( G , I ) denote the undirected optical index and edge-forwarding index with respect to I, respectively. In this paper, we derive the inequality \(w(T,I_A)<\frac{3}{2}\pi (T,I_A)\) w ( T , I A ) < 3 2 π ( T , I A ) for any tree T, where \(I_A:=\{\{x,y\}:\,x,y\in V(T)\}\) I A : = { { x , y } : x , y V ( T ) } is the all-to-all instance.