Bounds on Threshold Dimension and Disjoint Threshold Coverings

The threshold dimension (threshold covering number) of a graph $G$ is the least number of threshold graphs needed to edgecover the graph $G$. If $\operatorname{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 <...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on matrix analysis and applications 1987-04, Vol.8 (2), p.151
Main Authors: Erdos, Paul, Ordman, Edward T, Zalcstein, Yechezkel
Format: Article
Language:English
Subjects:
Graphs
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The threshold dimension (threshold covering number) of a graph $G$ is the least number of threshold graphs needed to edgecover the graph $G$. If $\operatorname{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 < \operatorname{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.
ISSN:0895-4798
1095-7162
DOI:10.1137/0608012