Article ID Journal Published Year Pages File Type
6872444 Discrete Applied Mathematics 2014 7 Pages PDF
Abstract
A pseudo [2,b]-factor of a graph G is a spanning subgraph in which each component C on at least three vertices verifies 2≤dC(x)≤b, for every vertex x in C. Given an integer b≥4, we show that a graph G with minimum degree δ, independence number α>b(δ−1)2 and without isolated vertices possesses a pseudo [2,b]-factor with at most α−⌊b2(δ−1)⌋ components that are edges or vertices. This bound is sharp.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,