Eigenvalues, edge-disjoint perfect matchings and toughness of regular graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908075481366528 |
|---|---|
| author | Zhang, Wenqian |
| author_facet | Zhang, Wenqian |
| contents | Let $G$ be a connected $d$-regular graph of order $n$, where $d\geq3$. Let $λ_{2}(G)$ be the second largest eigenvalue of $G$. For even $n$, we show that $G$ contains $\left\lfloor\frac{2}{3}(d-λ_{2}(G))\right\rfloor$ edge-disjoint perfect matchings. This improves a result stated by Cioabă, Gregory and Haemers \cite{CGH}. Let $t(G)$ be the toughness of $G$. When $G$ is non-bipartite, we give a sharp upper bound of $λ_{2}(G)$ to guarantee that $t(G)>1$. This enriches the previous results on this direction. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_04413 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Eigenvalues, edge-disjoint perfect matchings and toughness of regular graphs Zhang, Wenqian Combinatorics Let $G$ be a connected $d$-regular graph of order $n$, where $d\geq3$. Let $λ_{2}(G)$ be the second largest eigenvalue of $G$. For even $n$, we show that $G$ contains $\left\lfloor\frac{2}{3}(d-λ_{2}(G))\right\rfloor$ edge-disjoint perfect matchings. This improves a result stated by Cioabă, Gregory and Haemers \cite{CGH}. Let $t(G)$ be the toughness of $G$. When $G$ is non-bipartite, we give a sharp upper bound of $λ_{2}(G)$ to guarantee that $t(G)>1$. This enriches the previous results on this direction. |
| title | Eigenvalues, edge-disjoint perfect matchings and toughness of regular graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2410.04413 |