A lower bound of toughness of regular graphs: in terms of second largest eigenvalue
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917453206913024 |
|---|---|
| author | Zhang, Wenqian |
| author_facet | Zhang, Wenqian |
| contents | Let $G$ be a connected (non-complete) $d$-regular graph with $d\geq3$. Let $c(G-S)$ denote the number of components of $G-S$ for any cut $S$ of $G$. The toughness $t(G)$ of $G$ is defined as $\min\left\{\frac{|S|}{c(G-S)}\right\}$, where the minimum is taken over all proper cuts $S$ of $G$. Let $λ_{2}(G)$ denote the second largest eigenvalue of $G$. In this paper, we prove $$t(G)\geq\min\left\{\frac{d+1}{d}(d-λ_{2}(G)),1\right\}.$$ |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_00627 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A lower bound of toughness of regular graphs: in terms of second largest eigenvalue Zhang, Wenqian Combinatorics Let $G$ be a connected (non-complete) $d$-regular graph with $d\geq3$. Let $c(G-S)$ denote the number of components of $G-S$ for any cut $S$ of $G$. The toughness $t(G)$ of $G$ is defined as $\min\left\{\frac{|S|}{c(G-S)}\right\}$, where the minimum is taken over all proper cuts $S$ of $G$. Let $λ_{2}(G)$ denote the second largest eigenvalue of $G$. In this paper, we prove $$t(G)\geq\min\left\{\frac{d+1}{d}(d-λ_{2}(G)),1\right\}.$$ |
| title | A lower bound of toughness of regular graphs: in terms of second largest eigenvalue |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2605.00627 |