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
topHow 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 ?
topYou 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.