Star factors with given properties. (English) Zbl 0723.05099

Chen, Ciping; Egawa, Yoshimi; Kano, Mikio

Ars Comb. 28, 65-70 (1989).

Summary: A spanning subgraph F of a graph G is called a \(\{K_{1,1},...,K_{1,n}\}\)-factor if each component of F is isomorphic to one of \(\{K_{1,1},...,K_{1,n}\}\), where \(K_{1,k}\) denotes the star of order \(k+1\). Among other results, we show that for a graph G, the following two statements are equivalent:
(1) every edge e of G possesses the property that some \(\{K_{1,1},...,K_{1,n}\}\)-factor of G has a component which is isomorphic to \(K_{1,1}\) or \(K_{1,2}\) and contains e;
(2) for all \(S\subset V(G)\), the number of isolated vertices of G-S is at most \(n| S| -\epsilon (S)\), where \(n\geq 2\) and \(\epsilon\) (S) is defined to be 2n-1 when the subgraph induced by S contains an edge, and to be 0 otherwise.

MSC:

05C70	Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C05	Trees

Keywords:

spanning subgraph; factor; star