A spanning subgraph F of a graph G is called a star-cycle factor of G if each component of F is a star or cycle. Let G be a graph and f : V (G) → {1, 2, 3, . . .} be a function. Let W = {v ∈ V (G) : f(v) = 1}. Under this notation, it was proved by Berge and Las Vergnas that G has a star-cycle factor F with the property that (i) if a component D of F is a star with center v, then degF (v) ≤ f(v), and (ii) if a component D of F is a cycle, then V (D) ⊆ W if and only if iso(G − S) ≤ Σx∈S f(x) for all S ⊂ V (G), where iso(G − S) denotes the number of isolated vertices of G − S. They proved this result by using circulation theory of flows and fractional factors of graphs. In this paper, we give an elementary and short proof of this theorem.
@article{bwmeta1.element.doi-10_7151_dmgt_1717,
author = {Yoshimi Egawa and Mikio Kano and Zheng Yan},
title = {Star-Cycle Factors of Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {34},
year = {2014},
pages = {193-198},
zbl = {1292.05212},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1717}
}
Yoshimi Egawa; Mikio Kano; Zheng Yan. Star-Cycle Factors of Graphs. Discussiones Mathematicae Graph Theory, Tome 34 (2014) pp. 193-198. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1717/
[1] J. Akiyama and M. Kano, Factors and Factorizations of Graphs (Lecture Notes in Math. 2031, Springer, 2011). | Zbl 1229.05001
[2] A. Amahashi and M. Kano, On factors with given components, Discrete Math. 42 (1983) 1-6. doi:10.1016/0012-365X(82)90048-6[Crossref] | Zbl 0525.05048
[3] C. Berge and M. Las Vergnas, On the existence of subgraphs with degree constraints, Nederl. Akad. Wetensch. Indag. Math. 40 (1978) 165-176. doi:10.1016/1385-7258(78)90034-3[Crossref]
[4] M. Las Vergnas, An extension of Tutte‘s 1-factor theorem, Discrete Math. 23 (1978) 241-255. doi:10.1016/0012-365X(78)90006-7[Crossref]
[5] W.T. Tutte, The 1-factors of oriented graphs, Proc. Amer. Math. Soc. 4 (1953) 922-931. doi:10.2307/2031831[Crossref]