<p>The spectral extremal problem of planar graphs has received increasing attention in the past several decades. Boots and Royle (Geogr Anal 23(3):276–282, 1991) and Cao and Vince (Linear Algebra Appl 187:251–257, 1993 independently) conjectured that <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3384_Article_IEq1.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="75" /> </InlineMediaObject> <EquationSource Format="TEX">\(K_2 + P_{n-2}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>K</mi> <mn>2</mn> </msub> <mo>+</mo> <msub> <mi>P</mi> <mrow> <mi>n</mi> <mo>-</mo> <mn>2</mn> </mrow> </msub> </mrow> </math></EquationSource> </InlineEquation> is the unique graph attaining the maximum spectral radius among all planar graphs on <i>n</i> vertices, where <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3384_Article_IEq1.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="75" /> </InlineMediaObject> <EquationSource Format="TEX">\(K_2 + P_{n-2}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>K</mi> <mn>2</mn> </msub> <mo>+</mo> <msub> <mi>P</mi> <mrow> <mi>n</mi> <mo>-</mo> <mn>2</mn> </mrow> </msub> </mrow> </math></EquationSource> </InlineEquation> is the graph obtained from <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3384_Article_IEq3.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="75" /> </InlineMediaObject> <EquationSource Format="TEX">\(K_2\cup P_{n-2}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>K</mi> <mn>2</mn> </msub> <mo>∪</mo> <msub> <mi>P</mi> <mrow> <mi>n</mi> <mo>-</mo> <mn>2</mn> </mrow> </msub> </mrow> </math></EquationSource> </InlineEquation> by adding all possible edges between <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3384_Article_IEq4.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="TEX">\(K_2\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3384_Article_IEq5.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="35" /> </InlineMediaObject> <EquationSource Format="TEX">\(P_{n-2}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mrow> <mi>n</mi> <mo>-</mo> <mn>2</mn> </mrow> </msub> </math></EquationSource> </InlineEquation>. Tait and Tobin (J Combin Theory Ser B 126:37–161, 2017) confirmed this conjecture for all sufficiently large <i>n</i>. In this paper, we consider the spectral extremal problem for planar graphs without specified subgraphs. For a fixed graph <i>F</i>, let <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3384_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="98" /> </InlineMediaObject> <EquationSource Format="TEX">\(\textrm{SPEX}_{{\mathcal {P}}}(n,F)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mtext>SPEX</mtext> <mi mathvariant="script">P</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>F</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> denote the set of graphs attaining the maximum spectral radius among all <i>F</i>-free planar graphs on <i>n</i> vertices. We describe a rough structure of the connected extremal graphs in <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3384_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="98" /> </InlineMediaObject> <EquationSource Format="TEX">\(\textrm{SPEX}_{{\mathcal {P}}}(n,F)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mtext>SPEX</mtext> <mi mathvariant="script">P</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <mi>F</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> when <i>F</i> is a planar graph not contained in <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3384_Article_IEq8.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="47" /> </InlineMediaObject> <EquationSource Format="TEX">\(K_{2,n-2}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mrow> <mn>2</mn> <mo>,</mo> <mi>n</mi> <mo>-</mo> <mn>2</mn> </mrow> </msub> </math></EquationSource> </InlineEquation>. As applications, we determine the extremal graphs in <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3384_Article_IEq9.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="107" /> </InlineMediaObject> <EquationSource Format="TEX">\(\textrm{SPEX}_{{\mathcal {P}}}(n,W_k)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mtext>SPEX</mtext> <mi mathvariant="script">P</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <msub> <mi>W</mi> <mi>k</mi> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3384_Article_IEq10.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="102" /> </InlineMediaObject> <EquationSource Format="TEX">\(\textrm{SPEX}_{{\mathcal {P}}}(n,F_k)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mtext>SPEX</mtext> <mi mathvariant="script">P</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <msub> <mi>F</mi> <mi>k</mi> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3384_Article_IEq11.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="123" /> </InlineMediaObject> <EquationSource Format="TEX">\(\textrm{SPEX}_{{\mathcal {P}}}(n,M_{k+1})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mtext>SPEX</mtext> <mi mathvariant="script">P</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>,</mo> <msub> <mi>M</mi> <mrow> <mi>k</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> for all sufficiently large <i>n</i>, where <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3384_Article_IEq12.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="26" /> </InlineMediaObject> <EquationSource Format="TEX">\(W_k\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>W</mi> <mi>k</mi> </msub> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq13"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3384_Article_IEq13.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">\(F_k\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>F</mi> <mi>k</mi> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq14"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3384_Article_IEq14.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="39" /> </InlineMediaObject> <EquationSource Format="TEX">\(M_{k+1}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>M</mi> <mrow> <mi>k</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> </math></EquationSource> </InlineEquation> are the wheel graph of order <i>k</i>, the friendship graph of order <InlineEquation ID="IEq15"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3384_Article_IEq15.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="47" /> </InlineMediaObject> <EquationSource Format="TEX">\(2k+1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mi>k</mi> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> and the <InlineEquation ID="IEq16"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3384_Article_IEq16.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="51" /> </InlineMediaObject> <EquationSource Format="TEX">\((k+1)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>k</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-matching of order <InlineEquation ID="IEq17"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3384_Article_IEq17.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="47" /> </InlineMediaObject> <EquationSource Format="TEX">\(2k+2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> <mi>k</mi> <mo>+</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, respectively.</p>

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

On the spectral extremal problem of planar graphs

  • Xiaolong Wang,
  • Xueyi Huang,
  • Huiqiu Lin

摘要

The spectral extremal problem of planar graphs has received increasing attention in the past several decades. Boots and Royle (Geogr Anal 23(3):276–282, 1991) and Cao and Vince (Linear Algebra Appl 187:251–257, 1993 independently) conjectured that \(K_2 + P_{n-2}\) K 2 + P n - 2 is the unique graph attaining the maximum spectral radius among all planar graphs on n vertices, where \(K_2 + P_{n-2}\) K 2 + P n - 2 is the graph obtained from \(K_2\cup P_{n-2}\) K 2 P n - 2 by adding all possible edges between \(K_2\) K 2 and \(P_{n-2}\) P n - 2 . Tait and Tobin (J Combin Theory Ser B 126:37–161, 2017) confirmed this conjecture for all sufficiently large n. In this paper, we consider the spectral extremal problem for planar graphs without specified subgraphs. For a fixed graph F, let \(\textrm{SPEX}_{{\mathcal {P}}}(n,F)\) SPEX P ( n , F ) denote the set of graphs attaining the maximum spectral radius among all F-free planar graphs on n vertices. We describe a rough structure of the connected extremal graphs in \(\textrm{SPEX}_{{\mathcal {P}}}(n,F)\) SPEX P ( n , F ) when F is a planar graph not contained in \(K_{2,n-2}\) K 2 , n - 2 . As applications, we determine the extremal graphs in \(\textrm{SPEX}_{{\mathcal {P}}}(n,W_k)\) SPEX P ( n , W k ) , \(\textrm{SPEX}_{{\mathcal {P}}}(n,F_k)\) SPEX P ( n , F k ) and \(\textrm{SPEX}_{{\mathcal {P}}}(n,M_{k+1})\) SPEX P ( n , M k + 1 ) for all sufficiently large n, where \(W_k\) W k , \(F_k\) F k and \(M_{k+1}\) M k + 1 are the wheel graph of order k, the friendship graph of order \(2k+1\) 2 k + 1 and the \((k+1)\) ( k + 1 ) -matching of order \(2k+2\) 2 k + 2 , respectively.