ACTA MATHEMATICA
UNIVERSITATIS COMENIANAE




Vol. LXXIX, 2 (2010)
p. 151 - 164

Vertex degree in the interval graph
of a random Boolean function


J. Daubner and E. Toman

Received: August 5, 2008;   Revised: November 4, 2009;   Accepted: March 16, 2010



Abstract.   In the present paper we obtain asymptotic estimation of vertex degree in the interval graph of a random Boolean function. Till now only lower and upper bound of this parameter was known.

Keywords:  random Boolean function; interval graph  

AMS Subject classification: Primary:  05C80, 60C05, 06E30, 68R05   Secondary: 46B42




PDF                               Compressed Postscript                                 Version to read






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
© 2010, ACTA MATHEMATICA UNIVERSITATIS COMENIANAE