A note on the number of non-cycle components in a pseudo 2-factor of graphs
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_ | 1866911209094119424 |
|---|---|
| author | Kashima, Masaki |
| author_facet | Kashima, Masaki |
| contents | A pseudo 2-factor of a graph is a spanning subgraph such that each component is $K_1$, $K_2$, or a cycle. This notion was introduced by Bekkai and Kouider in 2009, where they showed that every graph $G$ has a pseudo 2-factor with at most $α(G)-δ(G)+1$ components that are not cycles. For a graph $G$ and a set of vertices $S$, let $δ_G(S)$ denote the minimum degree of vertices in $S$. In this note, we show that every graph $G$ has a pseudo 2-factor with at most $f(G)$ components that are not cycles, where $f(G)$ is the maximum value of $|I|-δ_G(I)+1$ among all independent sets $I$ of $G$. This result is a common generalization of a result by Bekkai and Kouider and a previous result by the author on the existence of a 2-factor. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_12155 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A note on the number of non-cycle components in a pseudo 2-factor of graphs Kashima, Masaki Combinatorics 05C38, 05C70 A pseudo 2-factor of a graph is a spanning subgraph such that each component is $K_1$, $K_2$, or a cycle. This notion was introduced by Bekkai and Kouider in 2009, where they showed that every graph $G$ has a pseudo 2-factor with at most $α(G)-δ(G)+1$ components that are not cycles. For a graph $G$ and a set of vertices $S$, let $δ_G(S)$ denote the minimum degree of vertices in $S$. In this note, we show that every graph $G$ has a pseudo 2-factor with at most $f(G)$ components that are not cycles, where $f(G)$ is the maximum value of $|I|-δ_G(I)+1$ among all independent sets $I$ of $G$. This result is a common generalization of a result by Bekkai and Kouider and a previous result by the author on the existence of a 2-factor. |
| title | A note on the number of non-cycle components in a pseudo 2-factor of graphs |
| topic | Combinatorics 05C38, 05C70 |
| url | https://arxiv.org/abs/2510.12155 |