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.

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

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 ≥.

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.