On maximum spectral radius of $\{H(3,3),~H(4,3)\}$-free graphs
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_ | 1866913188828676096 |
|---|---|
| author | Rehman, Amir Pirzada, S. |
| author_facet | Rehman, Amir Pirzada, S. |
| contents | Let $G$ be a simple connected graph of size $m$. Let $A$ be the adjacency matrix of $G$ and let $ρ(G)$ be the spectral radius of $G$. A graph is said to be $H$-free if it does not contain a subgraph isomorphic to $H$. Let $H(\ell,3)$ be the graph formed by taking a cycle of length $\ell$ and a triangle on a common vertex. Recently, Li, Lu and Peng [Y. Li, L. Lu, Y. Peng, Spectral extremal graphs for the bowtie, Discrete Math. 346(12) (2023) 113680.] showed that the unique $m$-edge $H(3,3)$-free spectral extremal graph is the join of $K_2$ with an independent set of $\frac{m-1}{2}$ vertices if $m\ge 8$ and the condition $m\ge 8$ is tight. In particular, if $G$ does not contain $H(3,3)$ as induced subgraph, they proved that $ρ(G) \leq \frac{1+\sqrt{4m-3}}{2} $ and equality holds when $G$ is isomorphic to $S_{\frac{m+3}{2},2}$. Note that Li et al. denoted $H(3,3)$ by $F_2$. In this paper, we find the maximum spectral radius and identify the graph with the largest spectral radius among all \{$H(3,3), H(4,3)$\}-free graphs of size odd $m$, where $m\geq 259$. Coincidentally, we show that $ρ(G) \leq \frac{1+\sqrt{4m-3}}{2}$ when $G$ forbids both $H(3,3)$ and $H(4,3)$. In our case, the equality holds when $G$ is isomorphic to the same graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_03787 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On maximum spectral radius of $\{H(3,3),~H(4,3)\}$-free graphs Rehman, Amir Pirzada, S. Combinatorics 05C50, 05C12, 15A18 Let $G$ be a simple connected graph of size $m$. Let $A$ be the adjacency matrix of $G$ and let $ρ(G)$ be the spectral radius of $G$. A graph is said to be $H$-free if it does not contain a subgraph isomorphic to $H$. Let $H(\ell,3)$ be the graph formed by taking a cycle of length $\ell$ and a triangle on a common vertex. Recently, Li, Lu and Peng [Y. Li, L. Lu, Y. Peng, Spectral extremal graphs for the bowtie, Discrete Math. 346(12) (2023) 113680.] showed that the unique $m$-edge $H(3,3)$-free spectral extremal graph is the join of $K_2$ with an independent set of $\frac{m-1}{2}$ vertices if $m\ge 8$ and the condition $m\ge 8$ is tight. In particular, if $G$ does not contain $H(3,3)$ as induced subgraph, they proved that $ρ(G) \leq \frac{1+\sqrt{4m-3}}{2} $ and equality holds when $G$ is isomorphic to $S_{\frac{m+3}{2},2}$. Note that Li et al. denoted $H(3,3)$ by $F_2$. In this paper, we find the maximum spectral radius and identify the graph with the largest spectral radius among all \{$H(3,3), H(4,3)$\}-free graphs of size odd $m$, where $m\geq 259$. Coincidentally, we show that $ρ(G) \leq \frac{1+\sqrt{4m-3}}{2}$ when $G$ forbids both $H(3,3)$ and $H(4,3)$. In our case, the equality holds when $G$ is isomorphic to the same graph. |
| title | On maximum spectral radius of $\{H(3,3),~H(4,3)\}$-free graphs |
| topic | Combinatorics 05C50, 05C12, 15A18 |
| url | https://arxiv.org/abs/2401.03787 |