- Bound graph
In
graph theory , a bound graph expresses which pairs of elements of somepartially ordered set have anupper bound . Rigorously, any graph "G" is a bound graph if there exists a partial order ≤ on the vertices of "G" with the property that for any vertices "u" and "v" of "G", "uv" is an edge of "G" if and only if "u" ≠ "v" and there is a vertex "w" such that "u" ≤ "w" and "v" ≤ "w".Bound graphs are sometimes referred to as "upper bound graphs", but the analogously defined lower bound graphs comprise the exact same class—any lower bound for ≤ is easily seen to be an upper bound for the dual partial order ≥.
References
*cite journal
author = McMorris, F.R.; Zaslavsky, T.
title = Bound graphs of a partially ordered set
journal = Journal of Combinatorics, Information & System Sciences
volume = 7
year = 1982
pages = 134–138*cite journal
author = Lundgren, J.R.; Maybee, J.S.
title = A characterization of upper bound graphs
journal = Congressus Numerantium
volume = 40
year = 1983
pages = 189–193*cite journal
author = Bergstrand, D.J.; Jones, K.F.
title = On upper bound graphs of partially ordered sets
journal = Congressus Numerantium
volume = 66
year = 1988
pages = 185–193*cite journal
author = Tanenbaum, P.J.
title = Bound graph polysemy
journal = Electronic Journal of Combinatorics
volume = 7
year = 2000
pages = #R43
url = http://www.combinatorics.org/Volume_7/PDF/v7i1r43.pdf
Wikimedia Foundation. 2010.