Finding graph minimum stable set and core via semi-tensor product approach

By resorting to a new matrix product, called semi-tensor product of matrices, this paper investigates the Minimum stable set and core of graph, and also presents a number of results and algorithms. By defining a characteristic logical vector and using matrix expressions of logical functions, a new algebraic representation is derived for the externally stable set. Then, based on the algebraic representation, an algorithm is established to find all the externally stable sets. According to this algorithm, a new necessary and sufficient condition is obtained to determine whether a given vertex subset is an absolutely minimum externally stable set or not. Meanwhile, a new algorithm is also obtained to find all the absolutely minimum externally stable sets. Finally, the graph core, which is simultaneously externally stable set and internally stable set, is investigated. Here the internally stable set requires that internal nodes of this set are all disconnected with each other. Using semi-tensor product, some necessary and sufficient conditions are presented, and then an algorithm is established to find all the graph cores. The study of illustrative examples shows that the results/algorithms presented in this paper are effective. (C) 2015 Elsevier B.V. All rights reserved.