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 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.^[1]

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.^[1]

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. This is an edge clique cover together with a total order on the vertices with the properties that each vertex ${\displaystyle v_{i}}$ is the unique vertex of one clique in the cover (perhaps consisting only of it), that all other vertices ${\displaystyle v_{j}}$ in the clique of ${\displaystyle v_{i}}$ appear later than ${\displaystyle v_{i}}$ in the ordering, and that when ${\displaystyle v_{j}}$ appears in the clique of ${\displaystyle v_{i}}$, the clique of ${\displaystyle v_{j}}$ is a subset of the clique of ${\displaystyle v_{i}}$.^[2]

Bound graphs are sometimes referred to as upper bound graphs,^[3] 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 ≥.

A graph is a bound graph if and only if each edge belongs to the closed neighborhood of a simplicial vertex. These simplicial vertices correspond to the maximal elements of the underlying partial order. This characterization allows the bound graphs to be recognized in polynomial time.^[3]