Matrix approach to formulate and search \(k\)-ESS of graphs using the STP theory (Q2240198)

Summary: In this paper, the structure of graphs in terms of \(k\)-externally stable set (\(k\)-ESS) is investigated by a matrix method based on a new matrix product, called semitensor product of matrices. By defining an eigenvector and an eigenvalue of the node subset of a graph, three necessary and sufficient conditions of \(k\)-ESS, minimum \(k\)-ESS, and \(k\)-kernels of graphs are proposed in a matrix form, respectively. Using these conditions, the concepts of \(k\)-ESS matrix, minimum \(k\)-ESS matrix, and \(k\)-kernel matrix are introduced. These matrices provide complete information of the corresponding structures of a graph. Further, three algorithms are designed, respectively, to find all these three structures of a graph by conducting a series of matrix operation. Finally, the correctness and effectiveness of the results are checked by studying an example. The proposed method and results may offer a new way to investigate the problems related to graph structures in the field of network systems.