A note on the number of non-cycle components in a pseudo 2-factor of graphs
Discrete Applied Mathematics · 2026-11 · 393 · 121-125
DOI: 10.1016/j.dam.2026.06.029 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Applied Mathematics, 2026-11. Verfasst von Masaki Kashima. Die Arbeit nennt 8 Literaturangaben. Gefördert von: Japan Society for the Promotion of Science.
Abstract (Originalsprache)
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 $\alpha(G)-\delta(G)+1$ components that are not cycles. For a graph $G$ and a set of vertices $S$, let $\delta_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|-\delta_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.
Förderung
- Japan Society for the Promotion of Science
Zitieren
APA
Kashima, M. (2026). A note on the number of non-cycle components in a pseudo 2-factor of graphs. Discrete Applied Mathematics, 393, 121-125. https://doi.org/10.1016/j.dam.2026.06.029
Vancouver
Kashima M. A note on the number of non-cycle components in a pseudo 2-factor of graphs. Discrete Applied Mathematics. 2026;393:121-125. doi:10.1016/j.dam.2026.06.029
BibTeX
@article{Kashima2026,
author = {Kashima, Masaki},
title = {A note on the number of non-cycle components in a pseudo 2-factor of graphs},
journal = {Discrete Applied Mathematics},
year = {2026},
volume = {393},
pages = {121--125},
doi = {10.1016/j.dam.2026.06.029}
}
EUVIMED