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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1261,
author = {Ewa Drgas-Burchardt and Anna Fiedorowicz},
title = {Maximal hypergraphs with respect to the bounded cost hereditary property},
journal = {Discussiones Mathematicae Graph Theory},
volume = {25},
year = {2005},
pages = {67-77},
zbl = {1078.05060},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1261}
}
Ewa Drgas-Burchardt; Anna Fiedorowicz. Maximal hypergraphs with respect to the bounded cost hereditary property. Discussiones Mathematicae Graph Theory, Tome 25 (2005) pp. 67-77. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1261/
[000] [1] C. Berge, Hypergraphs (North-Holland, Amsterdam, 1989).
[001] [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.
[002] [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. | Zbl 0876.05031
[003] [4] J. Riordan, An Introduction to Combinatorial Analysis (New York, 1958). | Zbl 0078.00805