Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Star-Cycle Factors of Graphs

100%

Egawa Y., Kano M., Yan Z.

Discussiones Mathematicae Graph Theory

2014

tom 34

nr 1

193-198

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.

Ograniczanie wyników

1 Discussiones Mathematicae Graph Theory

1 Egawa Y.

1 Kano M.

1 Yan Z.

1 2014

Wyniki wyszukiwania

Star-Cycle Factors of Graphs