# Matrix Approach to Formulate and Searchk-ESS of Graphs Using the STP Theory

Authors: Jumei Yue; Yongyi Yan; He Deng
Journal: Journal of Mathematics
 (2021)

---

## Abstract

In this paper, the structure of graphs in terms ofk-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.


---

## Body

## 1. Introduction

A graph is a figure consisting of nodes and edges; nodes represent things; an edge linking two nodes represents the relationship between the two things. A graph usually describes a specific binary relation between things. And, graph theory is a delightful playground for the exploration of proof techniques in discrete mathematics, and its results have applications in many areas of computing, social, and natural sciences [1]. Interest in graphs and their applications continues to grow rapidly, largely due to the usefulness of graphs as models for computation and optimization [2].An externally stable set (ESS) of a graph is a set of nodes that any node outside of the set is linked with a node in the set. Ak-externally stable set (k-ESS) of a graph is an advanced version of an ESS that any node outside of the set is linked with a node in the set by a path of length k. A kernel of a graph is a set of nodes, that is, both an ESS and internally stable set (ISS). An internally stable set of a graph is a set of nodes where any two nodes are not linked with each other. Similarly, a k-kernel of a graph is an advanced form of a kernel, that is, a k-kernel of a graph is both a k-ESS and a k-internally stable set (k-ISS), where a k-ISS is a set of nodes where any two nodes are not linked with each other by a path of length k. ISS, ESS, kernel, k-ISS, k-ESS, and k-kernels are important modes of describing the structure of graphs.The structure of graphs is a lasting hot topic in graph theory and has been widely discussed in various areas. In the field of novelty detection, Mohammadi et al. [3] used kernel dependence technique to characterize the statistical dependency of the random variable. Previous results mainly use the density assessment method to determine the dependency of random variables and are unable to address high dimension data. This approach uses a kernel of the graph to characterize the dependency and is robust and suitable to problems of arbitrary high dimension data. Bernshtejn and Bozhenyuk [4] proposed the concepts of fuzzy internally stable and fuzzy externally stable sets of a fuzzy directed graph and defined their degrees. By generalizing the approach to discriminate maximal internally stable sets and minimal externally stable sets of an ordinary graph, they developed a method of determining fuzzy internally stable and fuzzy externally stable sets with maximum stability degree. In the analysis of logical networks, Liu et al. [5] applied the graph structure to detect some special states such as observable and unobservable states of Boolean networks. Compared with the methods based on computer algorithms, the advantage of such graph structure-based method is that the observable and unobservable states of Boolean networks can be determined directly. Besides, the structures of graphs are used to many areas such as fault detection [6], network sentiment analysis [7], and decision theory [8].Matrix can be applied in almost every field of natural science. Although traditional matrix multiplication is widely used, it has limitations. In terms of application scope, it can only be used when two matrices meet the equal dimension condition, and it does not meet the commutative law. In terms of the types of problem-solving, it is mainly used to solve linear or bilinear problems. For multilinear and nonlinear problems, it is almost powerless. With the development of computer and nonlinear sciences, a new method able to deal with high-dimensional array is expected.A new matrix multiplication, called semitensor product of matrices (STP), has been developed in recent years [9]. STP extends the traditional multiplication of matrices to any two matrices, which overcome the dimension limitation and keep almost all the important properties of the traditional multiplication. Furthermore, due to the introduction of the swap matrix, STP has some exchangeable properties, called pseudoexchangeability, which overcomes the weakness of commutativity of traditional matrix multiplication to some extent. STP is now well established and has been successfully applied in many fields [10–17].Based on STP, a matrix method of studying the graph structure has been developed. Wang et al. [18] investigated the maximum stable sets and node coloring problems of graphs by using the STP. Several new results and algorithms are presented. The results are useful to consider the network control problems such as group consensus of multiagent systems. Since then, the matrix method has been used to investigate many problems of graphs. Xu et al. [19] continued to consider the coloring of robust graphs by transforming the problem into a type of optimal problem in the framework of the STP and used the matrix method to design an algorithm that can find all the colorings of robust graphs. Further, the timetabling problem is solved by the presented results. In [20, 21], Xu et al. pushed the matrix method to a new level and studied the coloring of fuzzy graphs and the conflict-free coloring problem. Using the matrix method, Zhong et al. [22] investigated the minimum stable sets and cores of graphs; several new theoretic results and algorithms are proposed. These new results provide a way to further consider the optimization of minimum stable sets of graphs and control problems of Boolean control networks such as pinning control. In the hypergraph area, Meng et al. [23] applied the matrix method to investigate the hypergraph coloring. A necessary and sufficient condition of the algebraic inequality form is given, and an algorithm of finding all the coloring schemes of a hypergraph with specific numbers of colors is designed. Yue et al. [24] considered the k-track scheduling problem by investigating the k-ISS of graphs. Two necessary and sufficient conditions and schedulable conditions are developed by using the matrix method.The merits of this matrix method in addressing graph problems are concise mathematical description and clear results. Generally speaking, the problems related to the graph structure can be formulated by matrices, usually called structure matrices. A structure matrix contains all the structure information of a particular class of the graph structure. The embodying of complete structure information provides us a chance to design algorithms to find all the structures of a graph.As far as we know, there has been no report on using the matrix method to investigate thek-ESS and k-kernel structures of graphs. Generally speaking, there are three kinds of ways to consider the graph structures: based on graph theory, mathematical programming and computer algorithm. Most results obtained by these methods, especially by the computer-based algorithms, are inconvenient to explain the structures mathematically and cannot theoretically guarantee to find all the k-ESSes and k-kernels of a graph.Motivated by the above defects of the existing results and the advantages of the matrix method of the investigating graph structure, the aims of this paper are to use the matrix method to consider several more complicated structures of graphs, including thek-ESS, minimum k-ESS, and k-kernel, and to design algebraic algorithms to find all these structures of a given graph.The main contributions of this paper contain two parts, theoretic results and algorithms. The theoretic part includes algebraic formulations of thek-ESS, minimum k-ESS, and k-kernels, which are presented as several necessary and sufficient conditions. The algorithm part consists of three algorithms of finding k-ESS, minimum k-ESS, and k-kernels, respectively. These results can find all these structures of a graph and may provide a new way to consider the structure problems of network systems such as reductions of Boolean networks, dynamic evolution game systems, and finite state machine networks. A disadvantage of the presented algorithms is the memory burden when solved by computers for graphs with more than 20 nodes.The remainder of this paper is organized as follows. Section2 gives some preliminaries on the mathematical tool (STP) and graphs. In Section 3, the main results of this paper are presented, including theoretic and algorithm parts. In Section 4, we analyze the computation complexity of the presented algorithms and discuss the differences between the presented results and existing ones. Section 5 is devoted to examine the correctness of the results. Finally, a concluding remark is given in Section 6.The following are the notations used in this paper.1n/0n: the n×1 vector of all element being 1/0coliA: the ith column of matrix AcolA: the set of all the columns of matrix Aδni: the ith column of the identity matrix InΔn: the set δn1,…,δnnδni1,…,ik: the compactness form of matrix δni1,…,δnikS: the cardinality of set S


## 2. Preliminaries

This section gives some necessary preliminaries on the theoretic basis and research object, namely, STP andk-ESS of graphs, respectively.Definition 1.
(see [9]).(1)
LetX be a row vector of dimension np and Y be a column vector with dimension p. Split X into p equal-size blocks as X1,…,Xp, which are 1×n row vectors. The semitensor product of X and Y, X⋉Y, is defined as(1)X⋉Y=∑i=1pXiyi∈Rn,YT⋉XT=∑i=1pyiXiT∈Rn,whereyi∈R is the ith component of Y.(2)
For any matricesA∈Rm×n and B∈Rp×q, if either n is a factor of p, say, nt=p, or p is a factor of n, say, n=pt, then the semitensor product of A and B, denoted by C=Cij=A⋉B, is defined as follows: C consists of m×q blocks, and each block is defined as(2)Cij=Ai⋉Bj,i=1,2,…,mandj=1,2,…,q,where Ai is the ith row of A and Bj is the jth column of B.Remark 1.
Definition1 is a special case of STP; the generalized definition is defined as A⋉B≔A⊗Is/nB⊗Is/p, where s is the least common multiple of n and p and ⊗ is the Kronecker product. The STP used in this paper is the form of Definition 1.Remark 2.
Ifn=p, Definition 1 reduces to the traditional product of matrices. Therefore, STP is a generalization of the traditional multiplication of matrices. In this paper, the matrix multiplication is defaulted to the STP, and the symbol ⋉ is omitted except for special emphasis needed.Definition 2.
(see [9]). A swap matrix Wm,n is a matrix of size mn×mn; its rows and columns are labelled by index i,j. The rows and columns are organized by the order of multiindex Idj,i;n,m and Idi,j;m,n, respectively. The element at position I,J,i,j is(3)WI,J,i,j=δi,jI,j=1,I=iandJ=j,0,otherwise.Proposition 1.
(see [9]). Let X∈Rm and Y∈Rn; then,(4)Wm,n⋉X⋉Y=Y⋉X,Wn,m⋉Y⋉X=X⋉Y.Definition 3.
(see [25]). The following matrices Ed_latterm,n and Ed_formerm,n are called dummy operators:(5)Ed_latterm,n=In,…,In︸m,Ed_formerm,n=Im,…,Im︸n.
Especially,Ed_latter2,2≔Ed_latter and Ed_former2,2≔Ed_former.Proposition 2.
(see [25]). Let u∈Δm and v∈Δn be two logical vectors; then,(6)Ed_latterm,n⋉u⋉v=v,Ed_formerm,n⋉Wn,m⋉u⋉v=u.Proposition 3.
(see [18]). Let x be a 2-valued logical variable; then,(7)Mnx=x¯,where Mn=δ22,1.Definition 4.
(see [26]). A graph G=V,E is a mathematical structure composed of two finite sets V and E. The elements of V are called nodes, and the elements of E are called edges. Each edge has a set of one or two nodes associated to it, which are called its endpoints.
An edge is said to join its endpoints. A node joined by an edge to a nodevi is said to be a neighbor of vi. In this paper, vi is thought to be a neighbor of itself denoted by Nvi=vj∈V|vj,vi∈E, the neighbor set of vi. A graph P=V′,E′ is called a subgraph of G=V,E if V′⊆V and E′⊆E.Definition 5.
(see [26]). A subgraph P=V′,E′ of G=V,E with the form V′=vi1,vi2,…,vik and E′=vi1,vi2,vi2,vi3,…,vik−1,vk is called a path of G. The number of the edges of a path from vi to vj is called the length of the path, denoted as dvi,vj. dvi,vi=0 if and only if vi=vj.Definition 6.
(see [18]). A set S of nodes of G is called a k-externally stable set (k-ESS) of G if for any node vi∉S, there is a node vj∈S such that vj∈Nvi. A k-ESS S is called a minimum k-ESS if any proper subset of S is not a k-ESS. A minimum k-ESS with the least number of nodes is called an absolutely minimum k-ESS; the number of nodes of an absolutely minimum k-ESS is called the k-externally stable number of G, denoted by αG.Definition 7.
(see [27]). For two matrices A=aijp×q and B=bijq×r, their Boolean product C=A×ℬB=cijp×r is defined as(8)cij=∨l=1qail∧blj,where ∨ and ∧ are the operations of “logic Or” and “logic And”, respectively. The Boolean power of A is defined as(9)A0ℬ=A,Akℬ=Ak−1ℬ×ℬA,k=1,2,….Definition 8.
(see [25]). For graph G=V,E, V=v1,v2,…,vn, the matrix A=aij is called its adjacency matrix (AM), where(10)aij=1,ifvi,vj∈E,0,otherwise.
Thek-adjacency matrix (k-AM) of G is defined as follows:(11)Ak=A∨A2ℬ∨…∨Akℬ,where(i)
Aiℬ denotes the Boolean power of A(ii)
A∨B=aij∨bijm×n


## 3. Main Results

In this section, we present the main results of the paper, including theoretic and algorithm results. The theoretic part contains matrix formulations ofk-ESS, minimum k-ESS, and k-kernels of graphs. The algorithm part consists of algebraic algorithms of finding all the k-ESSes, minimum k-ESSes, and k-kernels of a graph.


### 3.1. Onk-ESS

Definition 9.
(see [18]). Given a node subset S⊆V of graph G=V,E, the eigenvector of S, denoted by VS=x1,x2,…,xn, is(12)xi=1,xi∈S,0,xi∉S.
Using STP, we define the eigenvalue of a node subset of a graph. An eigenvalue and the corresponding node subset are uniquely determined by each other.Definition 10.
LetVS=x1,x2,…,xn be the eigenvector of a node subset S⊆V of graph G=V,E, and let us define yi=xi,1−xiT, i=1,2,…,n. The eigenvalue of S is defined as(13)YS=⋉i=1nyi.Remark 3.
Because thatyii=1,2,…,n can be uniquely obtained by calculating yi=Sin⋉YS, where Sin is given in (22), and that the yii=1,2,…,n uniquely determines YS, the eigenvalue YS of S uniquely determines the eigenvector VS, and vice versa. Thus, if YS (or VS) is given, then VS (or YS) can be determined. Consequently, the node subset S is obtained.Proposition 4.
LetAk=aijk be the k-AM of graph G=V,E, V=v1,v2,…,vn. The length of a path from node vi to vj is less than or equal to k, i.e., dvi,vj≤k, if and only if aijk=1.Proof.
ConsiderAlℬ=aijl, 1≤l≤k. It follows from (4) that(14)aijl=∨i1,…,ilaii1∧ai1i2∧…∧ail−1j.
It is obvious thataijl=1 if and only if there are l−1 subscripts i1,i2,…,il−1 such that(15)aii1=ai1i2=⋯=ail−1j=1.
Combining (15) with (5), we get that there is an edge between vi and vi1, vi1 and vi2, …, and vil−1 and vj, respectively. Therefore, aijl=1 if and only if vi and vj are linked by a path of length dvi,vj≤l. dvi,vj=l if and only if i,i1,i2,…,il−1,j are different from each other.
ForAk=aijk, aijk=aij1∨aij2∨…∨aijk=1 holds if and only if there exists an l1≤l≤k such that aijl=1. And, aijl=1 if and only if vi and vj are linked by a path of length dvi,vj≤l; thus, aijk=1 if and only if there is a path of length dvi,vj≤k from node vi to vj.Theorem 1.
LetAk=aijk be the k-AM of graph G=V,E, V=v1,v2,…,vn. G has a k-ESS if and only if there exists a 1≤j≤2n such that(16)coljM=1n,where(17)M=M1M2⋮Mn,Mi=J⋉∑i=1naijkQj,i=1,2,…,n,J=1,0,Qj=Ed_lattern−j⋉W2,2n−j⋉Ed_latterj−1.Proof.
We first prove the necessity. SupposeS is a k-ESS of G. Let VS=x1,x2,…,xn be the eigenvector of S. From Proposition 4 and the definition of k-ESS of a graph, we get that, for vi not in S, there exists a j1≤j≤n such that(18)aijk=1,xj=1.
Equation (18) implies that(19)xi∨∨j=1naijkxj=1.
Using (10) and (19), it can be re-expressed as follows:(20)∨j=1naijkxj=1.
Becauseaij and xj are either 1 or 0, (20) is equivalent to(21)∑j=1naijkxj=1.
Letyj=xj,1−xjT,j=1,2,…,n. It follows from (6) that(22)yj=Ed_lattern−j⋉yj+1⋉yj+2⋉⋯⋉yn⋉yj=Ed_lattern−j⋉W2,2n−j⋉yj⋉yj+1⋉⋯⋉yn=Ed_lattern−j⋉W2,2n−j⋉Ed_latterj−1⋉y1⋉⋯⋉yn⋮=Qj⋉YS,where Qj=Ed_lattern−j⋉W2,2n−j⋉Ed_latterj−1.
It is evident that(23)xj=J⋉yj,aijkxj=aijkJ⋉yj=aijkJ⋉Qj⋉YS.
By (21), we know that(24)∑j=1naijkxj=J⋉∑j=1naijkQj⋉YS≔Mi⋉YS,where Mi=J⋉∑j=1naijkQj.
Therefore, the following statements are equivalent to each other fori∈1,2,…,n:(25)i∑j=1naijkxj=1,iiMi⋉YS=1,iiiThere exists anl:collMi=1n,ivThere exists a1≤j≤2n:coljMi=1n.
Note that (21) is equivalent to the following equations:(26)∑j=1na1jkxj=1,∑j=1na2jkxj=1,⋮∑j=1nanjkxj=1.
Equations (26) are solvable if and only if there exists a 1≤j≤2n such that(27)coljM=1n,where(28)M=M1M2⋮Mn.
Obviously, (21) is equivalent to (26); then, the necessity is proved.
We next show the sufficiency. Because the derivation process from equations (18) to (26) is reversible mathematically, according to Proposition 4 and the definition of k-ESS of a graph, the sufficiency holds. The proof is then completed.
Theorem1 gives the condition that a graph contains a k-ESS. Based on the condition, we further establish a rule to judge whether a given node subset is a k-ESS or not.Theorem 2.
LetAk=aijk be the k-AM of graph G=V,E. For a given S⊆V, suppose that the eigenvector and eigenvalue of S are VS=x1,x2,…,xn and YS=δ2nk, respectively. Then, S is a k-ESS of G if and only if(29)colkM=1n,where(30)M=M1M2⋮Mn,Mi=J⋉∑i=1naijkQj,i=1,2,…,n,J=1,0,Qj=Ed_lattern−j⋉W2,2n−j⋉Ed_latterj−1.Proof.
Comparison of (29) with (16) suggests that it is only needed to prove that(31)colkM=1n,that is,(32)colkMi=1,i=1,2,…,n.
It follows from (25) that Mi⋉Ys=1 is equivalent to there exists a 1≤j≤2n such that coljMi=1. Consequently, we only need to show that k satisfies the condition.
Taking notice of the sizes ofMi and YS, they are of dimension 1×2n and 2n×1, respectively. In such a situation, STP coincides with the traditional product of matrices. It is clear that Mi⋉YS is just colkMi.
Therefore,Mi⋉YS=1 if and only if colkMi=1. This proves (32) and completes the proof of Theorem 2.Remark 4.
The matrixM of (16) or (29) gives a complete picture for all of the k-ESSes of a graph. We thus propose the following definition.Definition 11.
The matrixM in (16) or (29) is called the k-ESS matrix of graph G.
According to Remark3 and the proof of Theorem 2, the following Corollary 1 is clearly true.Corollary 1.
LetM be the k-ESS matrix of graph G=V,E. Then, there is a one-to-one correspondence between the k-ESSes of G and the solutions of the following equation:(33)M⋉i=1nyi=1n,where yi=xi,1−xiT, xi∈D=0,1, is a 2-valued variable assigned to each vertex vi∈V.
Corollary1 provides a way to obtain all the k-ESSes of a given graph.Algorithm 1.
LetAk=aijk be the k-AM of graph G=V,E. Assign each node vi∈V a 2-valued variable xi∈D=0,1 and define yi=xi,1−xiT. To find all the k-ESSes and minimum k-ESSes of G, one can take the following procedure.Step 1. Compute the k-ESS matrix M of G.Step 2. Check if there is a column being 1n in colM. If not, there is no k-ESS in G and then the algorithm ends. Otherwise, construct the set(34)K=l|collM=1n.Step 3. For each l in K, compute yi=Sin⋉δ2nl, i=1,2,…,n, where(35)S1n=δ21…1︸2n−12…2︸2n−1,S2n=δ21…1︸2n−22…2︸2n−21…1︸2n−22…2︸2n−2,⋮Snn=δ212︸2…12︸2︸2n−1.Step 4. Choose yi=δ21 and construct a set Sl=vi|yi=δ21. Sl is a k-ESS of G. All the k-ESSes of G are Sl|l∈K.Step 5. The k-externally stable number of G is αG=minl∈KSl. All the minimum k-ESSes of G are ζ=Sl|Sl=αG.Remark 5.
Algorithm1 produces all the k-ESSes of a graph. Naturally, the k-ESSes of some characteristics can also be obtained. For instance, each of the nodes outside a k-ESS is connected with the k-ESS once or exactly k times, etc. In a word, Algorithm 1 provides us a picture of the structure of graphs by producing all the k-ESSes.


### 3.2. On Minimumk-ESS

Theorem 3.
LetAk=aijk be the k-AM of graph G=V,E. And, let VS=x1,x2,…,xn and YS=⋉i=1nyi=δ2nk be the eigenvector and eigenvalue of a subset S⊆V, where yi=xi,1−xiT. Then, S is a minimum k-ESS of G if and only if(36)colkM=0n,where(37)M=JQi−n2Jn−1MnEd_latter∑j=1na¯ijk,J=1,0,Qi=Ed_lattern−iW2,2n−iEd_latteri−1,
Mn is given in Proposition 3; a¯ijk=1−aijk.Proof.
We first show the necessity. LetVS=x1,x2,…,xn be the eigenvector of the minimum k-ESS S. There are two cases to be discussed.Case (i):xi=0. In this situation, it follows from (21) that(38)∑j=1j≠inaijkxj=1.Case (ii):xi=1. We can prove that(39)∑j=1j≠inaijkxj=0.
If (39) is false, i.e.,(40)∑j=1j≠inaijkxj=1,then according to Theorem 1, the node subset corresponding to VS=x1,…xi−1,0,xi+1,…,xn is a k-ESS too, i.e.,(41)S′=v1,…,vi−1,vi+1,…,vn,is a k-ESS of G.
This is in contradiction with thatS=v1,…,vi,…,vn is a minimum k-ESS of G. Thus, (39) is true. We then get that(42)xi=∑j=1na¯ijk∧j=1j≠inx¯j,where a¯ijk=1−aijk.
It follows from (22) that(43)xi=Jyi=JEd_lattern−jW2,2n−jEd_latterj−1YS=JQiYS,where Qi=Ed_lattern−jW2,2n−jEd_latterj−1.
On the contrary, using Propositions2 and 3, we have(44)∑j=1na¯ijk∧j=1j≠iny¯j=∑j=1na¯ijk∧j=1j≠inMnyj=∑j=1na¯ijkMn∧j=1j≠inyj=nMn∑j=1na¯ijk∧j=1j≠inyj=nMn∑j=1na¯ijkEd_latteryi∧j=1j≠inyj=nMn∑j=1na¯ijkEd_latter∧j=1nyj=nMn∑j=1na¯ijkEd_latterYs=n2MnEd_latter∑j=1na¯ijkYs.
Submitting (44), (43), and xj=Jyj into (42), we get(45)JQi−n2Jn−1MnEd_latter∑j=1na¯ijk.
The necessity is proved.
Sufficiency: suppose (36) is true; then, according to the reversibility of the derivation process from equations (42) to (44), the eigenvector of S, Vs=x1,x2,…,xn, meets the conditions of (38) and (39).
Ifx1=x2=⋯=xn=1, then(46)∑j=1naijkxj≥∑j=1najjk=1,thus S is a k-ESS of G.
If there exists axi=0, then(47)∑j=1naijkxj=∑j=1j≠inaijkxj=1.
It follows from (26) that S is a k-ESS of G.
Next, we show thatS is a minimum k-ESS. If we delete any vertex, say xi, from S, denote the new subset by S′; then, the eigenvector of S′ is VS′=x1,…,xi−1,0,xi+1,…,xn. Because vi∈S and xi=1, we get from (39) that(48)∑j=1j≠inaijkxj=0,and then,(49)coljM=0n.
This suggests that the subsetVS′=x1,…,xi−1,0,xi+1,…,xn is unsatisfied with condition (9). Thus, S′ is not a k-ESS of G. Consequently, S is a minimum k-ESS of G. This proves the sufficiency, and the proof of Theorem 3 is completed.
Using the minimization of pseudo-Boolean functions (PBFs), the problem of finding all the minimumk-ESSes of a graph can also be solved. The following proposition is needed.Proposition 5.
(see [28]). For a PBF fx1,x2,…,xn under the constraints,(50)fjx1,x2,…,xn=0,j=1,2,…,m,where fj are nonnegative integer-valued PBFs. Use S+ and S− to denote the sum of positive and negative coefficients of f, respectively. Construct the following PBF:(51)Fx1,x2,…,xn=fx1,x2,…,xn+S+−S−+1∑j=1mfjx1,x2,…,xn.
The following statements hold.(i)
Supposex1∗,x2∗,…,xn∗ is a local minimum point of PBF f with constraint (50); then, x1∗,x2∗,…,xn∗ is also a local minimum point of PBF F(ii)
Supposex1∗,x2∗,…,xn∗ is a local minimum point of PBF Fand Fx1∗,x2∗,…,xn∗≤S+; then x1∗,x2∗,…,xn∗ is also a local minimum point of PBF f with constraint (50)Theorem 4.
LetAk=aijk be the k-AM of graph G=V,E. For a given subset S⊆V, suppose its eigenvector and eigenvalue are VS=x1,x2,…,xn and YS=⋉i=1nyi=δ2nk, respectively, where yi=xi,1−xiT. Then, S is a minimum k-ESS of G if and only if the kth component of M is a minimum one in the set of nonnegative components, where(52)M=J∑i=1nQi+n+1∑j=1n∑i=1naijkQi,in which J=1,0 and Qi=Ed_lattern−iW2,2n−iEd_latteri−1.Proof.
It follows from the proof of Theorem1 that the eigenvector of a minimum k-ESS of G is a local minimum point of PBF hx1,x2,…,xn=∑i=1nxi under constraint (20). Applying Proposition 5, here, S+=n and S−=0, to the minimization problem, we only need to investigate the following minimization problem:(53)fx1,x2,…,xn=∨i=1nxi∨n+1∨i=1n∨i=1naijkxj.
Because bothxii=1,2,…,n and aij only take values 0 and 1, (53) amounts to the following PBF:(54)fx1,x2,…,xn=∑i=1nxi+n+1∑j=1n∑i=1naijkxj.
According to (22), (23), (24), and (54) can be represented in the following form:(55)fy1,y2,…,yn=J∑i=1nQiYS+n+1∑j=1n∑i=1naijkQiYS=J∑i=1nQi+n+1∑j=1n∑i=1naijkQiYS≔MYS,where(56)M=J∑i=1nQi+n+1∑j=1n∑i=1naijkQi,J=1,0,Qi=Ed_lattern−iW2,2n−iEd_latteri−1,yi=xi,1−xiT,YS=⋉i=1nyi.
Now, it is easy to see from the eigenvalue ofS, YS=⋉i=1nyi=δ2nk, that the k-th component of M is the minimum value of PBFs (53) and (54). This completes the proof of Theorem 4.
Similarly to Definition11, we define the matrix M of (52) as the minimum k-ESS matrix of a graph.Definition 12.
The matrixM of (52) in Theorem 4 is called the minimum k-ESS matrix of graph G.Remark 6.
The minimumk-ESS matrix of a graph offers us a way to find all the minimum k-ESSes of a graph in a matrix manner. Similarly to Algorithm 1, the following algorithm can produce all the minimum k-ESSes of a given graph.Algorithm 2.
LetAk=aijk be the k-AM of a given graph G=V,E. Assign each vi∈V a 2-valued variable xi∈D=0,1 and define yi=xi,1−xiT. To get all the minimum k-ESSes of G, one can take the following steps.Step 1. Compute the minimum k-ESS matrix of G, denoted by M.Step 2. Check whether there is a nonnegative component in M; if not, G has no minimum k-ESS and the algorithm terminates here. Otherwise, set(57)K=l|thel−th component ofMis a minimum one.Step 3. For each l in K, compute yi=Sin⋉δ2nl, i=1,2,…,n, where(58)S1n=δ21…1︸2n−12…2︸2n−1,S2n=δ21…1︸2n−22…2︸2n−21…1︸2n−22…2︸2n−2,⋮Snn=δ212︸2…12︸2︸2n−1.Step 4. Choose yi=δ21 and construct Sl=vi|yi=δ21. Sl is a minimum k-ESS of G. All the minimum k-ESSes of G are {Sl|l∈K, Sl is produced by Step 3 and Step 4}


### 3.3. Further Results onk-Kernels

Thek-kernels of a graph play a key role in describing the structures of graphs and have a wide application prospect in the network systems [29]. A subset S of nodes of a graph G is called a k-kernel if S is both a k-ESS and a k-internally stable set (k-ISS) of G. Yue and Yan [24] considered the algebraic formulation of k-ISS of graphs in the framework of STP and proposed the matrix form of the necessary and sufficient condition of k-ISS. Integrating the results with those of this paper, we expand the results of the k-ESS and minimum k-ESS to the k-kernels of graphs.Proposition 6.
(see [24]). Let Ak=aijk be the k-AM of graph G=V,E, where V=v1,v2,…,vn. There is a k-ISS in G if and only if matrix N contains a column coljN=0n, 1≤j≤2n, where(59)N=N1N2⋮Nn,Ni=Q∑j=1naijPij,i=1,2,…,n,Q=1,0,0,0,Pij=Ed_lattern−2⋉W2j,2n−j⋉W2i,2j−i−1.Proposition 7.
(see [24]). Let Ak=aijk be the k-AM of graph G=V,E, where V=v1,v2,…,vn; and, let VS=x1,x2,…,xn and YS=⋉i=1nyi=δ2nk be the eigenvector and eigenvalue of a subset S⊆V, where yi=xi,xi¯T. Then, S is a k-ISS of G if and only if colkN=0n, where N is given in Proposition 6.
Based on Propositions6 and 7 and Theorems 1 and 2, it follows from the definition of the k-kernel that the following results are true.Corollary 2.
LetAk=aijk be the k-AM of graph G=V,E, where V=v1,v2,…,vn. Then, G has a k-kernel if and only if there exists a 1≤j≤2n such that(60)coljM=1n,coljN=0n,where M and N are given in Theorem 1 and Proposition 6, respectively.Corollary 3.
LetAk=aijk be the k-AM of graph G=V,E. For a given node subset S⊆V, the eigenvector and eigenvalue are VS=x1,x2,…,xn and YS=⋉i=1nyi=δ2nk, respectively, where yi=xi,1−xiT. Then, S is a k-kernel G if and only if(61)colkM=1n,colkN=0n,where M and N are given in Corollary 2.Remark 7.
It is clear fromCorollaries 2 and 3 that the matrices M and N of Corollary 3 provide the complete information of all the k-kernels of a graph. We use them to define the concepts of the k-kernel matrix of a graph.Definition 13.
Thek-kernel matrix of the graph G described in Corollary 3 is the following matrix K:(62)K=MN,in which M and N are given in Corollary 3.
Based on Corollary3, we can design an algorithm to find all the k-kernels of a graph.Algorithm 3.
For the graph described in Corollary3, give each vi∈V a 2-valued variable xi∈D=0,1 and define yi=xi,1−xiT. To find all the k-kernels of the graph, one can take the following steps.Step 1. Compute the k-kernel matrix K of G.Step 2. Rewrite K as the form of K=MN shown in Corollary 3.Step 3. Check whether there is a 1n in colM. If not, there is no k-kernel in G and the algorithm ends here. Otherwise, go to the next step.Step 4. Check whether there is a 0n in colN. If not, there is no k-kernel in G and the algorithm ends. Otherwise, set(63)R=l|collM=1n,collN=0n.Step 5. For each l in R, compute yi=Sin⋉δ2nl, i=1,2,…,n, where(64)S1n=δ21…1︸2n−12…2︸2n−1,S2n=δ21…1︸2n−22…2︸2n−21…1︸2n−22…2︸2n−2,⋮Snn=δ212︸2…12︸2︸2n−1.Step 6. Pick out yi=δ21, and set Sl=vi|yi=δ21. Sl is a k-kernel of G. All the k-kernels of G are Sl|l∈K.


## 3.1. Onk-ESS

Definition 9.
(see [18]). Given a node subset S⊆V of graph G=V,E, the eigenvector of S, denoted by VS=x1,x2,…,xn, is(12)xi=1,xi∈S,0,xi∉S.
Using STP, we define the eigenvalue of a node subset of a graph. An eigenvalue and the corresponding node subset are uniquely determined by each other.Definition 10.
LetVS=x1,x2,…,xn be the eigenvector of a node subset S⊆V of graph G=V,E, and let us define yi=xi,1−xiT, i=1,2,…,n. The eigenvalue of S is defined as(13)YS=⋉i=1nyi.Remark 3.
Because thatyii=1,2,…,n can be uniquely obtained by calculating yi=Sin⋉YS, where Sin is given in (22), and that the yii=1,2,…,n uniquely determines YS, the eigenvalue YS of S uniquely determines the eigenvector VS, and vice versa. Thus, if YS (or VS) is given, then VS (or YS) can be determined. Consequently, the node subset S is obtained.Proposition 4.
LetAk=aijk be the k-AM of graph G=V,E, V=v1,v2,…,vn. The length of a path from node vi to vj is less than or equal to k, i.e., dvi,vj≤k, if and only if aijk=1.Proof.
ConsiderAlℬ=aijl, 1≤l≤k. It follows from (4) that(14)aijl=∨i1,…,ilaii1∧ai1i2∧…∧ail−1j.
It is obvious thataijl=1 if and only if there are l−1 subscripts i1,i2,…,il−1 such that(15)aii1=ai1i2=⋯=ail−1j=1.
Combining (15) with (5), we get that there is an edge between vi and vi1, vi1 and vi2, …, and vil−1 and vj, respectively. Therefore, aijl=1 if and only if vi and vj are linked by a path of length dvi,vj≤l. dvi,vj=l if and only if i,i1,i2,…,il−1,j are different from each other.
ForAk=aijk, aijk=aij1∨aij2∨…∨aijk=1 holds if and only if there exists an l1≤l≤k such that aijl=1. And, aijl=1 if and only if vi and vj are linked by a path of length dvi,vj≤l; thus, aijk=1 if and only if there is a path of length dvi,vj≤k from node vi to vj.Theorem 1.
LetAk=aijk be the k-AM of graph G=V,E, V=v1,v2,…,vn. G has a k-ESS if and only if there exists a 1≤j≤2n such that(16)coljM=1n,where(17)M=M1M2⋮Mn,Mi=J⋉∑i=1naijkQj,i=1,2,…,n,J=1,0,Qj=Ed_lattern−j⋉W2,2n−j⋉Ed_latterj−1.Proof.
We first prove the necessity. SupposeS is a k-ESS of G. Let VS=x1,x2,…,xn be the eigenvector of S. From Proposition 4 and the definition of k-ESS of a graph, we get that, for vi not in S, there exists a j1≤j≤n such that(18)aijk=1,xj=1.
Equation (18) implies that(19)xi∨∨j=1naijkxj=1.
Using (10) and (19), it can be re-expressed as follows:(20)∨j=1naijkxj=1.
Becauseaij and xj are either 1 or 0, (20) is equivalent to(21)∑j=1naijkxj=1.
Letyj=xj,1−xjT,j=1,2,…,n. It follows from (6) that(22)yj=Ed_lattern−j⋉yj+1⋉yj+2⋉⋯⋉yn⋉yj=Ed_lattern−j⋉W2,2n−j⋉yj⋉yj+1⋉⋯⋉yn=Ed_lattern−j⋉W2,2n−j⋉Ed_latterj−1⋉y1⋉⋯⋉yn⋮=Qj⋉YS,where Qj=Ed_lattern−j⋉W2,2n−j⋉Ed_latterj−1.
It is evident that(23)xj=J⋉yj,aijkxj=aijkJ⋉yj=aijkJ⋉Qj⋉YS.
By (21), we know that(24)∑j=1naijkxj=J⋉∑j=1naijkQj⋉YS≔Mi⋉YS,where Mi=J⋉∑j=1naijkQj.
Therefore, the following statements are equivalent to each other fori∈1,2,…,n:(25)i∑j=1naijkxj=1,iiMi⋉YS=1,iiiThere exists anl:collMi=1n,ivThere exists a1≤j≤2n:coljMi=1n.
Note that (21) is equivalent to the following equations:(26)∑j=1na1jkxj=1,∑j=1na2jkxj=1,⋮∑j=1nanjkxj=1.
Equations (26) are solvable if and only if there exists a 1≤j≤2n such that(27)coljM=1n,where(28)M=M1M2⋮Mn.
Obviously, (21) is equivalent to (26); then, the necessity is proved.
We next show the sufficiency. Because the derivation process from equations (18) to (26) is reversible mathematically, according to Proposition 4 and the definition of k-ESS of a graph, the sufficiency holds. The proof is then completed.
Theorem1 gives the condition that a graph contains a k-ESS. Based on the condition, we further establish a rule to judge whether a given node subset is a k-ESS or not.Theorem 2.
LetAk=aijk be the k-AM of graph G=V,E. For a given S⊆V, suppose that the eigenvector and eigenvalue of S are VS=x1,x2,…,xn and YS=δ2nk, respectively. Then, S is a k-ESS of G if and only if(29)colkM=1n,where(30)M=M1M2⋮Mn,Mi=J⋉∑i=1naijkQj,i=1,2,…,n,J=1,0,Qj=Ed_lattern−j⋉W2,2n−j⋉Ed_latterj−1.Proof.
Comparison of (29) with (16) suggests that it is only needed to prove that(31)colkM=1n,that is,(32)colkMi=1,i=1,2,…,n.
It follows from (25) that Mi⋉Ys=1 is equivalent to there exists a 1≤j≤2n such that coljMi=1. Consequently, we only need to show that k satisfies the condition.
Taking notice of the sizes ofMi and YS, they are of dimension 1×2n and 2n×1, respectively. In such a situation, STP coincides with the traditional product of matrices. It is clear that Mi⋉YS is just colkMi.
Therefore,Mi⋉YS=1 if and only if colkMi=1. This proves (32) and completes the proof of Theorem 2.Remark 4.
The matrixM of (16) or (29) gives a complete picture for all of the k-ESSes of a graph. We thus propose the following definition.Definition 11.
The matrixM in (16) or (29) is called the k-ESS matrix of graph G.
According to Remark3 and the proof of Theorem 2, the following Corollary 1 is clearly true.Corollary 1.
LetM be the k-ESS matrix of graph G=V,E. Then, there is a one-to-one correspondence between the k-ESSes of G and the solutions of the following equation:(33)M⋉i=1nyi=1n,where yi=xi,1−xiT, xi∈D=0,1, is a 2-valued variable assigned to each vertex vi∈V.
Corollary1 provides a way to obtain all the k-ESSes of a given graph.Algorithm 1.
LetAk=aijk be the k-AM of graph G=V,E. Assign each node vi∈V a 2-valued variable xi∈D=0,1 and define yi=xi,1−xiT. To find all the k-ESSes and minimum k-ESSes of G, one can take the following procedure.Step 1. Compute the k-ESS matrix M of G.Step 2. Check if there is a column being 1n in colM. If not, there is no k-ESS in G and then the algorithm ends. Otherwise, construct the set(34)K=l|collM=1n.Step 3. For each l in K, compute yi=Sin⋉δ2nl, i=1,2,…,n, where(35)S1n=δ21…1︸2n−12…2︸2n−1,S2n=δ21…1︸2n−22…2︸2n−21…1︸2n−22…2︸2n−2,⋮Snn=δ212︸2…12︸2︸2n−1.Step 4. Choose yi=δ21 and construct a set Sl=vi|yi=δ21. Sl is a k-ESS of G. All the k-ESSes of G are Sl|l∈K.Step 5. The k-externally stable number of G is αG=minl∈KSl. All the minimum k-ESSes of G are ζ=Sl|Sl=αG.Remark 5.
Algorithm1 produces all the k-ESSes of a graph. Naturally, the k-ESSes of some characteristics can also be obtained. For instance, each of the nodes outside a k-ESS is connected with the k-ESS once or exactly k times, etc. In a word, Algorithm 1 provides us a picture of the structure of graphs by producing all the k-ESSes.


## 3.2. On Minimumk-ESS

Theorem 3.
LetAk=aijk be the k-AM of graph G=V,E. And, let VS=x1,x2,…,xn and YS=⋉i=1nyi=δ2nk be the eigenvector and eigenvalue of a subset S⊆V, where yi=xi,1−xiT. Then, S is a minimum k-ESS of G if and only if(36)colkM=0n,where(37)M=JQi−n2Jn−1MnEd_latter∑j=1na¯ijk,J=1,0,Qi=Ed_lattern−iW2,2n−iEd_latteri−1,
Mn is given in Proposition 3; a¯ijk=1−aijk.Proof.
We first show the necessity. LetVS=x1,x2,…,xn be the eigenvector of the minimum k-ESS S. There are two cases to be discussed.Case (i):xi=0. In this situation, it follows from (21) that(38)∑j=1j≠inaijkxj=1.Case (ii):xi=1. We can prove that(39)∑j=1j≠inaijkxj=0.
If (39) is false, i.e.,(40)∑j=1j≠inaijkxj=1,then according to Theorem 1, the node subset corresponding to VS=x1,…xi−1,0,xi+1,…,xn is a k-ESS too, i.e.,(41)S′=v1,…,vi−1,vi+1,…,vn,is a k-ESS of G.
This is in contradiction with thatS=v1,…,vi,…,vn is a minimum k-ESS of G. Thus, (39) is true. We then get that(42)xi=∑j=1na¯ijk∧j=1j≠inx¯j,where a¯ijk=1−aijk.
It follows from (22) that(43)xi=Jyi=JEd_lattern−jW2,2n−jEd_latterj−1YS=JQiYS,where Qi=Ed_lattern−jW2,2n−jEd_latterj−1.
On the contrary, using Propositions2 and 3, we have(44)∑j=1na¯ijk∧j=1j≠iny¯j=∑j=1na¯ijk∧j=1j≠inMnyj=∑j=1na¯ijkMn∧j=1j≠inyj=nMn∑j=1na¯ijk∧j=1j≠inyj=nMn∑j=1na¯ijkEd_latteryi∧j=1j≠inyj=nMn∑j=1na¯ijkEd_latter∧j=1nyj=nMn∑j=1na¯ijkEd_latterYs=n2MnEd_latter∑j=1na¯ijkYs.
Submitting (44), (43), and xj=Jyj into (42), we get(45)JQi−n2Jn−1MnEd_latter∑j=1na¯ijk.
The necessity is proved.
Sufficiency: suppose (36) is true; then, according to the reversibility of the derivation process from equations (42) to (44), the eigenvector of S, Vs=x1,x2,…,xn, meets the conditions of (38) and (39).
Ifx1=x2=⋯=xn=1, then(46)∑j=1naijkxj≥∑j=1najjk=1,thus S is a k-ESS of G.
If there exists axi=0, then(47)∑j=1naijkxj=∑j=1j≠inaijkxj=1.
It follows from (26) that S is a k-ESS of G.
Next, we show thatS is a minimum k-ESS. If we delete any vertex, say xi, from S, denote the new subset by S′; then, the eigenvector of S′ is VS′=x1,…,xi−1,0,xi+1,…,xn. Because vi∈S and xi=1, we get from (39) that(48)∑j=1j≠inaijkxj=0,and then,(49)coljM=0n.
This suggests that the subsetVS′=x1,…,xi−1,0,xi+1,…,xn is unsatisfied with condition (9). Thus, S′ is not a k-ESS of G. Consequently, S is a minimum k-ESS of G. This proves the sufficiency, and the proof of Theorem 3 is completed.
Using the minimization of pseudo-Boolean functions (PBFs), the problem of finding all the minimumk-ESSes of a graph can also be solved. The following proposition is needed.Proposition 5.
(see [28]). For a PBF fx1,x2,…,xn under the constraints,(50)fjx1,x2,…,xn=0,j=1,2,…,m,where fj are nonnegative integer-valued PBFs. Use S+ and S− to denote the sum of positive and negative coefficients of f, respectively. Construct the following PBF:(51)Fx1,x2,…,xn=fx1,x2,…,xn+S+−S−+1∑j=1mfjx1,x2,…,xn.
The following statements hold.(i)
Supposex1∗,x2∗,…,xn∗ is a local minimum point of PBF f with constraint (50); then, x1∗,x2∗,…,xn∗ is also a local minimum point of PBF F(ii)
Supposex1∗,x2∗,…,xn∗ is a local minimum point of PBF Fand Fx1∗,x2∗,…,xn∗≤S+; then x1∗,x2∗,…,xn∗ is also a local minimum point of PBF f with constraint (50)Theorem 4.
LetAk=aijk be the k-AM of graph G=V,E. For a given subset S⊆V, suppose its eigenvector and eigenvalue are VS=x1,x2,…,xn and YS=⋉i=1nyi=δ2nk, respectively, where yi=xi,1−xiT. Then, S is a minimum k-ESS of G if and only if the kth component of M is a minimum one in the set of nonnegative components, where(52)M=J∑i=1nQi+n+1∑j=1n∑i=1naijkQi,in which J=1,0 and Qi=Ed_lattern−iW2,2n−iEd_latteri−1.Proof.
It follows from the proof of Theorem1 that the eigenvector of a minimum k-ESS of G is a local minimum point of PBF hx1,x2,…,xn=∑i=1nxi under constraint (20). Applying Proposition 5, here, S+=n and S−=0, to the minimization problem, we only need to investigate the following minimization problem:(53)fx1,x2,…,xn=∨i=1nxi∨n+1∨i=1n∨i=1naijkxj.
Because bothxii=1,2,…,n and aij only take values 0 and 1, (53) amounts to the following PBF:(54)fx1,x2,…,xn=∑i=1nxi+n+1∑j=1n∑i=1naijkxj.
According to (22), (23), (24), and (54) can be represented in the following form:(55)fy1,y2,…,yn=J∑i=1nQiYS+n+1∑j=1n∑i=1naijkQiYS=J∑i=1nQi+n+1∑j=1n∑i=1naijkQiYS≔MYS,where(56)M=J∑i=1nQi+n+1∑j=1n∑i=1naijkQi,J=1,0,Qi=Ed_lattern−iW2,2n−iEd_latteri−1,yi=xi,1−xiT,YS=⋉i=1nyi.
Now, it is easy to see from the eigenvalue ofS, YS=⋉i=1nyi=δ2nk, that the k-th component of M is the minimum value of PBFs (53) and (54). This completes the proof of Theorem 4.
Similarly to Definition11, we define the matrix M of (52) as the minimum k-ESS matrix of a graph.Definition 12.
The matrixM of (52) in Theorem 4 is called the minimum k-ESS matrix of graph G.Remark 6.
The minimumk-ESS matrix of a graph offers us a way to find all the minimum k-ESSes of a graph in a matrix manner. Similarly to Algorithm 1, the following algorithm can produce all the minimum k-ESSes of a given graph.Algorithm 2.
LetAk=aijk be the k-AM of a given graph G=V,E. Assign each vi∈V a 2-valued variable xi∈D=0,1 and define yi=xi,1−xiT. To get all the minimum k-ESSes of G, one can take the following steps.Step 1. Compute the minimum k-ESS matrix of G, denoted by M.Step 2. Check whether there is a nonnegative component in M; if not, G has no minimum k-ESS and the algorithm terminates here. Otherwise, set(57)K=l|thel−th component ofMis a minimum one.Step 3. For each l in K, compute yi=Sin⋉δ2nl, i=1,2,…,n, where(58)S1n=δ21…1︸2n−12…2︸2n−1,S2n=δ21…1︸2n−22…2︸2n−21…1︸2n−22…2︸2n−2,⋮Snn=δ212︸2…12︸2︸2n−1.Step 4. Choose yi=δ21 and construct Sl=vi|yi=δ21. Sl is a minimum k-ESS of G. All the minimum k-ESSes of G are {Sl|l∈K, Sl is produced by Step 3 and Step 4}


## 3.3. Further Results onk-Kernels

Thek-kernels of a graph play a key role in describing the structures of graphs and have a wide application prospect in the network systems [29]. A subset S of nodes of a graph G is called a k-kernel if S is both a k-ESS and a k-internally stable set (k-ISS) of G. Yue and Yan [24] considered the algebraic formulation of k-ISS of graphs in the framework of STP and proposed the matrix form of the necessary and sufficient condition of k-ISS. Integrating the results with those of this paper, we expand the results of the k-ESS and minimum k-ESS to the k-kernels of graphs.Proposition 6.
(see [24]). Let Ak=aijk be the k-AM of graph G=V,E, where V=v1,v2,…,vn. There is a k-ISS in G if and only if matrix N contains a column coljN=0n, 1≤j≤2n, where(59)N=N1N2⋮Nn,Ni=Q∑j=1naijPij,i=1,2,…,n,Q=1,0,0,0,Pij=Ed_lattern−2⋉W2j,2n−j⋉W2i,2j−i−1.Proposition 7.
(see [24]). Let Ak=aijk be the k-AM of graph G=V,E, where V=v1,v2,…,vn; and, let VS=x1,x2,…,xn and YS=⋉i=1nyi=δ2nk be the eigenvector and eigenvalue of a subset S⊆V, where yi=xi,xi¯T. Then, S is a k-ISS of G if and only if colkN=0n, where N is given in Proposition 6.
Based on Propositions6 and 7 and Theorems 1 and 2, it follows from the definition of the k-kernel that the following results are true.Corollary 2.
LetAk=aijk be the k-AM of graph G=V,E, where V=v1,v2,…,vn. Then, G has a k-kernel if and only if there exists a 1≤j≤2n such that(60)coljM=1n,coljN=0n,where M and N are given in Theorem 1 and Proposition 6, respectively.Corollary 3.
LetAk=aijk be the k-AM of graph G=V,E. For a given node subset S⊆V, the eigenvector and eigenvalue are VS=x1,x2,…,xn and YS=⋉i=1nyi=δ2nk, respectively, where yi=xi,1−xiT. Then, S is a k-kernel G if and only if(61)colkM=1n,colkN=0n,where M and N are given in Corollary 2.Remark 7.
It is clear fromCorollaries 2 and 3 that the matrices M and N of Corollary 3 provide the complete information of all the k-kernels of a graph. We use them to define the concepts of the k-kernel matrix of a graph.Definition 13.
Thek-kernel matrix of the graph G described in Corollary 3 is the following matrix K:(62)K=MN,in which M and N are given in Corollary 3.
Based on Corollary3, we can design an algorithm to find all the k-kernels of a graph.Algorithm 3.
For the graph described in Corollary3, give each vi∈V a 2-valued variable xi∈D=0,1 and define yi=xi,1−xiT. To find all the k-kernels of the graph, one can take the following steps.Step 1. Compute the k-kernel matrix K of G.Step 2. Rewrite K as the form of K=MN shown in Corollary 3.Step 3. Check whether there is a 1n in colM. If not, there is no k-kernel in G and the algorithm ends here. Otherwise, go to the next step.Step 4. Check whether there is a 0n in colN. If not, there is no k-kernel in G and the algorithm ends. Otherwise, set(63)R=l|collM=1n,collN=0n.Step 5. For each l in R, compute yi=Sin⋉δ2nl, i=1,2,…,n, where(64)S1n=δ21…1︸2n−12…2︸2n−1,S2n=δ21…1︸2n−22…2︸2n−21…1︸2n−22…2︸2n−2,⋮Snn=δ212︸2…12︸2︸2n−1.Step 6. Pick out yi=δ21, and set Sl=vi|yi=δ21. Sl is a k-kernel of G. All the k-kernels of G are Sl|l∈K.


## 4. Comparisons with Existing Works and Computational Complexity

Roughly speaking, the approaches to study thek-ESS and k-kernel problems can be classified into three types: graph theory method, linear programming method, and computer algorithm-based method. Most of these results, especially the computer-based algorithms, cannot find all the k-ESSes of a graph.This paper uses a matrix method to consider thek-ESS and k-kernel problems of graphs. The results presented in this paper have several advantages over existing results. First, we established a matrix formulation of the k-ESS problems, which simply and clearly provide the complete information of the k-ESS of a graph in a matrix manner. Using these information, one can easily develop an algorithm to find all the k-ESSes of a graph. Second, the results of the k-ESS have good expansibility; the main results, including theoretic and algorithm ones, can be transplanted to the case of k-kernels of graphs; after slight modifications, they are applicable to formulate and find the k-kernels of graphs.Besides, several new concepts are proposed for thek-ESS and k-kernel of graphs, such as k-ESS matrix, minimum k-ESS matrix, and k-kernel matrix. These matrices can be viewed as structure matrices of k-ESS, minimum k-ESS, and k-kernel because they contain the complete information of all the k-ESSes, minimum k-ESSes, and k-kernel sets of graphs.The time complexity of the proposed algorithms isOn, including Algorithms 1, 2, and 3. Take Algorithm 2 for example (the complexity analysis of Algorithms 1 and 3 are very similar to that of Algorithm 2). For a given graph G with node set V=v1,v2,…,vn, of all the four steps of Algorithm 2, only Step 3 involves iterative operation. Therefore, for graphs of n vertices, the times of iterative operation are no more than n−1 in the worst situation. Thus, the time complexity is On. Besides, all the involved computations in Algorithm 2 are STP, which can be easily performed with the STP tool box.


## 5. Examination of Results

In this section, the correctness of the results are examined by using them to solve a network covering problem, as shown in Figure1. Because a k-kernel is both a k-ESS and a k-ISS, it needs only to check if that Algorithm 3 can find all the k-kernels of a graph.Figure 1
Graph model of the network covering problem.The 2-AM ofG is(65)A2=0111100000100101000001110010110100000110000000100000000000000010.Steps 1, 2 and 3: withA2, we can get the matrices M and N in Corollary 3. In M, the columns being 1n are as follows:(66)col103M,col104M,col113M,col117M,col123M,col124M,col125M,col126M,col127M,col128M,col171M,col172M,col173M,col174M,col176M,col177M,col183M,col184M,col188M,col189M,col190M,col192M,col193M,col216M,col224M,col227M,col230M,col238M,col239M,col240M,col242M,col247M,col248M,col249M,col251M,col252M,col253M,col254M,col255Mcol256M.And, the matrixN has the following columns being 0n:(67)col87M,col98M,col100M,col101M,col102M,col118M,col119M,col120M,col123M,col124M,col126M,col127M,col128M,col129M,col132M,col133M,col174M,col176M,col178M,col179M,col184M,col185M,col188M,col190M,col192M,col202M,col216M,col224M,col225M,col228M,col238M,col240M,col246M,col248M,col250M,col251M,col252M,col254M,col255M.Step 4: based on Steps 1, 2, and 3, construct the following set:(68)K=123,124,126,127,128,174,176,184,190,192,216,224,238,240,248,251,252,254,255.According to Corollary3, since K=20, there are total 20 2-kernels in G.Step 5: for each elementl∈K, we get yi by computing yi=Si8⋉δ256l, i=1,2,…,8. The set Sl=vi|yi=δ21 corresponds to a 2-kernel. Take l=123 for example, we get(69)y1=S18⋉δ256123=δ21,y2=S28⋉δ256123=δ22,y3=S38⋉δ256123=δ22,y4=S48⋉δ256123=δ22,y5=S58⋉δ256123=δ22,y6=S68⋉δ256123=δ21,y7=S78⋉δ256123=δ22,y8=S88⋉δ256123=δ21,where y1=δ21, y6=δ21, and y8=δ21. We then get a 2-kernel S123=v1,v6,v8, which is marked by triangles in Figure 1.Forl=124, we calculate yi=Si8⋉δ256124, i=1,2,…,8, and get(70)y1=S18⋉δ256123=δ21,y2=S28⋉δ256123=δ22,y3=S38⋉δ256123=δ22,y4=S48⋉δ256123=δ22,y5=S58⋉δ256123=δ22,y6=S68⋉δ256123=δ21,y7=S78⋉δ256123=δ22,y8=S88⋉δ256123=δ22,where y1=δ21 and y6=δ21. We get another 2-kernel S123=v1,v6.Considerl=174 for another example. Computing yi=Si8⋉δ256174, i=1,2,…,8, we get(71)y1=S18⋉δ256174=δ22,y2=S28⋉δ256174=δ21,y3=S38⋉δ256174=δ22,y4=S48⋉δ256174=δ21,y5=S58⋉δ256174=δ22,y6=S68⋉δ256174=δ22,y7=S78⋉δ256174=δ21,y8=S88⋉δ256174=δ22,where y2=δ21, y4=δ21, and y7=δ21 indicate a 2-kernel S174=v2,v4,v7, which is marked in pentagrams in Figure 1.Using the similar procedure, all the 2-kernels ofG can be obtained, which are collected in Table 1.Table 1
All the 2-kernels ofG.
l2-kernels123v1,v6,v8124v1,v6126v1,v7127v1,v8128v1174v2,v4184v2,v5190v2,v7192v2216v3,v5224v3238v4,v7248v4251v5252v6,v8254v6255v7For the case ofk=3, following the above steps, we can get all the 3-kernels of G:(72)v1,v7,v2,v4,v2,v5,v3,v5,v5,v8,v6,v8.Fork=4, there are five 4-kernels:(73)2,4,2,5,3,5,5,8,6,8.Whenk≥4, the k-kernels of G are the same because the k-AM Ak no longer changes.Remark 8.
According to Zhang et al. [30], the k-kernels of undirected graphs are the same as their maximum k-internally stable sets. The results above coincide with the statement.


## 6. Conclusion

In graph theory,k-ESS of graphs is an important research topic because many problems in the real world can be described and be solved by such graph model. In this paper, the formulation and search of k-ESS, minimum k-ESS, and k-kernels of a graph are reconsidered by using a new mathematical tool called STP. Several matrix forms of necessary and sufficient conditions of the k-ESS, minimum k-ESS, and k-kernels of graphs are established. Based on the necessary and sufficient conditions, the concepts of the k-ESS matrix, minimum k-ESS matrix, and k-kernel matrix are proposed. Besides, three algorithms of finding all the k-ESSes, minimum k-ESSes, and k-kernels of a graph are designed. The presented results may provide a new way to solve the problems of the network system such as minimization of networks.



---

*Source: 7230661-2021-07-06.xml*