Properties of the interval graph of a Boolean function (Q2850100)

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