scientific article; zbMATH DE number 3869363
[For the entire collection see Zbl 0534.00004.] The study of the problem what is the maximal number of senders having at least one site in range that receives its transmission in broadcast networks leads to a very special problem in the graph theory: having an undirected graph G(V,E) what is the maximum order of an open irredundant set OIR. Supposing N(v) denotes the set of vertices adjacent to v \((N(v)=\{u\in V:\) (u,v)\(\in E\})\) the OIR is such a set of vertices for which it holds: \[ (\forall v\in OIR)\quad (N(v)-\cup_{u\in OIR- \{v\}}(N(u)\cup\{u\}))\neq\emptyset. \] The algorithm computing the maximum order of an open irredundant set for trees as well as the proof of its correctness and comments concerning its algorithmical complexity are presented.
- Irredundance perfect graphs
- Weighted irredundance of interval graphs.
- scientific article; zbMATH DE number 3859049 (Why is no real title available?)
- Irredundance
- The private neighbor concept
- Irredundancy in circular arc graphs
- Efficient sets in graphs
- Domination chains in graphs
- Bibliography on domination in graphs and some basic definitions of domination parameters
- Open irredundance and maximum degree in graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3337494)