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...

Full description

Saved in:
Bibliographic Details
Published in:Journal of mathematics (Hidawi) 2021, Vol.2021, p.1-12
Main Authors: Yan, Yongyi, Yue, Jumei, Deng, He
Format: Article
Language:English
Subjects:
Algorithms
Control theory
Graphs
Kernels
Mathematical analysis
Mathematics
Matrix methods
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2314-4629
2314-4785
DOI:10.1155/2021/5526532