New type degree conditions for a graph to have a 2-factor
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908280648892416 |
|---|---|
| author | Kashima, Masaki |
| author_facet | Kashima, Masaki |
| contents | A 2-factor of a graph is a 2-regular spanning subgraph. For a graph $G$ and an independent set $I$ of $G$, let $δ_G(I)$ denote the minimum degree of vertices contained in $I$. We show that (1) if every independent set $I$ of $G$ satisfies $|I|\leq δ_G(I)-1$, then $G$ has a 2-factor and that (2) if every independent set $I$ of $G$ satisfies $|I|\leq δ_G(I)$, then $G$ has a 2-factor unless $G$ is isomorphic to a graph in completely determined exceptional graphs. It can be easily shown that the assumption of (1) is a relaxation of the Dirac condition on Hamiltonicity of graphs, and that the assumption of (2) is a relaxation of the Chvátal-Erdős condition on Hamiltonicity of graphs. Furthermore, for graphs with the assumption of (1), we show some results on a 2-factor with a bounded number of cycles. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_18409 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | New type degree conditions for a graph to have a 2-factor Kashima, Masaki Combinatorics 05C38, 05C45 A 2-factor of a graph is a 2-regular spanning subgraph. For a graph $G$ and an independent set $I$ of $G$, let $δ_G(I)$ denote the minimum degree of vertices contained in $I$. We show that (1) if every independent set $I$ of $G$ satisfies $|I|\leq δ_G(I)-1$, then $G$ has a 2-factor and that (2) if every independent set $I$ of $G$ satisfies $|I|\leq δ_G(I)$, then $G$ has a 2-factor unless $G$ is isomorphic to a graph in completely determined exceptional graphs. It can be easily shown that the assumption of (1) is a relaxation of the Dirac condition on Hamiltonicity of graphs, and that the assumption of (2) is a relaxation of the Chvátal-Erdős condition on Hamiltonicity of graphs. Furthermore, for graphs with the assumption of (1), we show some results on a 2-factor with a bounded number of cycles. |
| title | New type degree conditions for a graph to have a 2-factor |
| topic | Combinatorics 05C38, 05C45 |
| url | https://arxiv.org/abs/2503.18409 |