Abstract: Face detection plays an important role in many applications such as face recognition, face image database and video surveillance. In this study a novel face detection algorithm has been introduced with accurate results. The method is based on the idea of Local Graph Structure (LGS) and neural network. LGS features are derived from a general definition of texture in a local graph neighbourhood. The features are based on dominating set of pixels on certain sub-graph of the image, once the features are extracted then neural network is applied as a classifier. The experiments results on CBL face database images demonstrated the effectiveness of the proposed method.