RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2009 Volume 16, Issue 5, Pages 19–25 (Mi da583)

On the entropy minimal hereditary classes of coloured graphs

V. E. Alekseev, S. V. Sorochan

Nizhny Novgorod State University, Nizhny Novgorod, Russia

Abstract: We consider hereditary classes of graphs with coloured edges. The class is called entropy minimal if it does not contain proper hereditary subclasses having the same entropy value (logarithmic density). It is known for simple graphs that, for arbitrary fixed $a$ and $b$, the class consisting of all graphs admitting a partition by $a$ cliques and $b$ independent sets is entropy minimal. We prove a generalization of this statement for coloured graphs. Bibl. 5.

Keywords: hereditary class, entropy, entropy minimal class.

UDC: 519.17

Received: 16.04.2008
Revised: 08.05.2009


 English version:
Journal of Applied and Industrial Mathematics, 2010, 4:2, 143–146

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024