ACTA MATHEMATICA
UNIVERSITATIS COMENIANAE




Properties of the interval graph of a Boolean function

E. Toman and L. Haviarová

Received: June 26, 2012;   Revised: October 15, 2012;   Accepted: January 4, 2013



Abstract.   In the present paper we describe relations between the interval graph of a Boolean function, its abbreviated disjunctive normal form and its minimal disjunctive normal forms. The inteval graph of a Boolean function f has vertices corresponding to the maximal intervals of f and any two vertices are joined with an edge if the corresponding maximal intervals have nonempty intersection.

Keywords:  Boolean function; interval graph; disjunctive normal form.  

AMS Subject classification: Primary:  60C05, 05C80, 68R10  


Version to read:   PDF



Acta Mathematica Universitatis Comenianae
ISSN 0862-9544   (Printed edition)

Faculty of Mathematics, Physics and Informatics
Comenius University
842 48 Bratislava, Slovak Republic  

Telephone: + 421-2-60295111 Fax: + 421-2-65425882  
e-Mail: amuc@fmph.uniba.sk    Internet: www.iam.fmph.uniba.sk/amuc
© 2013, ACTA MATHEMATICA UNIVERSITATIS COMENIANAE