# Star-Cycle Factors of Graphs

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

top

## Abstract

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

## How to cite

top

Yoshimi 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. [1] J. Akiyama and M. Kano, Factors and Factorizations of Graphs (Lecture Notes in Math. 2031, Springer, 2011). Zbl1229.05001
2. [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. [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. [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. [5] W.T. Tutte, The 1-factors of oriented graphs, Proc. Amer. Math. Soc. 4 (1953) 922-931. doi:10.2307/2031831[Crossref]

## NotesEmbed?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.