Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 626.05045
Autor: Erdös, Paul; Ordman, Edward T.; Zalcstein, Yechezkel
Title: Bounds on threshold dimension and disjoint threshold coverings. (In English)
Source: SIAM J. Algebraic Discrete Methods 8, 151-154 (1987).
Review: The threshold dimension (threshold covering number) of a graph G is the least number of threshold graphs needed to edgecover the graph G. If tc(n) is the greatest threshold dimension of any graph of n vertices, we show that for some constant A, n-A\sqrt{n} log n < tc(n) < n-\sqrt{n}+1. We establish the same bounds for edge-disjoint coverings of graphs by threshold graphs (threshold partitions). We give an example to show there exist planar graphs on n vertices with a smallest covering of An threshold graphs and a smallest partition of Bn threshold graphs, with B = 1.5A. Thus the difference between these two covering numbers can grow linearly in the number of vertices.
Classif.: * 05C70 Factorization, etc.
Keywords: graph partition; threshold dimension; threshold covering number; threshold graphs; coverings; threshold partitions
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag