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 v_i is the unique vertex of one clique in the cover (perhaps consisting only of it), that all other vertices v_j in the clique of v_i appear later than v_i in the ordering, and that when v_j appears in the clique of v_i, the clique of v_j is a subset of the clique of v_i.

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.

References