Discussiones Mathematicae Graph Theory 25(1-2) (2005) 67-77

MAXIMAL HYPERGRAPHS WITH RESPECT TO THE BOUNDED COST HEREDITARY PROPERTY

Ewa Drgas-Burchardt and Anna Fiedorowicz

Faculty of Mathematics
Computer Science and Econometrics
University of Zielona Góra
Z. Szafrana 4a, Zielona Góra, Poland
e-mail: E.Drgas-Burchardt@wmie.uz.zgora.pl
e-mail: A.Fiedorowicz@wmie.uz.zgora.pl

Abstract

The hereditary property of hypergraphs generated by the cost colouring notion is considered in the paper. First, we characterize all maximal graphs with respect to this property. Second, we give the generating function for the sequence describing the number of such graphs with the numbered order. Finally, we construct a maximal hypergraph for each admissible number of vertices showing some density property. All results can be applied to the problem of information storage.

Keywords: cost colouring, hereditary property, maximal hypergraphs.

2000 Mathematics Subject Classification: 05C65, 05C15.

References

[1] C. Berge, Hypergraphs (North-Holland, Amsterdam, 1989).
[2] E. Kubicka and A.J. Schwenk, An introduction to chromatic sums, in: Proceedings of the Seventeenth, Annual ACM Computer Sciences Conference (ACM Press) (1989) 39-45.
[3] J. Mitchem and P. Morriss, On the cost chromatic number of graphs, Discrete Math. 171 (1997) 201-211, doi: 10.1016/S0012-365X(96)00005-2.
[4] J. Riordan, An Introduction to Combinatorial Analysis (New York, 1958).

Received 30 October 2003
Revised 9 December 2004