Matrix Approach to Formulate and Search k-ESS of Graphs Using the STP Theory

Abstract

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.