Bound graph
In graph theory, a bound graph expresses which pairs of elements of some partially ordered set have an upper bound. Rigorously, any graph[disambiguation needed] 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 exactly the same class—any lower bound for ≤ is easily seen to be an upper bound for the dual partial order ≥.
References
- McMorris, F.R.; Zaslavsky, T. (1982). "Bound graphs of a partially ordered set". Journal of Combinatorics, Information & System Sciences. 7: 134–138.
{{cite journal}}: CS1 maint: multiple names: authors list (link)
- Lundgren, J.R.; Maybee, J.S. (1983). "A characterization of upper bound graphs". Congressus Numerantium. 40: 189–193.
{{cite journal}}: CS1 maint: multiple names: authors list (link)
- Bergstrand, D.J.; Jones, K.F. (1988). "On upper bound graphs of partially ordered sets". Congressus Numerantium. 66: 185–193.
{{cite journal}}: CS1 maint: multiple names: authors list (link)
- Tanenbaum, P.J. (2000). "Bound graph polysemy" (PDF). Electronic Journal of Combinatorics. 7: #R43.