<p>The supereulerian width of a graph <i>G</i>, denoted <i>sw</i>(<i>G</i>), is the largest integer <i>s</i> such that for any integer <i>k</i> with <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2024_1810_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="75" /> </InlineMediaObject> <EquationSource Format="TEX">\(0 \le k \le s\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>0</mn> <mo>≤</mo> <mi>k</mi> <mo>≤</mo> <mi>s</mi> </mrow> </math></EquationSource> </InlineEquation>, and for any distinct vertices <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2024_1810_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="88" /> </InlineMediaObject> <EquationSource Format="TEX">\(u, v \in V(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>u</mi> <mo>,</mo> <mi>v</mi> <mo>∈</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, <i>G</i> has a spanning subgraph <i>H</i> consisting of <i>k</i>-edge-disjoint (<i>u</i>,&#xa0;<i>v</i>)-trails. It is known that for any graph <i>G</i>, <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2024_1810_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="110" /> </InlineMediaObject> <EquationSource Format="TEX">\(\kappa '(G) \ge sw(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>κ</mi> <mo>′</mo> </msup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>≥</mo> <mi>s</mi> <mi>w</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>. As deciding if <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2024_1810_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="79" /> </InlineMediaObject> <EquationSource Format="TEX">\(sw(G) \ge 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>s</mi> <mi>w</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> is NP-complete, Li et al. in 2016 posed an open problem asking to determine <i>sw</i>(<i>G</i>) when <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2024_1810_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">\(\kappa '(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>κ</mi> <mo>′</mo> </msup> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is given. Former results in 1988 of Catlin on supereulerian graphs and in 2009 of Lai et al. imply that every 4-edge-connected graph <i>G</i> satisfies <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2024_1810_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="79" /> </InlineMediaObject> <EquationSource Format="TEX">\(sw(G) \ge 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>s</mi> <mi>w</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>. We proved that every 4-edge-connected graph with diameter at most 4 satisfies <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2024_1810_Article_IEq7.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="79" /> </InlineMediaObject> <EquationSource Format="TEX">\(sw(G) \ge 3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>s</mi> <mi>w</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>; and every 3-edge-connected claw-free graph with diameter at most 3 satisfies <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2024_1810_Article_IEq8.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="79" /> </InlineMediaObject> <EquationSource Format="TEX">\(sw(G) \ge 3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>s</mi> <mi>w</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>.</p>

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

Graphs with Supereulerian Width 3 and Small Diameters

  • Wei Xiong,
  • Xing Chen,
  • Yang Wu,
  • Mingquan Zhan,
  • Hong-Jian Lai

摘要

The supereulerian width of a graph G, denoted sw(G), is the largest integer s such that for any integer k with \(0 \le k \le s\) 0 k s , and for any distinct vertices \(u, v \in V(G)\) u , v V ( G ) , G has a spanning subgraph H consisting of k-edge-disjoint (uv)-trails. It is known that for any graph G, \(\kappa '(G) \ge sw(G)\) κ ( G ) s w ( G ) . As deciding if \(sw(G) \ge 2\) s w ( G ) 2 is NP-complete, Li et al. in 2016 posed an open problem asking to determine sw(G) when \(\kappa '(G)\) κ ( G ) is given. Former results in 1988 of Catlin on supereulerian graphs and in 2009 of Lai et al. imply that every 4-edge-connected graph G satisfies \(sw(G) \ge 2\) s w ( G ) 2 . We proved that every 4-edge-connected graph with diameter at most 4 satisfies \(sw(G) \ge 3\) s w ( G ) 3 ; and every 3-edge-connected claw-free graph with diameter at most 3 satisfies \(sw(G) \ge 3\) s w ( G ) 3 .