EUVIMEDEUVIMED entdecken
Crossref

A note on the number of non-cycle components in a pseudo 2-factor of graphs

Masaki Kashima

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →