For a family of graphs <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mathcal {H}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">H</mi> </math></EquationSource> </InlineEquation>, a graph G is <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\mathcal {H}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">H</mi> </math></EquationSource> </InlineEquation>-free if it does not contain a subgraph isomorphic to any graph in <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\mathcal {H}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">H</mi> </math></EquationSource> </InlineEquation>. Nikiforov (Linear Algebra Appl 432:2243–2256, 2010) proposed a spectral analogue of the Turán problem which asks to determine the maximum spectral radius of an H-free graph of size m or order n. Let <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$F_k$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>F</mi> <mi>k</mi> </msub> </math></EquationSource> </InlineEquation> be the graph obtained from k intersecting triangles sharing a common vertex. For <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$k=2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>=</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>, the graph <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$F_2$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>F</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation> is called the bowtie. Let <InlineEquation ID="IEq7"> <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="IEq8"> <EquationSource Format="TEX">$K_2$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation> to <InlineEquation ID="IEq9"> <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="IEq10"> <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="IEq11"> <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 vertex of degree 2. Li et al. (Discrete Math 346:113680, 2023) showed that <InlineEquation ID="IEq12"> <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> for any <InlineEquation ID="IEq13"> <EquationSource Format="TEX">$F_2$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>F</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation>-free graph of size <InlineEquation ID="IEq14"> <EquationSource Format="TEX">$m\ge 8$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>m</mi> <mo>≥</mo> <mn>8</mn> </mrow> </math></EquationSource> </InlineEquation>. They also proved that the unique extremal graph is the join of <InlineEquation ID="IEq15"> <EquationSource Format="TEX">$K_2$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>K</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation> with an independent set of <InlineEquation ID="IEq16"> <EquationSource Format="TEX">$\frac{m-1}{2}$</EquationSource> <EquationSource Format="MATHML"><math> <mfrac> <mrow> <mi>m</mi> <mo>-</mo> <mn>1</mn> </mrow> <mn>2</mn> </mfrac> </math></EquationSource> </InlineEquation> vertices. However, this bound is only sharp for odd m. Let <InlineEquation ID="IEq17"> <EquationSource Format="TEX">$\mathcal {F}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> </InlineEquation> be a family of graphs, where any m-edge graph G in <InlineEquation ID="IEq18"> <EquationSource Format="TEX">$\mathcal {F}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> </InlineEquation> is obtained from a bipartite graph B(S, W) (not necessarily complete) by adding two new vertices u and <InlineEquation ID="IEq19"> <EquationSource Format="TEX">$v_0$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>v</mi> <mn>0</mn> </msub> </math></EquationSource> </InlineEquation>, an edge <InlineEquation ID="IEq20"> <EquationSource Format="TEX">$uv_0$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>u</mi> <msub> <mi>v</mi> <mn>0</mn> </msub> </mrow> </math></EquationSource> </InlineEquation>, all edges between u and S, and t edges between <InlineEquation ID="IEq21"> <EquationSource Format="TEX">$v_0$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>v</mi> <mn>0</mn> </msub> </math></EquationSource> </InlineEquation> and S, where <InlineEquation ID="IEq22"> <EquationSource Format="TEX">$t\le |N(u)|$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>t</mi> <mo>≤</mo> <mo stretchy="false">|</mo> <mi>N</mi> <mo stretchy="false">(</mo> <mi>u</mi> <mo stretchy="false">)</mo> <mo stretchy="false">|</mo> </mrow> </math></EquationSource> </InlineEquation>. In this paper, we determine a sharp upper bound for <InlineEquation ID="IEq23"> <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> in <InlineEquation ID="IEq24"> <EquationSource Format="TEX">$F_2$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>F</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation>-free graphs that do not belong to <InlineEquation ID="IEq25"> <EquationSource Format="TEX">$\mathcal {F}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">F</mi> </math></EquationSource> </InlineEquation>, given that G has <InlineEquation ID="IEq26"> <EquationSource Format="TEX">$m$</EquationSource> <EquationSource Format="MATHML"><math> <mi>m</mi> </math></EquationSource> </InlineEquation> (even) edges.

On the Spectral Radius of Bowtie-Free Graphs with Given Size

期刊论文
发表日期：

2026年1月19日

查看全文

S. Pirzada,
Amir Rehman

摘要

For a family of graphs $\mathcal {H}$ $H$ , a graph G is $\mathcal {H}$ $H$ -free if it does not contain a subgraph isomorphic to any graph in $\mathcal {H}$ $H$ . Nikiforov (Linear Algebra Appl 432:2243–2256, 2010) proposed a spectral analogue of the Turán problem which asks to determine the maximum spectral radius of an H-free graph of size m or order n. Let $F_k$ $F_{k}$ be the graph obtained from k intersecting triangles sharing a common vertex. For $k=2$ $k = 2$ , the graph $F_2$ $F_{2}$ is called the bowtie. 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 vertex of degree 2. Li et al. (Discrete Math 346:113680, 2023) showed that $\rho (G)\le \frac{1+\sqrt{4m-3}}{2}$ $ρ (G) \leq \frac{1 + \sqrt{4 m - 3}}{2}$ for any $F_2$ $F_{2}$ -free graph of size $m\ge 8$ $m \geq 8$ . They also proved that the unique extremal graph is the join of $K_2$ $K_{2}$ with an independent set of $\frac{m-1}{2}$ $\frac{m - 1}{2}$ vertices. However, this bound is only sharp for odd m. Let $\mathcal {F}$ $F$ be a family of graphs, where any m-edge graph G in $\mathcal {F}$ $F$ is obtained from a bipartite graph B(S, W) (not necessarily complete) by adding two new vertices u and $v_0$ $v_{0}$ , an edge $uv_0$ $u v_{0}$ , all edges between u and S, and t edges between $v_0$ $v_{0}$ and S, where $t\le |N(u)|$ $t \leq | N (u) |$ . In this paper, we determine a sharp upper bound for $\rho (G)$ $ρ (G)$ in $F_2$ $F_{2}$ -free graphs that do not belong to $\mathcal {F}$ $F$ , given that G has $m$ $m$ (even) edges.