<p>The scattering number <i>s</i>(<i>G</i>) (resp. <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2903_Article_IEq1.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="11" /> </InlineMediaObject> <EquationSource Format="TEX">\(\tau \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>τ</mi> </math></EquationSource> </InlineEquation>-toughness) of a graph <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2903_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="81" /> </InlineMediaObject> <EquationSource Format="TEX">\(G=(V,E)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>=</mo> <mo stretchy="false">(</mo> <mi>V</mi> <mo>,</mo> <mi>E</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> is defined as <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2903_Article_IEq3.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="217" /> </InlineMediaObject> <EquationSource Format="TEX">\(s(G)=\max \left\{ c(G-S)-|S|\right\} \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>s</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mo movablelimits="true">max</mo> <mfenced close="}" open="{"> <mi>c</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo>-</mo> <mi>S</mi> <mo stretchy="false">)</mo> <mo>-</mo> <mo stretchy="false">|</mo> <mi>S</mi> <mo stretchy="false">|</mo> </mfenced> </mrow> </math></EquationSource> </InlineEquation> (resp. <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2903_Article_IEq4.gif" Format="GIF" Height="33" Rendition="HTML" Resolution="72" Type="Linedraw" Width="169" /> </InlineMediaObject> <EquationSource Format="TEX">\(\tau (G)=\min \left\{ \frac{\vert S \vert }{c(G-S)-1}\right\} \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>τ</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mo movablelimits="true">min</mo> <mfenced close="}" open="{"> <mfrac> <mrow> <mo stretchy="false">|</mo> <mi>S</mi> <mo stretchy="false">|</mo> </mrow> <mrow> <mi>c</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo>-</mo> <mi>S</mi> <mo stretchy="false">)</mo> <mo>-</mo> <mn>1</mn> </mrow> </mfrac> </mfenced> </mrow> </math></EquationSource> </InlineEquation>), in which the maximum (resp. minimum) is taken over all proper sets <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2903_Article_IEq5.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="75" /> </InlineMediaObject> <EquationSource Format="TEX">\(S\subseteq V(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>S</mi> <mo>⊆</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2903_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="67" /> </InlineMediaObject> <EquationSource Format="TEX">\(c(G-S)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>c</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo>-</mo> <mi>S</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> denotes the number of components of <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2903_Article_IEq7.gif" Format="GIF" Height="15" Rendition="HTML" Resolution="72" Type="Linedraw" Width="49" /> </InlineMediaObject> <EquationSource Format="TEX">\(G-S\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>-</mo> <mi>S</mi> </mrow> </math></EquationSource> </InlineEquation>. These two parameters are known as the variants of the toughness of a graph. In this paper, we study the scattering number and the <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2903_Article_IEq8.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="11" /> </InlineMediaObject> <EquationSource Format="TEX">\(\tau \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>τ</mi> </math></EquationSource> </InlineEquation>-toughness by the eigenvalues of matrices associated with a graph. For the scattering number, we establish a sufficient condition involving the spectral radius for a graph <i>G</i> with minimum degree <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2903_Article_IEq9.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="12" /> </InlineMediaObject> <EquationSource Format="TEX">\(\delta \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>δ</mi> </math></EquationSource> </InlineEquation> such that <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2903_Article_IEq10.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="66" /> </InlineMediaObject> <EquationSource Format="TEX">\(s(G)\le 1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>s</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≤</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, as well as a condition involving Laplacian eigenvalues for a graph with <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2903_Article_IEq11.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="66" /> </InlineMediaObject> <EquationSource Format="TEX">\(s(G)\le 1\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>s</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≤</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>. Additionally, we present a lower bound for <i>s</i>(<i>G</i>) of <i>G</i> in terms of its Laplacian eigenvalues. Our results extend or improve the recent corresponding results. A non-complete graph <i>G</i> is <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2903_Article_IEq12.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="11" /> </InlineMediaObject> <EquationSource Format="TEX">\(\tau \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>τ</mi> </math></EquationSource> </InlineEquation>-tough if <InlineEquation ID="IEq13"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2903_Article_IEq13.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="69" /> </InlineMediaObject> <EquationSource Format="TEX">\(\tau (G)\ge \tau \)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>τ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <mi>τ</mi> </mrow> </math></EquationSource> </InlineEquation>. For <InlineEquation ID="IEq14"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2903_Article_IEq14.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="11" /> </InlineMediaObject> <EquationSource Format="TEX">\(\tau \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>τ</mi> </math></EquationSource> </InlineEquation>-tough graphs, we establish a sufficient condition involving the size (or the signless Laplacian spectral radius) for a graph to be <InlineEquation ID="IEq15"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2903_Article_IEq15.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="11" /> </InlineMediaObject> <EquationSource Format="TEX">\(\tau \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>τ</mi> </math></EquationSource> </InlineEquation>-tough. Furthermore, we present two lower bounds for <InlineEquation ID="IEq16"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="373_2025_2903_Article_IEq16.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="36" /> </InlineMediaObject> <EquationSource Format="TEX">\(\tau (G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>τ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> of <i>G</i> in terms of its Laplacian eigenvalues. As applications, several new results on factors are derived, which improve the related existing results.</p>

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

Two Variants of Toughness of a Graph and its Eigenvalues

  • Hongzhang Chen,
  • Jianxi Li,
  • Shou-Jun Xu

摘要

The scattering number s(G) (resp. \(\tau \) τ -toughness) of a graph \(G=(V,E)\) G = ( V , E ) is defined as \(s(G)=\max \left\{ c(G-S)-|S|\right\} \) s ( G ) = max c ( G - S ) - | S | (resp. \(\tau (G)=\min \left\{ \frac{\vert S \vert }{c(G-S)-1}\right\} \) τ ( G ) = min | S | c ( G - S ) - 1 ), in which the maximum (resp. minimum) is taken over all proper sets \(S\subseteq V(G)\) S V ( G ) , where \(c(G-S)\) c ( G - S ) denotes the number of components of \(G-S\) G - S . These two parameters are known as the variants of the toughness of a graph. In this paper, we study the scattering number and the \(\tau \) τ -toughness by the eigenvalues of matrices associated with a graph. For the scattering number, we establish a sufficient condition involving the spectral radius for a graph G with minimum degree \(\delta \) δ such that \(s(G)\le 1\) s ( G ) 1 , as well as a condition involving Laplacian eigenvalues for a graph with \(s(G)\le 1\) s ( G ) 1 . Additionally, we present a lower bound for s(G) of G in terms of its Laplacian eigenvalues. Our results extend or improve the recent corresponding results. A non-complete graph G is \(\tau \) τ -tough if \(\tau (G)\ge \tau \) τ ( G ) τ . For \(\tau \) τ -tough graphs, we establish a sufficient condition involving the size (or the signless Laplacian spectral radius) for a graph to be \(\tau \) τ -tough. Furthermore, we present two lower bounds for \(\tau (G)\) τ ( G ) of G in terms of its Laplacian eigenvalues. As applications, several new results on factors are derived, which improve the related existing results.