Some results on star-factor deleted graphs

Abstract

Let G be a graph and let k ? 2 be an integer. A {K1, j : 1 ? j ? k}-factor of G is a spanning subgraph of G, in which every component is isomorphic to a member in {K1, j : 1 ? j ? k}. A graph G is called a {K1, j : 1 ? j ? k}-factor deleted graph if for any e ? E(G), G has a {K1, j : 1 ? j ? k}-factor excluding e. In this article, we first give a characterization of {K1, j : 1 ? j ? k}-factor deleted graph. Then we show a lower bound on the binding number (resp. the size) of G to ensure that G is a {K1, j : 1 ? j ? k}-factor deleted graph. Finally, we construct two extremal graphs to claim that the bounds derived in this article are sharp.

Topics & Concepts