Let T be a tree, a vertex of degree one and a vertex of degree at least three is called a leaf and a branch vertex, respectively. The set of leaves of T is denoted by Leaf(T). The subtree T − Leaf(T) of T is called the stem of T and denoted by Stem(T). In this paper, we give two sufficient conditions for a connected graph to have a spanning tree whose stem has a bounded number of branch vertices, and these conditions are best possible.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
Let G be a graph and f : V (G) → {2, 3, . . .}. A spanning subgraph F is called strong f-star of G if each component of F is a star whose center x satisfies degF (x) ≤ ƒ(x) and F is an induced subgraph of G. In this paper, we prove that G has a strong f-star factor if and only if oddca(G − S) ≤ ∑x∊S ƒ(x) for all S ⊂ V (G), where oddca(G) denotes the number of odd complete-cacti of G.
3
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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.
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ć.