<p>The spread of a graph is defined as the difference between the maximum and minimum eigenvalues of its adjacency matrix. A graph has the Hereditarily Bounded Property <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(P_{t,r}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mrow> <mi>t</mi> <mo>,</mo> <mi>r</mi> </mrow> </msub> </math></EquationSource> </InlineEquation> if, for any subgraph <i>H</i> of order at least <i>t</i>, the size of <i>H</i> is at most <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(t|V(H)|+r\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo stretchy="false">|</mo> <mi>V</mi> <mo stretchy="false">(</mo> <mi>H</mi> <mo stretchy="false">)</mo> <mo stretchy="false">|</mo> <mo>+</mo> <mi>r</mi> </mrow> </math></EquationSource> </InlineEquation>, where |<i>V</i>(<i>H</i>)| denotes the number of vertices in <i>H</i>. In this paper, we determine the unique graph with maximum spread among all graphs of order sufficiently large that satisfy the Hereditarily Bounded Property <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(P_{t,r}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>P</mi> <mrow> <mi>t</mi> <mo>,</mo> <mi>r</mi> </mrow> </msub> </math></EquationSource> </InlineEquation>, where <i>t</i> is a positive integer and <i>r</i> is a real number with <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(r\ge -{t+1\atopwithdelims ()2}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>r</mi> <mo>≥</mo> <mo>-</mo> <mfenced close=")" open="("> <mfrac linethickness="0pt"> <mrow> <mi>t</mi> <mo>+</mo> <mn>1</mn> </mrow> <mn>2</mn> </mfrac> </mfenced> </mrow> </math></EquationSource> </InlineEquation>. Key applications of this result include the characterization of extremal graphs with maximum spread for the following families of asymptotically large graphs: graphs whose size equals their order plus a fixed non-negative integer; graphs excluding a <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\((t + 1)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mi>t</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-matching; graphs containing no <i>t</i> disjoint cycles. We conclude by proposing two open problems related to extremal spread properties, inviting further exploration in spectral graph theory.</p>

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

Maximum spread of graphs with the Hereditarily Bounded Property

  • Min Feng,
  • Minqing Zhai

摘要

The spread of a graph is defined as the difference between the maximum and minimum eigenvalues of its adjacency matrix. A graph has the Hereditarily Bounded Property \(P_{t,r}\) P t , r if, for any subgraph H of order at least t, the size of H is at most \(t|V(H)|+r\) t | V ( H ) | + r , where |V(H)| denotes the number of vertices in H. In this paper, we determine the unique graph with maximum spread among all graphs of order sufficiently large that satisfy the Hereditarily Bounded Property \(P_{t,r}\) P t , r , where t is a positive integer and r is a real number with \(r\ge -{t+1\atopwithdelims ()2}\) r - t + 1 2 . Key applications of this result include the characterization of extremal graphs with maximum spread for the following families of asymptotically large graphs: graphs whose size equals their order plus a fixed non-negative integer; graphs excluding a \((t + 1)\) ( t + 1 ) -matching; graphs containing no t disjoint cycles. We conclude by proposing two open problems related to extremal spread properties, inviting further exploration in spectral graph theory.