# Matrix Formulation of EISs of Graphs and Its Application to WSN Covering Problems

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

---

## Abstract

In this paper, the problem of formulating and finding externally independent sets of graphs is considered by using a newly developed STP method, called semitensor product of matrices. By introducing a characteristic value of a vertex subset of a graph and using the algebraic representation of pseudological functions, several necessary and sufficient conditions of matrix form are proposed to express the externally independent sets (EISs), minimum externally independent sets (MEISs), and kernels of graphs. Based on this, the concepts of EIS matrix, MEIS matrix, and kernel matrix are introduced. By these matrices’ complete characterization of these three structures of graphs, three algorithms are further designed which can find all these kinds of subsets of graphs mathematically. The results are finally applied to a WSN covering problem to demonstrate the correctness and effectiveness of the proposed results.


---

## Body

## 1. Introduction

A graph is a figure composed of vertices and edges and is usually used to describe a specific relationship between things; vertices are used to represent things, and an edge connecting two vertices is used to represent the relationship between the two things. The intuitive diagrammatic representation of relationships has created widespread use of graphs in modeling systems in physical science and engineering problems; actually any system involving a binary relation can be represented by a graph [1]. Graph theory has experienced explosive growth and has come to play a central role in engineering and computer science curricula [2].Independent set problem of graphs is a key issue in graph theory and control theory and has been applied to many practical problems in the industrial field such as resource selection, facility location, mobile base station location, and logistics center location. [3, 4]. The problem has become a hot topic in the field of system and control. Yue and Yan [5] gave a matrix formulation of k-internally independent sets and k-maximum internally independent sets of graphs by proposing several new sufficient and necessary conditions of k-internally independent sets and k-maximum internally independent sets. Based on these conditions, they further designed algebraic algorithms that can find all the k-internally independent sets and k-maximum internally independent sets of a given graph. The approach is different from other methods and may offer a new perspective to understand structures of a graph. With regard to the number of independent sets of a graph, Hua [6] proposed an upper bound of the value for the graphs having k cut-edges. Also, he described corresponding extremal graphs. There are also a series of conjectures on independent sets of graphs. Deng, Guo, and Zang [7] proved Chvatal’s conjecture on maximal independent sets of a graph. Later, the conjecture was generalized by Ding [8], which was then proved by Sun and Hu [9].In recent years, a new matrix analysis tool, called semitensor product of matrices (STP of matrices), has been developed [10]. The STP of matrices generalizes the traditional product of matrices by allowing any two matrices; the number of columns of the former is not equal to that of rows of the latter to participate in operation; and almost all the major properties of the traditional product hold true for the STP of matrices. Theoretically, the STP of matrices can be applied in most of engineering and science fields, especially for the problems that can be presented as a discrete mathematical model. The STP of matrices is now well established and has been found to be very useful in many areas [11–19].Based on the STP of matrices, a matrix approach to investigate graph problems has been established recently. Wang, Zhang, and Liu [20] introduced the STP of matrices to the domain of graph theory and proposed a matrix approach to investigate serval problems such as the internally stable set problem, absolutely maximum internally stable set problem, maximum weight stable set problem, and vertex coloring problem. Several new results and algorithms were proposed. Afterwards, the matrix approach was applied to many problems in the field of graph theory. In [21], Xu considered the coloring problem of robust graphs and presented several new results by formulating the coloring problem as an optimization problem. With these new conclusions, a new timetabling scheme is developed. Later, Xu and Wang [22, 23] advanced the study to the problems of conflict-free coloring and fuzzy graph coloring. Zhong et al. [24] used the matrix approach to discuss the way of searching minimum stable sets and cores of graphs. Meng, Feng, and Li [25] pushed the method towards the hypergraphs area and investigated transversal and covering problems. In [26], Yue et al. proposed a necessary and sufficient condition of multi-internally stable set of graphs. The presented results are further used to solve the multitrack assignment problem; two solvability conditions are presented.The advantages of this matrix approach to graph problems are the mathematical formulation and exact decision results for the problems, which are very useful to study other graph problems. The idea of this approach is entirely different from that of existing ones and may be a new perspective to comprehend the structures of graphs in a mode of mathematics.The motivations of this paper, inspired by the superiorities of the matrix approach to graphs, are to formulate the externally independent sets of graphs in a matrix fashion and to find all the externally independent sets of a graph mathematically. Further, the results are expected to expand to the cases of minimum externally independent sets and kernels of graphs; and the results are used to solve a kind of WSN covering problem and service stations optimal location problem, which serves as a means of examination of the correctness and effectiveness of the proposed results.The contributions of this paper consist of two aspects. In theory, we established several necessary and sufficient conditions of externally independent sets, minimum externally independent sets, and kernels of graphs. In algorithm, three algorithms were designed which can produce all the externally independent sets, all the minimum externally independent sets, and all the kernels of a graph. These may advance the graph matrix approach in the area of system science.The paper is organized as follows. In Section2, we give necessary preliminaries on graphs and the research tool of this paper, as well as the STP of matrices. Section 3 presents the main results of this paper, including theory results and algorithm ones. Section 4 is devoted to discussing differences between the proposed approach and existing methods, as well as the complexity of the proposed algorithms. An application of the results to WSN covering problem, serving as an examination of the correctness and effectiveness of the presented results, is given in Section 5; this is followed by concluding remarks in Section 6.


## 2. Preliminaries

In this section, we give some necessary preliminaries on STP of matrices (semitensor product of matrices) and externally independent sets (EISs) of graphs.Definition 1.
(STP of matrices) (see [10]). For any two matrices M∈Mm×n and N∈Mp×q, their STP, denoted by M⋉N, is defined as(1)M⋉N≔M⊗Is/nN⊗Is/p,where s is the least common multiple of n and p and ⊗ is the Kronecker product.
The following example illustrates the STP of matrices:(1)
For two vectorsX=1,−2,1,−3 and Y=2−1, their STP is(2)X⋉Y=1,−2⋅2+1,−3⋅−1=1,−1.(2)
For two matrices of dimensions3×4 and 2×2,A=224−14−102−1−211 and B=−3−221, their STP is(3)A⋉B=2,2,4,−1⋉−322,2,4,−1⋉−214,−1,0,2⋉−324,−1,0,2⋉−21−1,2,1,1⋉−32−1,2,1,1⋉−21=2201−122−845−43−3.Remark 1.
The STP of matrices is a generalization of the traditional matrix multiplication; whenn=p, the STP of matrices reduces to the latter. In this paper, the matrix multiplication is the STP of matrices by default, and the symbol ⋉ is also omitted except for special emphasis needed.Definition 2.
(swap matrix) (see [10]). A swap matrix Wm,n is an mn×mn matrix, whose rows and columns are tagged by index i,j. The rows are organized by the order of multi-index Idj,i;n,m and the columns by Idi,j;m,n. The element at position I,J,i,j is defined as(4)WI,J,i,j=δi,jI,J=1,I=iandJ=j,0,otherwise.Proposition 1.
(A property of swap matrix) [10]: For any two column vectors X∈Rm and Y∈Rn, the following pseudocommutative law holds:(5)Wm,n⋉X⋉Y=Y⋉X,Wn,m⋉Y⋉X=X⋉Y,Definition 3.
(dummy operator) (see [27]). The dummy operators Ed_latterm,n and Ed_formerm,n are defined as(6)Ed_latterm,n=In,…,In︸m,Ed_formerm,n=Im,…,Im︸n.
For convenience, defineEd_latter2,2≔Ed_latter and Ed_former2,2≔Ed_former.Proposition 2.
(a property of dummy operator) (see [27]). For any two logical vectors u∈Δm and v∈Δn (Δm and Δn are described below), the following pseudoelimination laws hold:(7)Ed_latterm,n⋉u⋉v=v,Ed_formerm,n⋉Wn,m⋉u⋉v=u.Proposition 3.
(negation operator) (see [20]). The matrix Mn=δ22,1 is called the negation operator of 2-valued logical variables (where δ22,1 is given in the following notations). For any 2-valued logical variable x, Mnx=x¯.Definition 4.
(graph) (see [2]). A graph G is a tuple G=V,E, where V is a set of objects called vertices and E is a set of 2-element subsets of V called edges.
In a graphG=V,E, V=v1,v2,…,vn, vj is called a neighbor of vi if vj,vi∈E; vi is default to be a neighbor of itself. Denote by Nvi=vj∈V|vj,vi∈E the neighbor set of vi.Definition 5.
(externally independent set of a graph) (see [20]). A set S of vertices of G is called an externally independent set (EIS) of G if for any a vertex vi∉S there is a vertex vj∈S such that vj∈Nvi. An EIS S is called a minimum externally independent set (MEIS) if any proper subset of S is not an EIS. An MEIS with the least number of vertices is called an absolutely minimum externally independent set (AMEIS). The number of vertices of an AMEIS is called the externally independent number of G, denoted by αG.Definition 6.
(unitary adjacency matrix of a graph) (see [27]). For a graph G of n vertices V=v1,v2,…,vn, the matrix B=bij is called the adjacency matrix of G:(8)bij=1,vi∈Nvj,0,vi∉Nvj.
The matrixA=aij is called the unitary adjacency matrix (UAM) of G:(9)aij=1,i=j,bij,i≠j.
It is easy to get that(10)aij=bij∨δij,where ∨ denotes the logic product operation, and δij is the Kronecker symbol defined as follows:(11)δij=1,i=j,0,i≠j.


## 3. Main Results

In this section, we present the main results of this paper, including theoretic part and algorithm part. Theoretic results consist of matrix formulations of externally independent set and minimum externally independent set of graphs. Algorithm results contain two algorithms which can find all the externally independent sets and minimum externally independent sets of a graph, respectively. Further, we extend these results to the kernels of graphs by appropriate modification.


### 3.1. Matrix Formulation and Algebraic Algorithm of EIS

Definition 7.
(characteristic logical vector of vertex subset) (see [20]). Given a vertex subset S⊆V of G=V,E, the characteristic logical vector of S, denoted as VS=x1,x2,…,xn, is(12)xi=1,xi∈S,0,xi∉S.
In the framework of the STP of matrices and based on Definition7, we define the characteristic value of a vertex subset of a graph. A characteristic value corresponds to a unique vertex subset of a graph.Definition 8.
(characteristic value of vertex subset). For a vertex subsetS⊆V of G=V,E, VS=x1,x2,…,xn is its characteristic logical vector. Let yi=xi,1−xiT, i=1,2,…,n; the characteristic value of S is defined as(13)YS=⋉i=1nyi.Remark 2.
Since eachyi is uniquely determined by yi=Sin⋉YS, where Sin is defined in (30), and each set of yi uniquely determines YS, the characteristic value YS of S is uniquely determined by the characteristic logical vector VS, and vice versa. Therefore, once one of YS and VS is known, the other one can then be determined; consequently, the vertex subset S is known.Theorem 1.
Given a graphG=V,E with A=aij being its UAM, V=v1,v2,…,vn. G contains an externally independent set if and only if there is 1≤j≤2n satisfying(14)coljM=1n,where(15)M=M1M2⋮Mn,Mi=J⋉∑i=1naijQj,i=1,2,…,n,J=1,0,Qj=Ed_lattern−j⋉W2,2n−j⋉Ed_latterj−1.Proof.
Necessity: assume thatS is an externally independent set of G. Let VS=x1,x2,…,xn be the characteristic logical vector of S. It follows from Definition 5 that, for a vertex vi not in S, corresponding to xi=0, there is j1≤j≤n such that(16)bij=1,xj=1.
Equation (16) is equivalent to(17)xi∨∨j=1nbijxj=1.
From (8) and (17), we have the following:(18)∨j=1naijxj=1.
Since bothaij and xj only take the values of 0 and 1, (18) can be further expressed as(19)∑j=1naijxj=1.
On the other hand, setyj=xj,1−xjT, j=1,2,…,n. From (7), we have that(20)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.
Clearly,(21)xj=J⋉yj,aijxj=aijJ⋉yj=aijJ⋉Qj⋉YS.
We thus get from (19) that(22)∑j=1naijxj=J⋉∑j=1naijQj⋉YS≔Mi⋉YS.where Mi=J⋉∑j=1naijQj.
Thus, the following equations are equivalent to each other fori∈1,2,…,n:(1)
∑j=1naijxj=1(2)
Mi⋉YS=1(3)
There is a column ofMi which is 1n(4)
There exists1≤j≤2n such that coljMi=1n
Note that (19) amounts to(23)∑j=1na1jxj=1,∑j=1na2jxj=1,⋮∑j=1nanjxj=1.
It is easy to know that equation (23) has a solution x1,x2,…,xn if and only if there is 1≤j≤2n such that(24)coljM=1n.where(25)M=M1M2⋮Mn.
The equivalence between (19) and (23) shows the necessity.
(Sufficiency). The sufficiency follows the reversibility from equations (16) to (23).Remark 3.
Theorem1 describes the condition that a graph contains an externally independent set, based on which we can develop a criterion of judging whether a given vertex subset of a graph is an externally independent set or not.Theorem 2.
LetA=aij be the UAM of graph G=V,E. Given a vertex subset S⊆V with VS=x1,x2,…,xn being its characteristic logical vector and YS=⋉i=1nyi=δ2nk being its characteristic value, where yi=xi,1−xiT, S is an externally independent set of G if and only if(26)colkM=1n.where(27)M=M1M2⋮Mn,Mi=J⋉∑i=1naijQj,i=1,2,…,n,J=1,0,Qj=Ed_lattern−j⋉W2,2n−j⋉Ed_latterj−1.Proof.
Comparing (26) with (14), we know that it is sufficient to show that the k-th column of M is equal to 1n; that is, the k-th column of Mi,i=1,2,…,n is equal to 1.
The proof of Theorem1 shows that Mi⋉YS=1 if and only if “there is 1≤j≤2n satisfying coljMi=1.” Thus, there is only a need to prove that k meets the requirement. Actually, the sizes of Mi and YS are 1×2n and 2n×1, respectively. In this situation, the semitensor product of matrices amounts to the traditional matrix multiplication. Thus, Mi⋉YS is exactly the k-th column of Mi. It is natural that Mi⋉YS=1 is equivalent to colkMi=1. Theorem 2 is then proved.Remark 4.
By Theorems1 and 2, we know that matrix M of (14) or (26) provides the information of all the externally independent sets of a graph. In view of this, we introduce the following definition:Definition 9.
(externally independent set matrix). MatrixM of (14) or (26) in Theorem 1 or 2 is called the externally independent set matrix of graph G.
According to the proof of Theorem1, we can easily get the following conclusion which describes a condition under which a graph has an externally independent set. The difference with Theorem 1 is the usage of a different characteristic logical vector, as Corollary 1 shows.Corollary 1.
Consider graphG=V,E whose UAM is A=aij. Give vi∈V a two-valued variable xi∈D=0,1 and let yi=xi,1−xiT. There are externally independent sets in G equivalent to the fact that the following equation has at least one solution:(28)M⋉i=1nyi=1n.
In fact, the number of externally independent sets ofG equals that of the solutions. More specifically, an externally independent set is determined by each solution of (28). Further, according to Theorem 2, the number of externally independent sets is equal to that of 1n-columns of M.The proofs of Theorems1 and 2, as well as Corollary 1, imply a way to design an algorithm to obtain all the externally independent sets of a graph.Algorithm 1.
For a given graphG=V,E, let A=aij be the UAM of G, and assign each vi∈V a two-valued variable xi∈D=0,1. Set yi=xi,1−xiT. The following five-step procedure yields all the externally independent sets and minimum externally independent sets of G.Step 1: compute the externally independent set matrixM of graph G.Step 2: check whetherM has a column being 1n. If not, G has no externally independent set and the algorithm ends here. Otherwise, define(29)K=l|collM=1n.Step 3: solve the equation⋉i=1nyi=δ2nl with respect to yi for each l in K by computing yi=Sin⋉δ2nl, i=1,2,…,n, where(30)S1n=δ21,…,1︸2n−12,…,2︸2n−1S2n=δ21,…,1︸2n−22,…,2︸2n−21,…,1︸2n−22,…,2︸2n−2,⋮Snn=δ212︸2,…,12︸2︸2n−1.Step 4: selectyi=δ21 and construct Sl=vi|yi=δ21. Sl is an externally independent set of G. All the externally independent sets of G are(31)Sl|l∈K.Step 5: the externally independent number ofG is(32)αG=minl∈KSl,whereSl is the cardinality of Sl. All the minimum externally independent sets of G are(33)ζ=Sl|Sl=αG.Remark 5.
Using Algorithm1, we can obtain all the externally independent sets of a graph, including the externally independent sets with special properties; for example, each vertex outside an externally independent set is linked with the externally independent set only once, exactly k times, and so forth. In brief, Algorithm 1 offers a way to see the whole picture of the structure of a graph in terms of externally independent sets by producing all of them.


### 3.2. Matrix Formulation and Algebraic Algorithm of MEIS

Algorithm1’s ability of finding all the externally independent sets of a graph enables us to obtain the minimum externally independent sets of a given graph. In this subsection, we address the algebraic formulation and algorithm of minimum externally independent sets of graphs.Theorem 3.
Consider a graphG=V,E with the UAM A=aij. For a given vertex subset S⊆V with characteristic logical vector VS=x1,x2,…,xn and characteristic value YS=⋉i=1nyi=δ2nk, where yi=xi,1−xiT, S is a minimum externally independent set of G if and only if(34)colkM=0n.where(1)
M=J⋉Qi−n2Jn−1MnEd_latter∑j=1na¯ij(2)
J=1,0; Qi=Ed_lattern−i⋉W2,2n−i⋉Ed_latteri−1
Mn is given in Proposition 3; a¯ij=1−aij.Proof: .
(Necessity) LetVS=x1,x2,…,xn be the characteristic logical vector of the minimum externally independent set S.(i)
Forxi=0, we know according to (19) that(35)∑j=1j≠inaijxj=1.(ii)
Forxi=1, we next prove that(36)∑j=1j≠inaijxj=0.
If this not true, that is,∑j=1j≠inaijxj=1, it follows then from Theorem 1 that the vertex subset with characteristic logical vector VS=x1,…,xi−1,0,xi+1,…,xn is also an externally independent set; that is, S′=v1,…,vi−1,vi+1,…,vn is an externally independent set of G. This contradicts the fact that S=v1,…,vi,…,vn is a minimum externally independent set of G. Thus, (36) holds.
Equations (35) and (36) imply that(37)xi=∑j=1na¯ij∧j=1j≠inx¯j.where a¯ij=1−aij.
On the other hand,(38)∑j=1na¯ij∧j=1j≠iny¯j=∑j=1na¯ij∧j=1j≠inMnyj=∑j=1na¯ijMn∧j=1j≠inyj=nMn∑j=1na¯ij∧j=1j≠inyj=nMn∑j=1na¯ijEd_latteryi∧j=1j≠inyj=nMn∑j=1na¯ijEd_latter∧j=1nyj=nMn∑j=1na¯ijEd_latterYs=n2MnEd_latter∑j=1na¯ijYs.
By (20), we get(39)xi=Jyi=JEd_lattern−jW2,2n−jEd_latterj−1YS≔JQiYS.
Substitution ofxj=Jyj and equations (38) and (39) into (37) gives the necessity.
Sufficiency: suppose that (34) holds; it follows from the reversibility of equation (37) to (39) that the characteristic logical vector of S, VS=x1,x2,…,xn, satisfies (35) and (36).
Ifx1=x2=⋯=xn=1, then ∑j=1naijxj≥∑j=1najj=1; therefore, S is an externally independent set of G. If there is xi=0, then(40)∑j=1naijxj=∑j=1j≠inaijxj=1.
According to Theorem2, S is an externally independent set of G.
Now let us remove a vertexxi from S and denote the resulting vertex subset as S′. The characteristic logical vector of S′ is VS′=x1,…,xi−1,0,xi+1,…,xn. Since vi∈S, xi=1. It follows from (36) that(41)∑j=1j≠inaijxj=0.
We then know thatcoljM=0n, and this indicates that VS′=x1,…,xi−1,0,xi+1,…,xn does not meet (14). Therefore, S′ is not an externally independent set of G. Thus, S is a minimum externally independent set of G. The sufficiency is proved.
We can also transfer the problem of finding minimum externally independent sets of graphs to the problem of solving the minimum value of pseudo-Boolean functions. To this end, we first make some preparations.Lemma 1.
(see [28]). Let fx1,x2,…,xn be a pseudo-Boolean function with constraint conditions:(42)fjx1,x2,…,xn=0,j=1,2,…,m,where each fj is a nonnegative integer-valued pseudo-Boolean function. Denote by S+ and S− the sums of positive coefficients and negative coefficients of f, respectively. Construct a pseudo-Boolean function:(43)Fx1,x2,…,xn=fx1,x2,…,xn+S+−S−+1∑j=1mfjx1,x2,…,xn.
Then,(i)
Ifx1∗,x2∗,…,xn∗ is a local minimum point of f under the constraint conditions (42), then x1∗,x2∗,…,xn∗ is also a local minimum point of F;(ii)
Ifx1∗,x2∗,…,xn∗ is a local minimum point of Fand Fx1∗,x2∗,…,xn∗≤S+, then x1∗,x2∗,…,xn∗ is also a local minimum point of f under the constraint conditions (42).Theorem 4.
For a given graphG=V,E with the UAM A=aij, a vertex subset S⊆V whose characteristic logical vector and characteristic value are VS=x1,x2,…,xn and YS=⋉i=1nyi=δ2nk, respectively, where yi=xi,1−xiT. Then, S is a minimum externally independent set of G if and only if the k-th component of M is minimum among all the nonnegative components, where(44)M=J∑i=1nQi+n+1∑j=1n∑i=1naijQi,in which J=1,0; Qi=Ed_lattern−i⋉W2,2n−i⋉Ed_latteri−1.Proof.
According to the proof of Theorem1, the characteristic logical vector of a minimum externally independent set of graph G is the local minimum point of pseudo-Boolean function hx1,x2,…,xn=∑i=1nxi under the constraint condition (18). Using Lemma 1, where S+=n and S−=0, such a minimization problem with constraint conditions is converted to the following minimization problem without constraint conditions:(45)fx1,x2,…,xn=∨i=1nxi∨n+1∨i=1n∨i=1naijxj.
Since bothxii=1,2,…,n and aij are two-valued variables taking 0 and 1, (45) is equivalent to the following pseudo-Boolean function:(46)fx1,x2,…,xn=∑i=1nxi+n+1∑j=1n∑i=1naijxj.
By (20)–(22), (46) can be rewritten as(47)fy1,y2,…,yn=J∑i=1nQiYS+n+1∑j=1n∑i=1naijQiYS=J∑i=1nQi+n+1∑j=1n∑i=1naijQiYS≔MYS,where(48)M=J∑i=1nQi+n+1∑j=1n∑i=1naijQi,J=1,0,Qi=Ed_lattern−i⋉W2,2n−i⋉Ed_latteri−1,yi=xi,1−xiT,YS=⋉i=1nyi.
It is now clear from the characteristic value ofS, YS=⋉i=1nyi=δ2nk, that the k-th component of M is the minimum value of functions (45) and (46). The proof is completed.Remark 6.
The necessity and sufficiency of Theorem4 ensure that the matrix of (44) is qualified to describe the minimum externally independent sets of graphs. We define M as the minimum externally independent set matrix of a graph.Definition 10.
(minimum externally independent set matrix). MatrixM of (44) in Theorem 4 is called the minimum externally independent set matrix of graph G.
The necessity and sufficiency of Theorem4 also offer us a matrix approach to find all the minimum externally independent sets of a graph. Similar to Algorithm 1, we have the following algorithm producing all the minimum externally independent sets of a given graph.Algorithm 2.
LetA=aij be the UAM of graph G=V,E. Assign each vertex vi∈V a characteristic variable xi∈D=0,1 and define yi=xi,1−xiT. Taking the following steps, one can get all the minimum externally independent sets of G.Step 1. Compute the minimum externally independent set matrix of G, that is, M in (44).Step 2. Check whether there are nonnegative components in the first row of M; if not, G contains no minimum externally independent set and the algorithm terminates. Otherwise, set(49)K=l|collM=mincolM.Step 3. For each l in K, solve the equation with respect to yi, ⋉i=1nyi=δ2nl, by computing yi=Sin⋉δ2nl, i=1,2,…,n, where(50)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 set(51)Sl=vi|yi=δ21.Sl is a minimum externally independent set of G; and all the minimum externally independent sets of G areSl|l∈K, Sl is produced by Steps 3 and 4.}


### 3.3. Extending Results to the Kernels of Graphs

The kernel of graphs is an important topic in the area of graph theory and has a great applied value in the scientific field such as similarity measurement of graph structures [3]. A subset S of vertices is called a kernel of a graph if S is both an externally independent set and an internally stable set of the graph. The matrix formulation and algebraic algorithm of internally stable set of graphs are presented in [26]. Combining these results, in this subsection, we extend the results of the externally independent sets and minimum externally independent sets to the case of the kernels of graphs, including matrix formulation and algebraic algorithm of finding all the kernels of a graph.Lemma 2.
(see [26]). Let A=aij be the UAM of graph G=V,E with V=v1,v2,…,vn. Then, G has an internally stable set if and only if there is j, 1≤j≤2n, such that coljN=0n, where(52)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.Lemma 3.
(see [26]). Let A=aij be the UAM of graph G=V,E with V=v1,v2,…,vn. For a given subset S⊆V with characteristic logical vector VS=x1,x2,⋯,xn and letting YS=⋉i=1nyi=δ2nk, yi=xi,xi¯T, S is an internally stable set of G if and only if colkN=0n, where N is given in Lemma 2.
According to the definition of kernel of a graph, combining Lemmas2 and 3 and Theorems 1 and 2, we can easily get the following results.Corollary 2.
Given a graphG=V,E with A=aij being its UAM, V=v1,v2,…,vn. G contains a kernel if and only if there is 1≤j≤2n satisfying the conditions:(53)coljM=1n,coljN=0n,where M and N are given in Theorem 1 and Lemma 2, respectively.Corollary 3.
LetA=aij be the UAM of graph G=V,E. Given a vertex subset S⊆V with VS=x1,x2,…,xn being its characteristic logical vector and YS=⋉i=1nyi=δ2nk being its characteristic value, where yi=xi,1−xiT, S is a kernel G if and only if(54)colkM=1n,colkN=0n,where M and N are given in Corollary 2.
FromCorollaries 2 and 3, it is clear that matrices M and N present the information of all the kernels of a graph. We introduce the definition of kernel matrix of a graph.Definition 11.
(kernel matrix of graphs). The following matrixK is called the kernel matrix of graph G described in Corollary 3, where(55)K=MN,in which M and N are given in Corollary 3.
Corollary3 offers us a way to develop an algorithm to find all the kernels of a graph.Algorithm 3.
Consider the graph given in Corollary3. Assign each vi∈V a two-valued variable xi∈D=0,1, and define yi=xi,1−xiT. The following procedure produces all the kernels of G:Step 1: compute the kernel matrix of graphG, denoted as K.Step 2: divideK into the form of K=MN as described in Corollary 3.Step 3: check whetherM has a column being 1n. If not, G has no kernel set and the algorithm ends here. Otherwise, go to next step.Step 4: check whetherN has a column being 0n. If not, G has no kernel set and the algorithm ends here. Otherwise, set(56)R=l|collM=1n,collN=0n.Step 5: solve the equation⋉i=1nyi=δ2nl with respect to yi for each l in R by computing yi=Sin⋉δ2nl, i=1,2,…,n, where(57)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: selectyi=δ21 and construct Sl=vi|yi=δ21. Sl is a kernel of G. All the kernels of G are Sl|l∈K.


## 3.1. Matrix Formulation and Algebraic Algorithm of EIS

Definition 7.
(characteristic logical vector of vertex subset) (see [20]). Given a vertex subset S⊆V of G=V,E, the characteristic logical vector of S, denoted as VS=x1,x2,…,xn, is(12)xi=1,xi∈S,0,xi∉S.
In the framework of the STP of matrices and based on Definition7, we define the characteristic value of a vertex subset of a graph. A characteristic value corresponds to a unique vertex subset of a graph.Definition 8.
(characteristic value of vertex subset). For a vertex subsetS⊆V of G=V,E, VS=x1,x2,…,xn is its characteristic logical vector. Let yi=xi,1−xiT, i=1,2,…,n; the characteristic value of S is defined as(13)YS=⋉i=1nyi.Remark 2.
Since eachyi is uniquely determined by yi=Sin⋉YS, where Sin is defined in (30), and each set of yi uniquely determines YS, the characteristic value YS of S is uniquely determined by the characteristic logical vector VS, and vice versa. Therefore, once one of YS and VS is known, the other one can then be determined; consequently, the vertex subset S is known.Theorem 1.
Given a graphG=V,E with A=aij being its UAM, V=v1,v2,…,vn. G contains an externally independent set if and only if there is 1≤j≤2n satisfying(14)coljM=1n,where(15)M=M1M2⋮Mn,Mi=J⋉∑i=1naijQj,i=1,2,…,n,J=1,0,Qj=Ed_lattern−j⋉W2,2n−j⋉Ed_latterj−1.Proof.
Necessity: assume thatS is an externally independent set of G. Let VS=x1,x2,…,xn be the characteristic logical vector of S. It follows from Definition 5 that, for a vertex vi not in S, corresponding to xi=0, there is j1≤j≤n such that(16)bij=1,xj=1.
Equation (16) is equivalent to(17)xi∨∨j=1nbijxj=1.
From (8) and (17), we have the following:(18)∨j=1naijxj=1.
Since bothaij and xj only take the values of 0 and 1, (18) can be further expressed as(19)∑j=1naijxj=1.
On the other hand, setyj=xj,1−xjT, j=1,2,…,n. From (7), we have that(20)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.
Clearly,(21)xj=J⋉yj,aijxj=aijJ⋉yj=aijJ⋉Qj⋉YS.
We thus get from (19) that(22)∑j=1naijxj=J⋉∑j=1naijQj⋉YS≔Mi⋉YS.where Mi=J⋉∑j=1naijQj.
Thus, the following equations are equivalent to each other fori∈1,2,…,n:(1)
∑j=1naijxj=1(2)
Mi⋉YS=1(3)
There is a column ofMi which is 1n(4)
There exists1≤j≤2n such that coljMi=1n
Note that (19) amounts to(23)∑j=1na1jxj=1,∑j=1na2jxj=1,⋮∑j=1nanjxj=1.
It is easy to know that equation (23) has a solution x1,x2,…,xn if and only if there is 1≤j≤2n such that(24)coljM=1n.where(25)M=M1M2⋮Mn.
The equivalence between (19) and (23) shows the necessity.
(Sufficiency). The sufficiency follows the reversibility from equations (16) to (23).Remark 3.
Theorem1 describes the condition that a graph contains an externally independent set, based on which we can develop a criterion of judging whether a given vertex subset of a graph is an externally independent set or not.Theorem 2.
LetA=aij be the UAM of graph G=V,E. Given a vertex subset S⊆V with VS=x1,x2,…,xn being its characteristic logical vector and YS=⋉i=1nyi=δ2nk being its characteristic value, where yi=xi,1−xiT, S is an externally independent set of G if and only if(26)colkM=1n.where(27)M=M1M2⋮Mn,Mi=J⋉∑i=1naijQj,i=1,2,…,n,J=1,0,Qj=Ed_lattern−j⋉W2,2n−j⋉Ed_latterj−1.Proof.
Comparing (26) with (14), we know that it is sufficient to show that the k-th column of M is equal to 1n; that is, the k-th column of Mi,i=1,2,…,n is equal to 1.
The proof of Theorem1 shows that Mi⋉YS=1 if and only if “there is 1≤j≤2n satisfying coljMi=1.” Thus, there is only a need to prove that k meets the requirement. Actually, the sizes of Mi and YS are 1×2n and 2n×1, respectively. In this situation, the semitensor product of matrices amounts to the traditional matrix multiplication. Thus, Mi⋉YS is exactly the k-th column of Mi. It is natural that Mi⋉YS=1 is equivalent to colkMi=1. Theorem 2 is then proved.Remark 4.
By Theorems1 and 2, we know that matrix M of (14) or (26) provides the information of all the externally independent sets of a graph. In view of this, we introduce the following definition:Definition 9.
(externally independent set matrix). MatrixM of (14) or (26) in Theorem 1 or 2 is called the externally independent set matrix of graph G.
According to the proof of Theorem1, we can easily get the following conclusion which describes a condition under which a graph has an externally independent set. The difference with Theorem 1 is the usage of a different characteristic logical vector, as Corollary 1 shows.Corollary 1.
Consider graphG=V,E whose UAM is A=aij. Give vi∈V a two-valued variable xi∈D=0,1 and let yi=xi,1−xiT. There are externally independent sets in G equivalent to the fact that the following equation has at least one solution:(28)M⋉i=1nyi=1n.
In fact, the number of externally independent sets ofG equals that of the solutions. More specifically, an externally independent set is determined by each solution of (28). Further, according to Theorem 2, the number of externally independent sets is equal to that of 1n-columns of M.The proofs of Theorems1 and 2, as well as Corollary 1, imply a way to design an algorithm to obtain all the externally independent sets of a graph.Algorithm 1.
For a given graphG=V,E, let A=aij be the UAM of G, and assign each vi∈V a two-valued variable xi∈D=0,1. Set yi=xi,1−xiT. The following five-step procedure yields all the externally independent sets and minimum externally independent sets of G.Step 1: compute the externally independent set matrixM of graph G.Step 2: check whetherM has a column being 1n. If not, G has no externally independent set and the algorithm ends here. Otherwise, define(29)K=l|collM=1n.Step 3: solve the equation⋉i=1nyi=δ2nl with respect to yi for each l in K by computing yi=Sin⋉δ2nl, i=1,2,…,n, where(30)S1n=δ21,…,1︸2n−12,…,2︸2n−1S2n=δ21,…,1︸2n−22,…,2︸2n−21,…,1︸2n−22,…,2︸2n−2,⋮Snn=δ212︸2,…,12︸2︸2n−1.Step 4: selectyi=δ21 and construct Sl=vi|yi=δ21. Sl is an externally independent set of G. All the externally independent sets of G are(31)Sl|l∈K.Step 5: the externally independent number ofG is(32)αG=minl∈KSl,whereSl is the cardinality of Sl. All the minimum externally independent sets of G are(33)ζ=Sl|Sl=αG.Remark 5.
Using Algorithm1, we can obtain all the externally independent sets of a graph, including the externally independent sets with special properties; for example, each vertex outside an externally independent set is linked with the externally independent set only once, exactly k times, and so forth. In brief, Algorithm 1 offers a way to see the whole picture of the structure of a graph in terms of externally independent sets by producing all of them.


## 3.2. Matrix Formulation and Algebraic Algorithm of MEIS

Algorithm1’s ability of finding all the externally independent sets of a graph enables us to obtain the minimum externally independent sets of a given graph. In this subsection, we address the algebraic formulation and algorithm of minimum externally independent sets of graphs.Theorem 3.
Consider a graphG=V,E with the UAM A=aij. For a given vertex subset S⊆V with characteristic logical vector VS=x1,x2,…,xn and characteristic value YS=⋉i=1nyi=δ2nk, where yi=xi,1−xiT, S is a minimum externally independent set of G if and only if(34)colkM=0n.where(1)
M=J⋉Qi−n2Jn−1MnEd_latter∑j=1na¯ij(2)
J=1,0; Qi=Ed_lattern−i⋉W2,2n−i⋉Ed_latteri−1
Mn is given in Proposition 3; a¯ij=1−aij.Proof: .
(Necessity) LetVS=x1,x2,…,xn be the characteristic logical vector of the minimum externally independent set S.(i)
Forxi=0, we know according to (19) that(35)∑j=1j≠inaijxj=1.(ii)
Forxi=1, we next prove that(36)∑j=1j≠inaijxj=0.
If this not true, that is,∑j=1j≠inaijxj=1, it follows then from Theorem 1 that the vertex subset with characteristic logical vector VS=x1,…,xi−1,0,xi+1,…,xn is also an externally independent set; that is, S′=v1,…,vi−1,vi+1,…,vn is an externally independent set of G. This contradicts the fact that S=v1,…,vi,…,vn is a minimum externally independent set of G. Thus, (36) holds.
Equations (35) and (36) imply that(37)xi=∑j=1na¯ij∧j=1j≠inx¯j.where a¯ij=1−aij.
On the other hand,(38)∑j=1na¯ij∧j=1j≠iny¯j=∑j=1na¯ij∧j=1j≠inMnyj=∑j=1na¯ijMn∧j=1j≠inyj=nMn∑j=1na¯ij∧j=1j≠inyj=nMn∑j=1na¯ijEd_latteryi∧j=1j≠inyj=nMn∑j=1na¯ijEd_latter∧j=1nyj=nMn∑j=1na¯ijEd_latterYs=n2MnEd_latter∑j=1na¯ijYs.
By (20), we get(39)xi=Jyi=JEd_lattern−jW2,2n−jEd_latterj−1YS≔JQiYS.
Substitution ofxj=Jyj and equations (38) and (39) into (37) gives the necessity.
Sufficiency: suppose that (34) holds; it follows from the reversibility of equation (37) to (39) that the characteristic logical vector of S, VS=x1,x2,…,xn, satisfies (35) and (36).
Ifx1=x2=⋯=xn=1, then ∑j=1naijxj≥∑j=1najj=1; therefore, S is an externally independent set of G. If there is xi=0, then(40)∑j=1naijxj=∑j=1j≠inaijxj=1.
According to Theorem2, S is an externally independent set of G.
Now let us remove a vertexxi from S and denote the resulting vertex subset as S′. The characteristic logical vector of S′ is VS′=x1,…,xi−1,0,xi+1,…,xn. Since vi∈S, xi=1. It follows from (36) that(41)∑j=1j≠inaijxj=0.
We then know thatcoljM=0n, and this indicates that VS′=x1,…,xi−1,0,xi+1,…,xn does not meet (14). Therefore, S′ is not an externally independent set of G. Thus, S is a minimum externally independent set of G. The sufficiency is proved.
We can also transfer the problem of finding minimum externally independent sets of graphs to the problem of solving the minimum value of pseudo-Boolean functions. To this end, we first make some preparations.Lemma 1.
(see [28]). Let fx1,x2,…,xn be a pseudo-Boolean function with constraint conditions:(42)fjx1,x2,…,xn=0,j=1,2,…,m,where each fj is a nonnegative integer-valued pseudo-Boolean function. Denote by S+ and S− the sums of positive coefficients and negative coefficients of f, respectively. Construct a pseudo-Boolean function:(43)Fx1,x2,…,xn=fx1,x2,…,xn+S+−S−+1∑j=1mfjx1,x2,…,xn.
Then,(i)
Ifx1∗,x2∗,…,xn∗ is a local minimum point of f under the constraint conditions (42), then x1∗,x2∗,…,xn∗ is also a local minimum point of F;(ii)
Ifx1∗,x2∗,…,xn∗ is a local minimum point of Fand Fx1∗,x2∗,…,xn∗≤S+, then x1∗,x2∗,…,xn∗ is also a local minimum point of f under the constraint conditions (42).Theorem 4.
For a given graphG=V,E with the UAM A=aij, a vertex subset S⊆V whose characteristic logical vector and characteristic value are VS=x1,x2,…,xn and YS=⋉i=1nyi=δ2nk, respectively, where yi=xi,1−xiT. Then, S is a minimum externally independent set of G if and only if the k-th component of M is minimum among all the nonnegative components, where(44)M=J∑i=1nQi+n+1∑j=1n∑i=1naijQi,in which J=1,0; Qi=Ed_lattern−i⋉W2,2n−i⋉Ed_latteri−1.Proof.
According to the proof of Theorem1, the characteristic logical vector of a minimum externally independent set of graph G is the local minimum point of pseudo-Boolean function hx1,x2,…,xn=∑i=1nxi under the constraint condition (18). Using Lemma 1, where S+=n and S−=0, such a minimization problem with constraint conditions is converted to the following minimization problem without constraint conditions:(45)fx1,x2,…,xn=∨i=1nxi∨n+1∨i=1n∨i=1naijxj.
Since bothxii=1,2,…,n and aij are two-valued variables taking 0 and 1, (45) is equivalent to the following pseudo-Boolean function:(46)fx1,x2,…,xn=∑i=1nxi+n+1∑j=1n∑i=1naijxj.
By (20)–(22), (46) can be rewritten as(47)fy1,y2,…,yn=J∑i=1nQiYS+n+1∑j=1n∑i=1naijQiYS=J∑i=1nQi+n+1∑j=1n∑i=1naijQiYS≔MYS,where(48)M=J∑i=1nQi+n+1∑j=1n∑i=1naijQi,J=1,0,Qi=Ed_lattern−i⋉W2,2n−i⋉Ed_latteri−1,yi=xi,1−xiT,YS=⋉i=1nyi.
It is now clear from the characteristic value ofS, YS=⋉i=1nyi=δ2nk, that the k-th component of M is the minimum value of functions (45) and (46). The proof is completed.Remark 6.
The necessity and sufficiency of Theorem4 ensure that the matrix of (44) is qualified to describe the minimum externally independent sets of graphs. We define M as the minimum externally independent set matrix of a graph.Definition 10.
(minimum externally independent set matrix). MatrixM of (44) in Theorem 4 is called the minimum externally independent set matrix of graph G.
The necessity and sufficiency of Theorem4 also offer us a matrix approach to find all the minimum externally independent sets of a graph. Similar to Algorithm 1, we have the following algorithm producing all the minimum externally independent sets of a given graph.Algorithm 2.
LetA=aij be the UAM of graph G=V,E. Assign each vertex vi∈V a characteristic variable xi∈D=0,1 and define yi=xi,1−xiT. Taking the following steps, one can get all the minimum externally independent sets of G.Step 1. Compute the minimum externally independent set matrix of G, that is, M in (44).Step 2. Check whether there are nonnegative components in the first row of M; if not, G contains no minimum externally independent set and the algorithm terminates. Otherwise, set(49)K=l|collM=mincolM.Step 3. For each l in K, solve the equation with respect to yi, ⋉i=1nyi=δ2nl, by computing yi=Sin⋉δ2nl, i=1,2,…,n, where(50)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 set(51)Sl=vi|yi=δ21.Sl is a minimum externally independent set of G; and all the minimum externally independent sets of G areSl|l∈K, Sl is produced by Steps 3 and 4.}


## 3.3. Extending Results to the Kernels of Graphs

The kernel of graphs is an important topic in the area of graph theory and has a great applied value in the scientific field such as similarity measurement of graph structures [3]. A subset S of vertices is called a kernel of a graph if S is both an externally independent set and an internally stable set of the graph. The matrix formulation and algebraic algorithm of internally stable set of graphs are presented in [26]. Combining these results, in this subsection, we extend the results of the externally independent sets and minimum externally independent sets to the case of the kernels of graphs, including matrix formulation and algebraic algorithm of finding all the kernels of a graph.Lemma 2.
(see [26]). Let A=aij be the UAM of graph G=V,E with V=v1,v2,…,vn. Then, G has an internally stable set if and only if there is j, 1≤j≤2n, such that coljN=0n, where(52)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.Lemma 3.
(see [26]). Let A=aij be the UAM of graph G=V,E with V=v1,v2,…,vn. For a given subset S⊆V with characteristic logical vector VS=x1,x2,⋯,xn and letting YS=⋉i=1nyi=δ2nk, yi=xi,xi¯T, S is an internally stable set of G if and only if colkN=0n, where N is given in Lemma 2.
According to the definition of kernel of a graph, combining Lemmas2 and 3 and Theorems 1 and 2, we can easily get the following results.Corollary 2.
Given a graphG=V,E with A=aij being its UAM, V=v1,v2,…,vn. G contains a kernel if and only if there is 1≤j≤2n satisfying the conditions:(53)coljM=1n,coljN=0n,where M and N are given in Theorem 1 and Lemma 2, respectively.Corollary 3.
LetA=aij be the UAM of graph G=V,E. Given a vertex subset S⊆V with VS=x1,x2,…,xn being its characteristic logical vector and YS=⋉i=1nyi=δ2nk being its characteristic value, where yi=xi,1−xiT, S is a kernel G if and only if(54)colkM=1n,colkN=0n,where M and N are given in Corollary 2.
FromCorollaries 2 and 3, it is clear that matrices M and N present the information of all the kernels of a graph. We introduce the definition of kernel matrix of a graph.Definition 11.
(kernel matrix of graphs). The following matrixK is called the kernel matrix of graph G described in Corollary 3, where(55)K=MN,in which M and N are given in Corollary 3.
Corollary3 offers us a way to develop an algorithm to find all the kernels of a graph.Algorithm 3.
Consider the graph given in Corollary3. Assign each vi∈V a two-valued variable xi∈D=0,1, and define yi=xi,1−xiT. The following procedure produces all the kernels of G:Step 1: compute the kernel matrix of graphG, denoted as K.Step 2: divideK into the form of K=MN as described in Corollary 3.Step 3: check whetherM has a column being 1n. If not, G has no kernel set and the algorithm ends here. Otherwise, go to next step.Step 4: check whetherN has a column being 0n. If not, G has no kernel set and the algorithm ends here. Otherwise, set(56)R=l|collM=1n,collN=0n.Step 5: solve the equation⋉i=1nyi=δ2nl with respect to yi for each l in R by computing yi=Sin⋉δ2nl, i=1,2,…,n, where(57)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: selectyi=δ21 and construct Sl=vi|yi=δ21. Sl is a kernel of G. All the kernels of G are Sl|l∈K.


## 4. Comparisons with Existing Approaches and Complexity Analysis

The externally independent set problem of graphs has been studied widely and many results have been proposed. Most of the existing results can be roughly classified, from viewpoint of research approach, into three categories: graph theory-based, integer programming model-based, and algorithm-based [29].The STP of matrices provides an elegant way to analyze the structures of graphs [20], which is very promising due to the rapid increase of computational technologies. The results of this paper established using the STP of matrices have the following differences and advantages in the aspects of model formulation, perspective and expansibility of conclusions, and so forth.Most of existing results use graph theory, optimization theory, and computer-based algorithms to formulate and find externally independent sets of a graph. Such approach has a disadvantage that not all the externally independent sets of given graphs can be obtained. In this paper, the problem of externally independent set is considered from the perspective of k-valued logic. Using the algebraic expression of k-valued pseudo-Boolean functions developed by STP, the externally independent set matrix (EISM), minimum externally independent set matrix (MEISM), and kernel matrix are proposed. These three matrices have precise mathematical meanings; they provide complete information of externally independent sets (EISs), minimum externally independent sets (MEISs), and kernel sets of a graph. More importantly, the completeness of describing externally independent sets (EISs) and minimum externally independent sets (MEISs) and kernels of graphs enable us to design algorithms to find all the EISs, MEISs, and kernel sets of a graph.Besides, the proposed results, including theoretical results and algorithms, can be easily extended to the cases of k-externally independent set, k-minimum externally independent set, and k-kernel sets by replacing the unitary adjacency matrix (UAM) by k-adjacency matrix (KAM) of graphs. Correspondingly, the concepts of k-externally independent set matrix (k-EISM), minimum externally independent set matrix (k-MEISM), and k-kernel matrix can also be established.We next analyze the computational complexity of the presented searching algorithms (Algorithms1–3), taking Algorithm 2 as an example; Algorithms 1 and 3 are very similar to Algorithm 2. Consider a graph G of n vertices V=v1,v2,…,vn. In Algorithm 2, only Step 3 involves circulation iteration. For a graph with n vertices, the time of circulation iteration is at most n−1 in the worst situation. Therefore, Algorithm 2 iterates n−1 times at most and the time complexity is On. In addition, all the computations involved in Algorithm 2 are matrix multiplication, namely, the semitensor product of matrices, which can be easily conducted by using the STP toolbox.


## 5. An Application to WSN Covering Problems

WSN covering problem studies how to reach a minimum number of sensors or the construction costs under the condition of covering all points of interest. WSN covering problem can be studied by viewing it as set covering problem. The set covering problem was first proposed by Roth [30] to solve the location problem of emergency service facilities such as fire control center and ambulance. An integer programming model for the set covering problem with different costs was established. Plane, Hendrick, Daskin, and Stern proposed a double objective set covering problem with the minimum number of service stations and the maximum number of customers. Since 2000, many heuristic algorithms have been used to solve set covering problems. Fisher and Northup proposed a dual heuristic algorithm to solve the set covering problem [31]. Beasley and Jornsten combined the subgradient optimization method and Lagrange relaxation algorithm to solve such problems [32]. Beasley and Chu gave a genetic algorithm to solve the set covering problem with different cost of service stations. Among them, random greedy algorithm, simple greedy algorithm, and transform greedy algorithm are the best algorithms for almost all problems, of which random greedy algorithm is the best. Halperin and Karp proved that the set covering problem is NP-complete [33].In this section, we use the presented results to solve a WSN covering problem, whose graph model is shown in Figure1, to verify the correctness and effectiveness of the results. It is sufficient from the logical relation among Algorithm 2, Theorems 2 and 1, and Algorithm 1 that there is only a need to check Algorithm 2.Figure 1
Graph model of a WSN covering problem.The UAM ofG is(58)A=010000010101110010010100000011011111010101000000110100000101000110100000000100000.Steps 1 and 2: according to (44), all of the minimum nonnegative components of the minimum externally independent set matrix of G are as follows:(59)col171M,col183M,col224M,col352M,col374M,col375M,col378M,col379M,col426M,col438M,col478M.Thus, the setK is K=171,183,224,352,374,375,378,379,426,438,478.Step 3: for eachl in K, computing yi=Si9⋉δ512l, i=1,2,…,9, taking l=171 as an example, we get(60)y1=S19⋉δ512171=δ21,y2=S29⋉δ512171=δ22,y3=S39⋉δ512171=δ21,y4=S49⋉δ512171=δ22,y5=S59⋉δ512171=δ21,y6=S69⋉δ512171=δ22,y7=S79⋉δ512171=δ21,y8=S89⋉δ512171=δ22,y9=S99⋉δ512171=δ21.Step 4: chooseyi=δ21 and construct S171=vi|yi=δ21=v1,v3,v5,v7,v9. S171 is a minimum externally independent set of G.Repeating Steps 3 and 4, we get all the minimum externally independent sets ofG, which are listed in Table 1.Table 1
All the minimum externally independent sets (MEISs) ofG.
lMEIS171v1,v3,v5,v7,v9183v1,v3,v6,v9224v1,v4352v2,v4374v2,v6,v8375v2,v6,v9378v2,v7,v8379v2,v7,v9426v3,v5,v7,v8438v3,v6,v8478v4,v8It is clear from Table1 that G has three absolutely minimum externally independent sets:(61)v1,v4,v2,v4,v4,v8.Therefore, the covering problem has three optimal solutions:(1)
Putting two sensors at locationsv1 and v4(2)
Putting two sensors at locationsv2 and v4(3)
Putting two sensors at locationsv4 and v8Remark 7.
It was shown in [28] that there are two optimization schemes of putting two sensors, v1,v4 and v2,v4. According to our result, there are exactly three such optimization schemes, v1,v4, v2,v4, and v4,v8.


## 6. Concluding Remarks

Externally independent set is an important structure of a graph. Many problems in science and engineering can be formulated by externally independent set of graphs. Description and search of externally independent sets of a graph represent a key issue in graph theory. In this paper, a newly proposed matrix analysis tool, semitensor product of matrices, is used to consider the problem of formulating and finding externally independent sets, minimum externally independent sets, and kernel sets of graphs. Several new necessary and sufficient conditions of these three structures are obtained; and three kinds of matrices containing the complete information of these vertex subsets are proposed. Further three algebraic algorithms that can find all these special subsets of a graph are developed. As a test of the effectiveness of the obtained results, a WSN covering problem, namely, location of service stations, is considered by these results. The research approach of this paper may offer a different way to investigate the structures of graphs and related problems such as Hamiltonian paths, Hamiltonian circles, and complete graphs.



---

*Source: 5526532-2021-04-22.xml*