Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-23T23:28:34.408Z Has data issue: false hasContentIssue false
  • English
  • Français

On Universal Threshold Graphs

Published online by Cambridge University Press:  12 September 2008

P. L. Hammer  and
A. K. Kelmans
P. L. Hammer
Affiliation:
RUTCOR, Rutgers University New Brunswick, New Jersey 08903
A. K. Kelmans
Affiliation:
RUTCOR, Rutgers University New Brunswick, New Jersey 08903
Get access Rights & Permissions [Opens in a new window]

Abstract

A graph G is threshold if there exists a ‘weight’ function w: V(G) → R such that the total weight of any stable set of G is less than the total weight of any non-stable set of G. Let n denote the set of threshold graphs with n vertices. A graph is called n-universal if it contains every threshold graph with n vertices as an induced subgraph. n-universal threshold graphs are of special interest, since they are precisely those n-universal graphs that do not contain any non-threshold induced subgraph.

In this paper we shall study minimumn-universal (threshold) graphs, i.e.n-universal (threshold) graphs having the minimum number of vertices.

It is shown that for any n ≥ 3 there exist minimum n-universal graphs, which are themselves threshold, and others which are not.

Two extremal minimum n-universal graphs having respectively the minimum and the maximum number of edges are described, it is proved that they are unique, and that they are threshold graphs.

The set of all minimum n-universal threshold graphs is then described constructively; it is shown that it forms a lattice isomorphic to the n − 1 dimensional Boolean cube, and that the minimum and the maximum elements of this lattice are the two extremal graphs introduced above.

The proofs provide a (polynomial) recursive procedure that determines for any threshold graph G with n vertices and for any minimum n-universal threshold graph T, an induced subgraph G' of T isomorphic to G.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 3 , Issue 3 , September 1994 , pp. 327 - 344
Copyright
Copyright © Cambridge University Press 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Bondy, J. A. and Murty, U. S. R. (1976) Graph Theory with Applications, Macmillan.Google Scholar
[2]Bhat, S. N. and Leiserson, C. E. (1984) How to assemble tree machines. In: Preparata, F. (ed.) Advances in Computing Research 2, JAI Press.Google Scholar
[3]Bhat, S. N., Chung, F. R. K., Leighton, T. and Rosenberg, A. L. (1989) Universal graphs for bounded-degree trees and planar graphs. SIAM J. Discrete Math. 2 145–155.Google Scholar
[4]Bhat, S. N., Chung, F. R. K., Leighton, T. and Rosenberg, A. L. (1988). Optimal simulations by butterfly networks. Proc. 27th Annual ACM Symposium on Theory of Computing, Chicago192–204.Google Scholar
[5]Brandstädt, A. (1991) Special Graph Classes – A Survey, Section Math, Fredrich Schiller Universität, Jena, Germany.Google Scholar
[6]Goldberg, M. K. and Lifshitz, E. M. (1968) On minimum universal trees. Mat. Zametki 4 371–379.Google Scholar
[7]Chung, F. R. K. (1990) Universal graphs and induced-universal graphs. Journal of Graph Theory 14 443–454.Google Scholar
[8]Chung, F. R. K., Graham, R. L. and Shaearer, J. (1981) Universal Caterpillars. J. Combinatorial Theory B 31 348–355.Google Scholar
[9]Chvátal, V. and Hammer, P. L. (1973) Set-packing problem and threshold graphs, University of Waterloo, CORR73–21.Google Scholar
[10]Chvátal, V. and Hammer, P. L. (1977) Aggregation of inequalities in integer programming. Annals of Discrete Mathematics 1 145–162.Google Scholar
[11]Erdős, P., Ordan, E. T. and Zalcstein, Y. (1987) Bounds on the threshold dimension and disjoint threshold coverings. SIAM J. of Algebra and Discrete Methods 8 151–154.CrossRefGoogle Scholar
[12]Friedman, J. and Pippenger, N. (1987) Expanding graphs contain all small trees. Combinatorica 7 71–76.Google Scholar
[13]Hammer, P. L., Ibaraki, T. and Peled, U. N. (1981) Threshold numbers and threshold completion. Annals of Discrete Mathematics 11 125–145.Google Scholar
[14]Kannan, S., Naos, M. and Rudich, S. (1988) Implicit representation of graphs. Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing334–343.Google Scholar
[15]Moon, J. W. (1965) On minimal n-universal graphs. Proc. Glasgow Math. Soc. 7 32–33.Google Scholar
[16]Rado, R. (1964) Universal graphs and universal functions. Acta Arith. 9 331–340.Google Scholar