Geodesic
Star-Cycle Factors of Graphs
Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 1, pp. 193-198 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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 deg_F (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.
Keywords: star factor, cycle factor, star-cycle factor, factor of graph 
@article{DMGT_2014_34_1_a15,
     author = {Egawa, Yoshimi and Kano, Mikio and Yan, Zheng},
     title = {Star-Cycle {Factors} of {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {193--198},
     year = {2014},
     volume = {34},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2014_34_1_a15/}
}
TY  - JOUR
AU  - Egawa, Yoshimi
AU  - Kano, Mikio
AU  - Yan, Zheng
TI  - Star-Cycle Factors of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2014
SP  - 193
EP  - 198
VL  - 34
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2014_34_1_a15/
LA  - en
ID  - DMGT_2014_34_1_a15
ER  - 
%0 Journal Article
%A Egawa, Yoshimi
%A Kano, Mikio
%A Yan, Zheng
%T Star-Cycle Factors of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2014
%P 193-198
%V 34
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2014_34_1_a15/
%G en
%F DMGT_2014_34_1_a15
Egawa, Yoshimi; Kano, Mikio; Yan, Zheng. Star-Cycle Factors of Graphs. Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 1, pp. 193-198. http://geodesic.mathdoc.fr/item/DMGT_2014_34_1_a15/

[1] J. Akiyama and M. Kano, Factors and Factorizations of Graphs (Lecture Notes in Math. 2031, Springer, 2011).

[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

[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

[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

[5] W.T. Tutte, The 1-factors of oriented graphs, Proc. Amer. Math. Soc. 4 (1953) 922-931. doi:10.2307/2031831