<p>For an integer <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10801_2025_1458_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">\(p\ge 3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>, we study graphs whose adjacency spectral radius satisfies <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10801_2025_1458_Article_IEq2.gif" Format="GIF" Height="24" Rendition="HTML" Resolution="72" Type="Linedraw" Width="135" /> </InlineMediaObject> <EquationSource Format="TEX">\(\rho (G)&lt;\frac{p}{\sqrt{p-1}}=A_p\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ρ</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>&lt;</mo> <mfrac> <mi>p</mi> <msqrt> <mrow> <mi>p</mi> <mo>-</mo> <mn>1</mn> </mrow> </msqrt> </mfrac> <mo>=</mo> <msub> <mi>A</mi> <mi>p</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> or whose signless Laplacian spectral radius satisfies <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10801_2025_1458_Article_IEq3.gif" Format="GIF" Height="29" Rendition="HTML" Resolution="72" Type="Linedraw" Width="125" /> </InlineMediaObject> <EquationSource Format="TEX">\(\kappa (G)&lt;\frac{p^2}{p-1}=Q_p\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>κ</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>&lt;</mo> <mfrac> <msup> <mi>p</mi> <mn>2</mn> </msup> <mrow> <mi>p</mi> <mo>-</mo> <mn>1</mn> </mrow> </mfrac> <mo>=</mo> <msub> <mi>Q</mi> <mi>p</mi> </msub> </mrow> </math></EquationSource> </InlineEquation>. The numbers <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10801_2025_1458_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="22" /> </InlineMediaObject> <EquationSource Format="TEX">\(A_p\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>A</mi> <mi>p</mi> </msub> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10801_2025_1458_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="23" /> </InlineMediaObject> <EquationSource Format="TEX">\(Q_p\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>Q</mi> <mi>p</mi> </msub> </math></EquationSource> </InlineEquation> are known as Hoffman–Smith limit points. For general <i>p</i>, we find upper bounds on the maximum degree of such graphs <i>G</i> and describe the graphs for which the upper bound is achieved with respect to the adjacency matrix. Moreover, we describe forbidden substructures for graphs in these classes. For <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10801_2025_1458_Article_IEq6.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">\(p=4\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo>=</mo> <mn>4</mn> </mrow> </math></EquationSource> </InlineEquation>, we show that the structure of graphs <i>G</i> such that <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10801_2025_1458_Article_IEq7.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="119" /> </InlineMediaObject> <EquationSource Format="TEX">\(A_3&lt;\rho (G)&lt;A_4\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>A</mi> <mn>3</mn> </msub> <mo>&lt;</mo> <mi>ρ</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>&lt;</mo> <msub> <mi>A</mi> <mn>4</mn> </msub> </mrow> </math></EquationSource> </InlineEquation> or <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10801_2025_1458_Article_IEq8.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="122" /> </InlineMediaObject> <EquationSource Format="TEX">\(Q_3&lt;\kappa (G)&lt;Q_4\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>Q</mi> <mn>3</mn> </msub> <mo>&lt;</mo> <mi>κ</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>&lt;</mo> <msub> <mi>Q</mi> <mn>4</mn> </msub> </mrow> </math></EquationSource> </InlineEquation> is much richer than the structure of graphs for which <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10801_2025_1458_Article_IEq9.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="78" /> </InlineMediaObject> <EquationSource Format="TEX">\(\rho (G)&lt;A_3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ρ</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>&lt;</mo> <msub> <mi>A</mi> <mn>3</mn> </msub> </mrow> </math></EquationSource> </InlineEquation> or <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10801_2025_1458_Article_IEq10.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="79" /> </InlineMediaObject> <EquationSource Format="TEX">\(\kappa (G)&lt;Q_3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>κ</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>&lt;</mo> <msub> <mi>Q</mi> <mn>3</mn> </msub> </mrow> </math></EquationSource> </InlineEquation>, whose study has been initiated by Woo and Neumaier (Graphs Combin 23:713–726, 2007).</p>

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

Graphs whose spectral radius is bounded by a fixed Hoffman–Smith limit point

  • Elizandro Max Borba,
  • Rafael Calegari,
  • Carlos Hoppen,
  • Vilmar Trevisan,
  • Bruno Scaratti Veloso

摘要

For an integer \(p\ge 3\) p 3 , we study graphs whose adjacency spectral radius satisfies \(\rho (G)<\frac{p}{\sqrt{p-1}}=A_p\) ρ ( G ) < p p - 1 = A p or whose signless Laplacian spectral radius satisfies \(\kappa (G)<\frac{p^2}{p-1}=Q_p\) κ ( G ) < p 2 p - 1 = Q p . The numbers \(A_p\) A p and \(Q_p\) Q p are known as Hoffman–Smith limit points. For general p, we find upper bounds on the maximum degree of such graphs G and describe the graphs for which the upper bound is achieved with respect to the adjacency matrix. Moreover, we describe forbidden substructures for graphs in these classes. For \(p=4\) p = 4 , we show that the structure of graphs G such that \(A_3<\rho (G)<A_4\) A 3 < ρ ( G ) < A 4 or \(Q_3<\kappa (G)<Q_4\) Q 3 < κ ( G ) < Q 4 is much richer than the structure of graphs for which \(\rho (G)<A_3\) ρ ( G ) < A 3 or \(\kappa (G)<Q_3\) κ ( G ) < Q 3 , whose study has been initiated by Woo and Neumaier (Graphs Combin 23:713–726, 2007).