scientific article; zbMATH DE number 3869363

From MaRDI portal
Publication:3337494





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











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)