<p>For a simple connected graph <i>G</i> of size <i>m</i>, let <i>A</i> be the adjacency matrix and let <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3257_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="37" /> </InlineMediaObject> <EquationSource Format="TEX">\(\rho (G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ρ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> be the spectral radius. A graph is said to be <i>H</i>-free if it does not contain a subgraph isomorphic to <i>H</i>. Let <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3257_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="52" /> </InlineMediaObject> <EquationSource Format="TEX">\(H(\ell ,3)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>H</mi> <mo stretchy="false">(</mo> <mi>ℓ</mi> <mo>,</mo> <mn>3</mn> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> be the graph formed by taking a cycle of length <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3257_Article_IEq3.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="12" /> </InlineMediaObject> <EquationSource Format="TEX">\(\ell \)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation> and a triangle on a common vertex. Let <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3257_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="28" /> </InlineMediaObject> <EquationSource Format="TEX">\(S_{n,2}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>S</mi> <mrow> <mi>n</mi> <mo>,</mo> <mn>2</mn> </mrow> </msub> </math></EquationSource> </InlineEquation> be the graph obtained by joining each vertex of <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3257_Article_IEq5.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> to <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3257_Article_IEq6.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="41" /> </InlineMediaObject> <EquationSource Format="TEX">\(n-2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>-</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation> isolated vertices and let <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3257_Article_IEq7.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="28" /> </InlineMediaObject> <EquationSource Format="TEX">\(S_{n,2}^-\)</EquationSource> <EquationSource Format="MATHML"><math> <msubsup> <mi>S</mi> <mrow> <mi>n</mi> <mo>,</mo> <mn>2</mn> </mrow> <mo>-</mo> </msubsup> </math></EquationSource> </InlineEquation> be the graph obtained from <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3257_Article_IEq4.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="28" /> </InlineMediaObject> <EquationSource Format="TEX">\(S_{n,2}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>S</mi> <mrow> <mi>n</mi> <mo>,</mo> <mn>2</mn> </mrow> </msub> </math></EquationSource> </InlineEquation> by deleting an edge incident to a vertex of degree 2. The authors (2024) have shown that if <i>G</i> is a graph of odd size that does not contain the subgraphs <i>H</i>(3,&#xa0;3) and <i>H</i>(4,&#xa0;3), then <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3257_Article_IEq9.gif" Format="GIF" Height="26" Rendition="HTML" Resolution="72" Type="Linedraw" Width="117" /> </InlineMediaObject> <EquationSource Format="TEX">\(\rho (G)\le \frac{1+\sqrt{4m-3}}{2}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ρ</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <mfrac> <mrow> <mn>1</mn> <mo>+</mo> <msqrt> <mrow> <mn>4</mn> <mi>m</mi> <mo>-</mo> <mn>3</mn> </mrow> </msqrt> </mrow> <mn>2</mn> </mfrac> </mrow> </math></EquationSource> </InlineEquation>, with equality if and only if <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3257_Article_IEq10.gif" Format="GIF" Height="23" Rendition="HTML" Resolution="72" Type="Linedraw" Width="81" /> </InlineMediaObject> <EquationSource Format="TEX">\(G\cong S_{\frac{m+3}{2},2}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>≅</mo> <msub> <mi>S</mi> <mrow> <mfrac> <mrow> <mi>m</mi> <mo>+</mo> <mn>3</mn> </mrow> <mn>2</mn> </mfrac> <mo>,</mo> <mn>2</mn> </mrow> </msub> </mrow> </math></EquationSource> </InlineEquation>. In this paper, we show that if <i>G</i> is a <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3257_Article_IEq11.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="132" /> </InlineMediaObject> <EquationSource Format="TEX">\(\{H(3,3), H(4,3)\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">{</mo> <mi>H</mi> <mo stretchy="false">(</mo> <mn>3</mn> <mo>,</mo> <mn>3</mn> <mo stretchy="false">)</mo> <mo>,</mo> <mi>H</mi> <mo stretchy="false">(</mo> <mn>4</mn> <mo>,</mo> <mn>3</mn> <mo stretchy="false">)</mo> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>-free graph of even size, then <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3257_Article_IEq12.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="99" /> </InlineMediaObject> <EquationSource Format="TEX">\(\rho (G)\le \rho ^\prime (m)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ρ</mi> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> <mo>≤</mo> <msup> <mi>ρ</mi> <mo>′</mo> </msup> <mrow> <mo stretchy="false">(</mo> <mi>m</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq13"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3257_Article_IEq13.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">\(\rho ^\prime (m)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>ρ</mi> <mo>′</mo> </msup> <mrow> <mo stretchy="false">(</mo> <mi>m</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> is the largest root of <InlineEquation ID="IEq14"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3257_Article_IEq14.gif" Format="GIF" Height="22" Rendition="HTML" Resolution="72" Type="Linedraw" Width="247" /> </InlineMediaObject> <EquationSource Format="TEX">\(x^4-mx^2-(m-2)x+\frac{m}{2}-1=0\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>x</mi> <mn>4</mn> </msup> <mo>-</mo> <mi>m</mi> <msup> <mi>x</mi> <mn>2</mn> </msup> <mo>-</mo> <mrow> <mo stretchy="false">(</mo> <mi>m</mi> <mo>-</mo> <mn>2</mn> <mo stretchy="false">)</mo> </mrow> <mi>x</mi> <mo>+</mo> <mfrac> <mi>m</mi> <mn>2</mn> </mfrac> <mo>-</mo> <mn>1</mn> <mo>=</mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation>, and equality holds if and only if <InlineEquation ID="IEq15"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40314_2025_3257_Article_IEq15.gif" Format="GIF" Height="28" Rendition="HTML" Resolution="72" Type="Linedraw" Width="81" /> </InlineMediaObject> <EquationSource Format="TEX">\(G\cong S_{\frac{m+4}{2},2}^-\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>G</mi> <mo>≅</mo> <msubsup> <mi>S</mi> <mrow> <mfrac> <mrow> <mi>m</mi> <mo>+</mo> <mn>4</mn> </mrow> <mn>2</mn> </mfrac> <mo>,</mo> <mn>2</mn> </mrow> <mo>-</mo> </msubsup> </mrow> </math></EquationSource> </InlineEquation>. Furthermore, the condition on the number of edges to be greater than or equal to 10 is essential.</p>

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

The maximum spectral radius of graphs of even size forbidding {H(3, 3), H(4, 3)}

  • S. Pirzada,
  • Amir Rehman

摘要

For a simple connected graph G of size m, let A be the adjacency matrix and let \(\rho (G)\) ρ ( G ) be the spectral radius. A graph is said to be H-free if it does not contain a subgraph isomorphic to H. Let \(H(\ell ,3)\) H ( , 3 ) be the graph formed by taking a cycle of length \(\ell \) and a triangle on a common vertex. Let \(S_{n,2}\) S n , 2 be the graph obtained by joining each vertex of \(K_2\) K 2 to \(n-2\) n - 2 isolated vertices and let \(S_{n,2}^-\) S n , 2 - be the graph obtained from \(S_{n,2}\) S n , 2 by deleting an edge incident to a vertex of degree 2. The authors (2024) have shown that if G is a graph of odd size that does not contain the subgraphs H(3, 3) and H(4, 3), then \(\rho (G)\le \frac{1+\sqrt{4m-3}}{2}\) ρ ( G ) 1 + 4 m - 3 2 , with equality if and only if \(G\cong S_{\frac{m+3}{2},2}\) G S m + 3 2 , 2 . In this paper, we show that if G is a \(\{H(3,3), H(4,3)\}\) { H ( 3 , 3 ) , H ( 4 , 3 ) } -free graph of even size, then \(\rho (G)\le \rho ^\prime (m)\) ρ ( G ) ρ ( m ) , where \(\rho ^\prime (m)\) ρ ( m ) is the largest root of \(x^4-mx^2-(m-2)x+\frac{m}{2}-1=0\) x 4 - m x 2 - ( m - 2 ) x + m 2 - 1 = 0 , and equality holds if and only if \(G\cong S_{\frac{m+4}{2},2}^-\) G S m + 4 2 , 2 - . Furthermore, the condition on the number of edges to be greater than or equal to 10 is essential.