Star-Cycle Factors of Graphs

• Autorzy: Yoshimi Egawa , Mikio Kano , Zheng Yan
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

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

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2014
• Tom: 34
• Numer: 1
• Strony: 193-198

Daty

wydano

2014-02-01

online

2014-02-14

Twórcy

autor

Yoshimi Egawa

• Tokyo University of Science, Shinjuku-Ku, Tokyo, Japan

autor

Mikio Kano

• Ibaraki University, Hitachi, Ibaraki, Japan

autor

Zheng Yan

• Ibaraki University, Hitachi, Ibaraki, Japan

Bibliografia

• [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[Crossref]
• [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]

Identyfikatory

DOI

10.7151/dmgt.1717