graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a bound graph expresses which pairs of elements of some

partially ordered set In mathematics, especially order theory, a partial order on a Set (mathematics), set is an arrangement such that, for certain pairs of elements, one precedes the other. The word ''partial'' is used to indicate that not every pair of elements need ...

have an

upper bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is every element of . Dually, a lower bound or minorant of is defined to be an element of that is less ...

. Rigorously, any

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...

''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 Edge or EDGE may refer to: Technology Computing * Edge computing, a network load-balancing system * Edge device, an entry point to a computer network * Adobe Edge, a graphical development application * Microsoft Edge, a web browser developed by ...

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 In the mathematical field of graph theory, the intersection number of a graph G=(V,E) is the smallest number of elements in a representation of G as an intersection graph of finite sets. In such a representation, each vertex is represented as a ...

, 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 Dual or Duals may refer to: Paired/two things * Dual (mathematics), a notion of paired concepts that mirror one another ** Dual (category theory), a formalization of mathematical duality *** see more cases in :Duality theories * Dual number, a nu ...

partial order ≥.

References

* * * *{{cite journal , author = Tanenbaum, P.J. , title = Bound graph polysemy , journal = Electronic Journal of Combinatorics , volume = 7 , year = 2000 , pages = #R43 , doi = 10.37236/1521 , url = http://www.combinatorics.org/Volume_7/PDF/v7i1r43.pdf, doi-access = free Graph families Order theory