Spectral extrema of graphs with fixed size: forbidden a fan graph, friendship graph or theta graph
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915448345329664 |
|---|---|
| author | Li, Shuchao Zhao, Sishu Zou, Lantao |
| author_facet | Li, Shuchao Zhao, Sishu Zou, Lantao |
| contents | It is well-known that the Brualdi-Hoffman-Turán-type problem inquiries about the maximum spectral radius \( λ(G) \) of an \( F \)-free graph \( G \) with \( m \) edges. Let \( θ_{1,p,q} \) denote the theta graph, which is constructed by connecting two vertices with 3 internally disjoint paths of lengths 1, \( p \), and \( q \) respectively. Let \( F_k \) be the fan graph, that is, the join of a \( K_1 \) and a path \( P_{k - 1} \). Let \( F_{k,3} \) be the friendship graph, obtained by having \( k \) triangles share a common vertex. In this paper, we utilize the \( k \)-core method and spectral techniques to address some spectral extrema of graphs with a fixed number of edges. Firstly, we demonstrate that for \( m \geqslant \frac{9}{4}k^6 + 6k^5 + 46k^4 + 56k^3 + 196k^2 \) and \( k \geqslant 3 \), if \( G \) is \( F_{2k + 2} \)-free, then \( λ(G) \leqslant \frac{k - 1 + \sqrt{4m - k^2 + 1}}{2} \). Equality holds if and only if \( G \cong K_k \vee (\frac{m}{k}-\frac{k - 1}{2})K_1 \). This validates a conjecture by Yu, Li, and Peng [Discrete Math. 348 (2025) 114391] and refines a recent result by Li, Zhai, and Shu [European J. Combin. 120 (2024) 103966]. Secondly, we show that for \( m \geqslant \frac{9}{4}k^6 + 6k^5 + 46k^4 + 56k^3 + 196k^2 \) with \( k \geqslant 3 \), if \( G \) is \( F_{k,3} \)-free and has \( m \) edges, then \( λ(G) \leqslant \frac{k - 1 + \sqrt{4m - k^2 + 1}}{2} \). Equality holds precisely when \( G \cong K_k \vee (\frac{m}{k}-\frac{k - 1}{2})K_1 \). This confirms a conjecture put forward by Li, Lu, and Peng [Discrete Math. 346(2023)113680]. Finally, we identify the \( θ_{1,p,q} \)-free graph with \( m \) edges that possesses the largest spectral radius, where \( q \geqslant p \geqslant 3 \) and \( p + q \geqslant 2k + 1 \). A further research problem is also proposed. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_15918 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Spectral extrema of graphs with fixed size: forbidden a fan graph, friendship graph or theta graph Li, Shuchao Zhao, Sishu Zou, Lantao Combinatorics 05C50, 05C35 It is well-known that the Brualdi-Hoffman-Turán-type problem inquiries about the maximum spectral radius \( λ(G) \) of an \( F \)-free graph \( G \) with \( m \) edges. Let \( θ_{1,p,q} \) denote the theta graph, which is constructed by connecting two vertices with 3 internally disjoint paths of lengths 1, \( p \), and \( q \) respectively. Let \( F_k \) be the fan graph, that is, the join of a \( K_1 \) and a path \( P_{k - 1} \). Let \( F_{k,3} \) be the friendship graph, obtained by having \( k \) triangles share a common vertex. In this paper, we utilize the \( k \)-core method and spectral techniques to address some spectral extrema of graphs with a fixed number of edges. Firstly, we demonstrate that for \( m \geqslant \frac{9}{4}k^6 + 6k^5 + 46k^4 + 56k^3 + 196k^2 \) and \( k \geqslant 3 \), if \( G \) is \( F_{2k + 2} \)-free, then \( λ(G) \leqslant \frac{k - 1 + \sqrt{4m - k^2 + 1}}{2} \). Equality holds if and only if \( G \cong K_k \vee (\frac{m}{k}-\frac{k - 1}{2})K_1 \). This validates a conjecture by Yu, Li, and Peng [Discrete Math. 348 (2025) 114391] and refines a recent result by Li, Zhai, and Shu [European J. Combin. 120 (2024) 103966]. Secondly, we show that for \( m \geqslant \frac{9}{4}k^6 + 6k^5 + 46k^4 + 56k^3 + 196k^2 \) with \( k \geqslant 3 \), if \( G \) is \( F_{k,3} \)-free and has \( m \) edges, then \( λ(G) \leqslant \frac{k - 1 + \sqrt{4m - k^2 + 1}}{2} \). Equality holds precisely when \( G \cong K_k \vee (\frac{m}{k}-\frac{k - 1}{2})K_1 \). This confirms a conjecture put forward by Li, Lu, and Peng [Discrete Math. 346(2023)113680]. Finally, we identify the \( θ_{1,p,q} \)-free graph with \( m \) edges that possesses the largest spectral radius, where \( q \geqslant p \geqslant 3 \) and \( p + q \geqslant 2k + 1 \). A further research problem is also proposed. |
| title | Spectral extrema of graphs with fixed size: forbidden a fan graph, friendship graph or theta graph |
| topic | Combinatorics 05C50, 05C35 |
| url | https://arxiv.org/abs/2409.15918 |