Neighbourhood of Constant Order in the Interval Graph of a Random Boolean Function

Article type: Research Article

Authors: Daubner, Jakub | Toman, Eduard

Affiliations: University of Žilina, Faculty of Management Science and Informatics, Department of Info Communication Networks, Univerzitná 8215/1, 01026 Žilina, Slovakia. jdaubner@gmail.com | Comenius University, Faculty of Mathematics, Physics and Informatics, Department of Computer Science, Mlynská dolina, 842 48 Bratislava, Slovak Republic. toman@dcs.fmph.uniba.sk

Note: [] Address for correspondence: Šalviová 44, Bratislava, 821 01, Slovakia

Abstract: In the present paper we estimate the size of a neighbourhood of constant order in the interval graph of a random Boolean function. So far, no bound of this parameter has been known.

Keywords: random Boolean function, hypercube, interval graph, disjunctive normal form

DOI: 10.3233/FI-2013-790

Journal: Fundamenta Informaticae, vol. 122, no. 4, pp. 275-295, 2013