PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2014 | 34 | 1 | 193-198
Tytuł artykułu

Star-Cycle Factors of Graphs

Treść / Zawartość
Warianty tytułu
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.
Wydawca
Rocznik
Tom
34
Numer
1
Strony
193-198
Opis fizyczny
Daty
wydano
2014-02-01
online
2014-02-14
Twórcy
  • Tokyo University of Science, Shinjuku-Ku, Tokyo, Japan
autor
autor
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]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1717
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.