On the maximum second eigenvalue of outerplanar graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916480828833792 |
|---|---|
| author | Brooks, George Gu, Maggie Hyatt, Jack Linz, William Lu, Linyuan |
| author_facet | Brooks, George Gu, Maggie Hyatt, Jack Linz, William Lu, Linyuan |
| contents | For a fixed positive integer $k$ and a graph $G$, let $λ_k(G)$ denote the $k$-th largest eigenvalue of the adjacency matrix of $G$. In 2017, Tait and Tobin proved that the maximum $λ_1(G)$ among all outerplanar graphs on $n$ vertices is achieved by the fan graph $K_1\vee P_{n-1}$. In this paper, we consider a similar problem of determining the maximum $λ_2$ among all connected outerplanar graphs on $n$ vertices. For $n$ even and sufficiently large, we prove that the maximum $λ_2$ is uniquely achieved by the graph $(K_1\vee P_{n/2-1})\!\!-\!\!(K_1\vee P_{n/2-1})$, which is obtained by connecting two disjoint copies of $(K_1\vee P_{n/2-1})$ through a new edge joining their smallest degree vertices. When $n$ is odd and sufficiently large, the extremal graphs are not unique. The extremal graphs are those graphs $G$ that contain a cut vertex $u$ such that $G\setminus \{u\}$ is isomorphic to $2(K_1\vee P_{n/2-1})$. We also determine the maximum $λ_2$ among all 2-connected outerplanar graphs and asymptotically determine the maximum of $λ_k(G)$ among all connected outerplanar graphs for any fixed $k$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_08548 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the maximum second eigenvalue of outerplanar graphs Brooks, George Gu, Maggie Hyatt, Jack Linz, William Lu, Linyuan Combinatorics For a fixed positive integer $k$ and a graph $G$, let $λ_k(G)$ denote the $k$-th largest eigenvalue of the adjacency matrix of $G$. In 2017, Tait and Tobin proved that the maximum $λ_1(G)$ among all outerplanar graphs on $n$ vertices is achieved by the fan graph $K_1\vee P_{n-1}$. In this paper, we consider a similar problem of determining the maximum $λ_2$ among all connected outerplanar graphs on $n$ vertices. For $n$ even and sufficiently large, we prove that the maximum $λ_2$ is uniquely achieved by the graph $(K_1\vee P_{n/2-1})\!\!-\!\!(K_1\vee P_{n/2-1})$, which is obtained by connecting two disjoint copies of $(K_1\vee P_{n/2-1})$ through a new edge joining their smallest degree vertices. When $n$ is odd and sufficiently large, the extremal graphs are not unique. The extremal graphs are those graphs $G$ that contain a cut vertex $u$ such that $G\setminus \{u\}$ is isomorphic to $2(K_1\vee P_{n/2-1})$. We also determine the maximum $λ_2$ among all 2-connected outerplanar graphs and asymptotically determine the maximum of $λ_k(G)$ among all connected outerplanar graphs for any fixed $k$. |
| title | On the maximum second eigenvalue of outerplanar graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2309.08548 |