A generalization of the Chvátal-Erdős theorem
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908370269634560 |
|---|---|
| author | Cheng, Kun |
| author_facet | Cheng, Kun |
| contents | A well-known result of Chvátal and Erdős from 1972 states that a graph with connectivity not less than its independence number plus one is hamiltonian-connected. A graph $G$ is called an $[s,t]$-graph if any induced subgraph of $G$ of order $s$ has size at least $t.$ We prove that every $k$-connected $[k+1,2]$-graph is hamiltonian-connected except $kK_1\vee G_{k},$ where $k\ge 2$ and $G_{k}$ is an arbitrary graph of order $k.$ This generalizes the Chvátal-Erdős theorem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_12907 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A generalization of the Chvátal-Erdős theorem Cheng, Kun Combinatorics A well-known result of Chvátal and Erdős from 1972 states that a graph with connectivity not less than its independence number plus one is hamiltonian-connected. A graph $G$ is called an $[s,t]$-graph if any induced subgraph of $G$ of order $s$ has size at least $t.$ We prove that every $k$-connected $[k+1,2]$-graph is hamiltonian-connected except $kK_1\vee G_{k},$ where $k\ge 2$ and $G_{k}$ is an arbitrary graph of order $k.$ This generalizes the Chvátal-Erdős theorem. |
| title | A generalization of the Chvátal-Erdős theorem |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2505.12907 |