<p>The crossing number <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1868_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">\(\textrm{cr}(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>cr</mtext> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> of a graph <i>G</i> is defined as the smallest number of crossings in any drawing of <i>G</i>. In this paper, we first derive upper and lower bounds on <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1868_Article_IEq6.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="67" /> </InlineMediaObject> <EquationSource Format="TEX">\(\textrm{cr}(K_{3,3,n})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>cr</mtext> <mo stretchy="false">(</mo> <msub> <mi>K</mi> <mrow> <mn>3</mn> <mo>,</mo> <mn>3</mn> <mo>,</mo> <mi>n</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> for general <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1868_Article_IEq7.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="43" /> </InlineMediaObject> <EquationSource Format="TEX">\(n\ge 1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, and prove that <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1868_Article_IEq8.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="104" /> </InlineMediaObject> <EquationSource Format="TEX">\(\textrm{cr}(K_{3,3,3})=15\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>cr</mtext> <mo stretchy="false">(</mo> <msub> <mi>K</mi> <mrow> <mn>3</mn> <mo>,</mo> <mn>3</mn> <mo>,</mo> <mn>3</mn> </mrow> </msub> <mo stretchy="false">)</mo> <mo>=</mo> <mn>15</mn> </mrow> </math></EquationSource> </InlineEquation>. Next, we introduce a contracting operation on the complete bipartite graph <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1868_Article_IEq9.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="31" /> </InlineMediaObject> <EquationSource Format="TEX">\(K_{3,3}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mrow> <mn>3</mn> <mo>,</mo> <mn>3</mn> </mrow> </msub> </math></EquationSource> </InlineEquation>, which enables us to establish a relationship between the crossing number of the capped Cartesian product <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1868_Article_IEq10.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="66" /> </InlineMediaObject> <EquationSource Format="TEX">\(K_{3,3}\Box _L T\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>K</mi> <mrow> <mn>3</mn> <mo>,</mo> <mn>3</mn> </mrow> </msub> <msub> <mo>□</mo> <mi>L</mi> </msub> <mi>T</mi> </mrow> </math></EquationSource> </InlineEquation> and the Cartesian product <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1868_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="57" /> </InlineMediaObject> <EquationSource Format="TEX">\(K_{3,3}\Box T\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>K</mi> <mrow> <mn>3</mn> <mo>,</mo> <mn>3</mn> </mrow> </msub> <mo>□</mo> <mi>T</mi> </mrow> </math></EquationSource> </InlineEquation> for any tree <i>T</i>. Finally, combining these results with known properties of the zip product, we establish lower bounds on <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1868_Article_IEq12.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="82" /> </InlineMediaObject> <EquationSource Format="TEX">\(\textrm{cr}(K_{3,3}\Box T)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>cr</mtext> <mo stretchy="false">(</mo> <msub> <mi>K</mi> <mrow> <mn>3</mn> <mo>,</mo> <mn>3</mn> </mrow> </msub> <mo>□</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> for any tree <i>T</i> and determine the exact values for subcubic trees.</p>

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

The Crossing Numbers of \(K_{3,3,n}\) and \(K_{3,3}\Box T\)

  • Zhangdong Ouyang

摘要

The crossing number \(\textrm{cr}(G)\) cr ( G ) of a graph G is defined as the smallest number of crossings in any drawing of G. In this paper, we first derive upper and lower bounds on \(\textrm{cr}(K_{3,3,n})\) cr ( K 3 , 3 , n ) for general \(n\ge 1\) n 1 , and prove that \(\textrm{cr}(K_{3,3,3})=15\) cr ( K 3 , 3 , 3 ) = 15 . Next, we introduce a contracting operation on the complete bipartite graph \(K_{3,3}\) K 3 , 3 , which enables us to establish a relationship between the crossing number of the capped Cartesian product \(K_{3,3}\Box _L T\) K 3 , 3 L T and the Cartesian product \(K_{3,3}\Box T\) K 3 , 3 T for any tree T. Finally, combining these results with known properties of the zip product, we establish lower bounds on \(\textrm{cr}(K_{3,3}\Box T)\) cr ( K 3 , 3 T ) for any tree T and determine the exact values for subcubic trees.