Properties of the interval graph of a Boolean function
type: Item
instance of: scholarly article
zbMATH Open document ID: 1313.60004
author: L. Haviarová
author: E. Toman
publication date: 2013-09-26T00:00:00Z
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6212346
zbMATH Keywords: Boolean function
zbMATH Keywords: intersection graph
zbMATH Keywords: disjunctive normal form
MaRDI profile type: Publication
title: Properties of the interval graph of a Boolean function
published in: Acta Mathematica Universitatis Comenianae. New Series
review text: 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\).
description: scientific article; zbMATH DE number 6212346