Matrix method to search k-maximum internally stable sets of graphs

摘要

This paper uses a new matrix analysis tool, the semi-tensor product of matrices (STP), to investigate the problem of searching k-internally stable set (k-ISS) and k-maximum internally stable set (k-MISS) of graphs, which serve as mathematical models of analizing many concrete realworld problems such as the k-track assignment problem. By introducing a characteristic vector for vertex subsets of graphs and using the STP, several new sufficient and necessary conditions of the k-ISS and k-MISS are obtained, based on which an algorithm able to find out all k-ISSs and k-MISSs of graphs is established. The results are quite different from existing methods and provide a new angle and means to understand and analyze the structure of graphs. The correctness of the results is finally examined by several illustration examples.