# Star-Cycle Factors of Graphs

Yoshimi Egawa; Mikio Kano; Zheng Yan

Discussiones Mathematicae Graph Theory (2014)

- Volume: 34, Issue: 1, page 193-198
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topYoshimi Egawa, Mikio Kano, and Zheng Yan. "Star-Cycle Factors of Graphs." Discussiones Mathematicae Graph Theory 34.1 (2014): 193-198. <http://eudml.org/doc/267810>.

@article{YoshimiEgawa2014,

abstract = {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.},

author = {Yoshimi Egawa, Mikio Kano, Zheng Yan},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {star factor; cycle factor; star-cycle factor; factor of graph},

language = {eng},

number = {1},

pages = {193-198},

title = {Star-Cycle Factors of Graphs},

url = {http://eudml.org/doc/267810},

volume = {34},

year = {2014},

}

TY - JOUR

AU - Yoshimi Egawa

AU - Mikio Kano

AU - Zheng Yan

TI - Star-Cycle Factors of Graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2014

VL - 34

IS - 1

SP - 193

EP - 198

AB - 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.

LA - eng

KW - star factor; cycle factor; star-cycle factor; factor of graph

UR - http://eudml.org/doc/267810

ER -

## References

top- [1] J. Akiyama and M. Kano, Factors and Factorizations of Graphs (Lecture Notes in Math. 2031, Springer, 2011). Zbl1229.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] Zbl0525.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]

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.