<p>The binding number of a graph <i>G</i> is defined as <Equation ID="Equ19"> <EquationSource Format="TEX">\(\begin{aligned} \operatorname {bind}(G)=\min \left\{ \frac{|N_G(S)|}{|S|}\,\bigg |\,\emptyset \ne S\subseteq V(G), N_G(S)\ne V(G)\right\} . \end{aligned}\)</EquationSource> <EquationSource Format="MATHML"><math display="block"> <mrow> <mtable> <mtr> <mtd columnalign="right"> <mrow> <mo>bind</mo> <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> <mrow> <mo stretchy="false">|</mo> </mrow> <msub> <mi>N</mi> <mi>G</mi> </msub> <mrow> <mrow> <mo stretchy="false">(</mo> <mi>S</mi> <mo stretchy="false">)</mo> </mrow> <mo stretchy="false">|</mo> </mrow> </mrow> <mrow> <mo stretchy="false">|</mo> <mi>S</mi> <mo stretchy="false">|</mo> </mrow> </mfrac> <mspace width="0.166667em" /> <mrow> <mo maxsize="2.047em" minsize="2.047em" stretchy="true">|</mo> </mrow> <mspace width="0.166667em" /> <mi mathvariant="normal">∅</mi> <mo>≠</mo> <mi>S</mi> <mo>⊆</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>,</mo> <msub> <mi>N</mi> <mi>G</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>S</mi> <mo stretchy="false">)</mo> </mrow> <mo>≠</mo> <mi>V</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mfenced> <mo>.</mo> </mrow> </mtd> </mtr> </mtable> </mrow> </math></EquationSource> </Equation>As a key structural parameter in graph factor theory, the binding number provides a useful tool for inferring the existence of various graph factors. We address the Brualdi–Solheid type problem for graphs with a given binding number and identify the extremal graph with the maximum spectral radius. For a real number <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(r\ge 0\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>≥</mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation>, a graph <i>G</i> is called to be <i>r</i>-binding if <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\operatorname {bind}(G)\ge r\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo>bind</mo> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> <mo>≥</mo> <mi>r</mi> </mrow> </math></EquationSource> </InlineEquation>. A natural question is to determine whether a graph is <i>r</i>-binding. For a positive integer <i>r</i>, Fan and Lin (<CitationRef CitationID="CR13">2024</CitationRef>) provided a spectral radius condition to guarantee a connected graph to be <i>r</i>-binding. In this paper, we extend their result by establishing two tight sufficient conditions based on the size and the spectral radius, respectively, for a connected graph to be <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(\frac{1}{r}\)</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mn>1</mn> <mi>r</mi> </mfrac> </math></EquationSource> </InlineEquation>-binding.</p>

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

Characterizing a connected graph to be \(\frac{1}{r}\)-binding via its size or spectral radius

  • Zeyuan Wu,
  • Hongzhang Chen,
  • Jianxi Li

摘要

The binding number of a graph G is defined as \(\begin{aligned} \operatorname {bind}(G)=\min \left\{ \frac{|N_G(S)|}{|S|}\,\bigg |\,\emptyset \ne S\subseteq V(G), N_G(S)\ne V(G)\right\} . \end{aligned}\) bind ( G ) = min | N G ( S ) | | S | | S V ( G ) , N G ( S ) V ( G ) . As a key structural parameter in graph factor theory, the binding number provides a useful tool for inferring the existence of various graph factors. We address the Brualdi–Solheid type problem for graphs with a given binding number and identify the extremal graph with the maximum spectral radius. For a real number \(r\ge 0\) r 0 , a graph G is called to be r-binding if \(\operatorname {bind}(G)\ge r\) bind ( G ) r . A natural question is to determine whether a graph is r-binding. For a positive integer r, Fan and Lin (2024) provided a spectral radius condition to guarantee a connected graph to be r-binding. In this paper, we extend their result by establishing two tight sufficient conditions based on the size and the spectral radius, respectively, for a connected graph to be \(\frac{1}{r}\) 1 r -binding.