<p>A graph <i>G</i> is said to be <i>F</i>-free if it does not contain <i>F</i> as a subgraph. Let <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1994_Article_IEq1.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="62" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal {G}(m, F)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">G</mi> <mo stretchy="false">(</mo> <mi>m</mi> <mo>,</mo> <mi>F</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> denote the set of <i>F</i>-free graphs with <i>m</i> edges having no isolated vertices. A theta graph, denoted by <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1994_Article_IEq2.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="42" /> </InlineMediaObject> <EquationSource Format="TEX">\(\theta _{l_1,l_2,l_3}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>θ</mi> <mrow> <msub> <mi>l</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>l</mi> <mn>2</mn> </msub> <mo>,</mo> <msub> <mi>l</mi> <mn>3</mn> </msub> </mrow> </msub> </math></EquationSource> </InlineEquation>, is the graph obtained by connecting two distinct vertices with three internally disjoint paths of length <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1994_Article_IEq3.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="50" /> </InlineMediaObject> <EquationSource Format="TEX">\(l_1, l_2, l_3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>l</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>l</mi> <mn>2</mn> </msub> <mo>,</mo> <msub> <mi>l</mi> <mn>3</mn> </msub> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq4"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1994_Article_IEq4.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="81" /> </InlineMediaObject> <EquationSource Format="TEX">\(l_1\le l_2\le l_3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>l</mi> <mn>1</mn> </msub> <mo>≤</mo> <msub> <mi>l</mi> <mn>2</mn> </msub> <mo>≤</mo> <msub> <mi>l</mi> <mn>3</mn> </msub> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq5"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1994_Article_IEq5.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="44" /> </InlineMediaObject> <EquationSource Format="TEX">\(l_2\ge 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>l</mi> <mn>2</mn> </msub> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>. Recently, Li, Zhao and Zou (2025) characterized the <InlineEquation ID="IEq6"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1994_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="34" /> </InlineMediaObject> <EquationSource Format="TEX">\(\theta _{1,p,q}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>θ</mi> <mrow> <mn>1</mn> <mo>,</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> </mrow> </msub> </math></EquationSource> </InlineEquation>-free graph of size <i>m</i> having the largest spectral radius, where <InlineEquation ID="IEq7"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1994_Article_IEq7.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="73" /> </InlineMediaObject> <EquationSource Format="TEX">\(q\ge p\ge 3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>q</mi> <mo>≥</mo> <mi>p</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq8"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1994_Article_IEq8.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="138" /> </InlineMediaObject> <EquationSource Format="TEX">\(p+q\ge 2k+1\ge 7\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo>+</mo> <mi>q</mi> <mo>≥</mo> <mn>2</mn> <mi>k</mi> <mo>+</mo> <mn>1</mn> <mo>≥</mo> <mn>7</mn> </mrow> </math></EquationSource> </InlineEquation>. Up to now, for all <InlineEquation ID="IEq9"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1994_Article_IEq6.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="34" /> </InlineMediaObject> <EquationSource Format="TEX">\(\theta _{1,p,q}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>θ</mi> <mrow> <mn>1</mn> <mo>,</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> </mrow> </msub> </math></EquationSource> </InlineEquation>-free graphs with <InlineEquation ID="IEq10"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1994_Article_IEq10.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="73" /> </InlineMediaObject> <EquationSource Format="TEX">\(q\ge p\ge 2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>q</mi> <mo>≥</mo> <mi>p</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, except for the case <InlineEquation ID="IEq11"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1994_Article_IEq11.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="71" /> </InlineMediaObject> <EquationSource Format="TEX">\(q=p=3\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>q</mi> <mo>=</mo> <mi>p</mi> <mo>=</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>, the graphs in <InlineEquation ID="IEq12"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1994_Article_IEq12.gif" Format="GIF" Height="20" Rendition="HTML" Resolution="72" Type="Linedraw" Width="81" /> </InlineMediaObject> <EquationSource Format="TEX">\(\mathcal {G}(m,\theta _{1,p,q})\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">G</mi> <mo stretchy="false">(</mo> <mi>m</mi> <mo>,</mo> <msub> <mi>θ</mi> <mrow> <mn>1</mn> <mo>,</mo> <mi>p</mi> <mo>,</mo> <mi>q</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> with the largest spectral radius have been determined. So they proposed a problem on characterizing the graphs with the maximum spectral radius among <InlineEquation ID="IEq13"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1994_Article_IEq13.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="34" /> </InlineMediaObject> <EquationSource Format="TEX">\(\theta _{1,3,3}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>θ</mi> <mrow> <mn>1</mn> <mo>,</mo> <mn>3</mn> <mo>,</mo> <mn>3</mn> </mrow> </msub> </math></EquationSource> </InlineEquation>-free graphs. In this paper, we consider this problem and determine the maximum spectral radius of <InlineEquation ID="IEq14"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="40840_2025_1994_Article_IEq13.gif" Format="GIF" Height="19" Rendition="HTML" Resolution="72" Type="Linedraw" Width="34" /> </InlineMediaObject> <EquationSource Format="TEX">\(\theta _{1,3,3}\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>θ</mi> <mrow> <mn>1</mn> <mo>,</mo> <mn>3</mn> <mo>,</mo> <mn>3</mn> </mrow> </msub> </math></EquationSource> </InlineEquation>-free graphs with size <i>m</i> and characterize the extremal graph.</p>

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

The Maximum Spectral Radius of Theta-Free Graphs with Given Size

  • Jing Gao,
  • Xueliang Li

摘要

A graph G is said to be F-free if it does not contain F as a subgraph. Let \(\mathcal {G}(m, F)\) G ( m , F ) denote the set of F-free graphs with m edges having no isolated vertices. A theta graph, denoted by \(\theta _{l_1,l_2,l_3}\) θ l 1 , l 2 , l 3 , is the graph obtained by connecting two distinct vertices with three internally disjoint paths of length \(l_1, l_2, l_3\) l 1 , l 2 , l 3 , where \(l_1\le l_2\le l_3\) l 1 l 2 l 3 and \(l_2\ge 2\) l 2 2 . Recently, Li, Zhao and Zou (2025) characterized the \(\theta _{1,p,q}\) θ 1 , p , q -free graph of size m having the largest spectral radius, where \(q\ge p\ge 3\) q p 3 and \(p+q\ge 2k+1\ge 7\) p + q 2 k + 1 7 . Up to now, for all \(\theta _{1,p,q}\) θ 1 , p , q -free graphs with \(q\ge p\ge 2\) q p 2 , except for the case \(q=p=3\) q = p = 3 , the graphs in \(\mathcal {G}(m,\theta _{1,p,q})\) G ( m , θ 1 , p , q ) with the largest spectral radius have been determined. So they proposed a problem on characterizing the graphs with the maximum spectral radius among \(\theta _{1,3,3}\) θ 1 , 3 , 3 -free graphs. In this paper, we consider this problem and determine the maximum spectral radius of \(\theta _{1,3,3}\) θ 1 , 3 , 3 -free graphs with size m and characterize the extremal graph.