Star partitions of graphs
Yoshimi Egawa, Mikio Kanō, Alexander K. Kelmans · 1997
Let G be a graph and n ≥ 2 an integer. We prove that the following are equivalent: (i) there is a partition (V1,...,Vm) ofV (G) such that each Vi induces one of stars K1,1,...,K1,n, and (ii) for every subset S of V (G), G\\S has at most n|S| components with the property that each of their blocks is an odd order complete graph.