Bound graph

Article summary

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. 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. 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. This cover, together with a linear extension of the given order, produces an ordered edge cover.…

Key claims

No claims recorded.

Discussion questions

1. Summarise the article in your own words. Which single claim would you verify first, and why?
2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.