Matrix Formulation of EISs of Graphs and Its Application to WSN Covering Problems
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 pseudo...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2021-01-01
|
| Series: | Journal of Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2021/5526532 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832546794908680192 |
|---|---|
| author | Yongyi Yan Jumei Yue He Deng |
| author_facet | Yongyi Yan Jumei Yue He Deng |
| author_sort | Yongyi Yan |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-320e42fc430145c3b362993bfead09c2 |
| institution | Kabale University |
| issn | 2314-4629 2314-4785 |
| language | English |
| publishDate | 2021-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Mathematics |
| spelling | doaj-art-320e42fc430145c3b362993bfead09c22025-02-03T06:47:03ZengWileyJournal of Mathematics2314-46292314-47852021-01-01202110.1155/2021/55265325526532Matrix Formulation of EISs of Graphs and Its Application to WSN Covering ProblemsYongyi Yan0Jumei Yue1He Deng2College of Information Engineering, Henan University of Science and Technology, Luoyang, ChinaCollege of Agricultural Equipment Engineering, Henan University of Science and Technology, Luoyang, ChinaCollege of Information Engineering, Henan University of Science and Technology, Luoyang, ChinaIn 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.http://dx.doi.org/10.1155/2021/5526532 |
| spellingShingle | Yongyi Yan Jumei Yue He Deng Matrix Formulation of EISs of Graphs and Its Application to WSN Covering Problems Journal of Mathematics |
| title | Matrix Formulation of EISs of Graphs and Its Application to WSN Covering Problems |
| title_full | Matrix Formulation of EISs of Graphs and Its Application to WSN Covering Problems |
| title_fullStr | Matrix Formulation of EISs of Graphs and Its Application to WSN Covering Problems |
| title_full_unstemmed | Matrix Formulation of EISs of Graphs and Its Application to WSN Covering Problems |
| title_short | Matrix Formulation of EISs of Graphs and Its Application to WSN Covering Problems |
| title_sort | matrix formulation of eiss of graphs and its application to wsn covering problems |
| url | http://dx.doi.org/10.1155/2021/5526532 |
| work_keys_str_mv | AT yongyiyan matrixformulationofeissofgraphsanditsapplicationtowsncoveringproblems AT jumeiyue matrixformulationofeissofgraphsanditsapplicationtowsncoveringproblems AT hedeng matrixformulationofeissofgraphsanditsapplicationtowsncoveringproblems |