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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page