Matrix formulation of EISs of graphs and its application to WSN covering problems

DOI10.1155/2021/5526532MaRDI QIDQ2036024zbMATH OpenOpenAlexFDO

Authors Y. Y. Yan, Jumei Yue, He Deng

Publication date 28 June 2021

Published in Journal of Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1155/2021/5526532

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Multilinear algebra, tensor calculus (15A69)

Review text

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.

Recommendations

• Matrix approach to formulate and search k-ESS of graphs using the STP theory
• A matrix approach to graph maximum stable set and coloring problems with application to multi-agent systems
• On minimum weakly connected independent sets for wireless sensor networks: properties and enumeration algorithm
• scientific article; zbMATH DE number 847156
• scientific article; zbMATH DE number 5593359

Cites work

• A congestion game framework for service chain composition in NFV with function benefit
• A matrix approach to graph maximum stable set and coloring problems with application to multi-agent systems
• A sharp upper bound for the number of stable sets in graphs with given number of cut edges
• An introduction to semi-tensor product of matrices and its applications
• Automata, Languages and Programming
• Categorization Problem on Controllability of Boolean Control Networks
• Enhancing an algorithm for set covering problems
• scientific article; zbMATH DE number 3573593 (Why is no real title available?)
• Induced-Equations-Based Stability Analysis and Stabilization of Markovian Jump Boolean Networks
• Observability of switched Boolean control networks using algebraic forms
• On graphs with the third largest number of maximal independent sets
• On the stabilization of nondeterministic finite automata via static output feedback
• Proof of Ding's conjecture on maximal stable sets and maximal cliques in planar graphs
• Properly colored connectivity of graphs
• Robust graph coloring based on the matrix semi-tensor product with application to examination timetabling
• Solvability of k-track assignment problem: a graph approach
• Stable sets versus independent sets

Cited in

(1)

• Matrix approach to formulate and search k-ESS of graphs using the STP theory

This page was built for publication: Matrix formulation of EISs of graphs and its application to WSN covering problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2036024)