In graph theory, a bound graph expresses which pairs of elements of some partially ordered set have an upper 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.
The bound graphs are exactly the graphs that have a clique edge cover, a family of cliques that cover all edges, with the additional property that each clique includes a vertex that does not belong to any other clique in the family. For the bound graph of a given partial order, each clique can be taken to be the subset of elements less than or equal to some given element. A graph that is covered by cliques in this way is the bound graph of a partial order on its vertices, obtained by ordering the unique vertices in each clique as a chain, above all other vertices in that clique.
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
edit- McMorris, F.R.; Zaslavsky, T. (1982). "Bound graphs of a partially ordered set". Journal of Combinatorics, Information & System Sciences. 7: 134–138.
- Lundgren, J.R.; Maybee, J.S. (1983). "A characterization of upper bound graphs". Congressus Numerantium. 40: 189–193.
- Bergstrand, D.J.; Jones, K.F. (1988). "On upper bound graphs of partially ordered sets". Congressus Numerantium. 66: 185–193.
- Tanenbaum, P.J. (2000). "Bound graph polysemy" (PDF). Electronic Journal of Combinatorics. 7: #R43. doi:10.37236/1521.