Properties of the interval graph of a Boolean function
The interval graph \(\Gamma (f)\) of a Boolean function \(f\) is the intersection graph of the set of all maximal intervals of \(f\); that is, the vertices of \(\Gamma (f)\) are the maximal intervals of \(f\), and two vertices are adjacent whenever the corresponding maximal intervals intersect. It is shown that \(\Gamma (f)\) may reflect certain important structural properties of \(f\). For example, if \(\Gamma (f)\) is a complete graph, then the abbreviated disjunctive normal form of \(f\) is also a minimal d.n.f. of \(f\). It is also shown that for every graph \(G\) on \(n\) vertices there exists an \(n\)-ary Boolean function for \(f\) such that \(\Gamma (f)\cong G\).
- Recognition of interval Boolean functions
- Properties of symmetric Boolean functions
- Computing the weighted isolated scattering number of interval graphs in polynomial time
- Average degree in the interval graph of a random Boolean function
- A polynomial algorithm for minimal interval representation
- scientific article; zbMATH DE number 701114 (Why is no real title available?)
- Neighbourhood of constant order in the interval graph of a random Boolean function
- Relations between threshold and \(k\)-interval Boolean functions
This page was built for publication: Properties of the interval graph of a Boolean function
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2850100)
