# Bound graph

In

graph theory , a**bound graph**expresses which pairs of elements of somepartially ordered set have anupper 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".Bound graphs are sometimes referred to as "upper bound graphs", but the analogously defined

**lower bound graphs**comprise the exact same class—any lower bound for ≤ is easily seen to be an upper bound for the dual partial order ≥.**References***cite journal

author = McMorris, F.R.; Zaslavsky, T.

title = Bound graphs of a partially ordered set

journal = Journal of Combinatorics, Information & System Sciences

volume = 7

year = 1982

pages = 134–138*cite journal

author = Lundgren, J.R.; Maybee, J.S.

title = A characterization of upper bound graphs

journal = Congressus Numerantium

volume = 40

year = 1983

pages = 189–193*cite journal

author = Bergstrand, D.J.; Jones, K.F.

title = On upper bound graphs of partially ordered sets

journal = Congressus Numerantium

volume = 66

year = 1988

pages = 185–193*cite journal

author = Tanenbaum, P.J.

title = Bound graph polysemy

journal = Electronic Journal of Combinatorics

volume = 7

year = 2000

pages = #R43

url = http://www.combinatorics.org/Volume_7/PDF/v7i1r43.pdf

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Graph paper**— Regular graphing paper (upper); Logarithmic graphing paper (lower). Graph paper, graphing paper, grid paper or millimeter paper is writing paper that is printed with fine lines making up a … Wikipedia**Graph coloring**— A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… … Wikipedia**Moore graph**— Unsolved problems in mathematics Does a Moore graph with girth 5 and degree 57 exist? In graph theory, a Moore graph is a regular graph of degree d and diameter k whose number of vertices equals the upper bound An equivalent definition of a Moore … Wikipedia**Unit distance graph**— In mathematics, and particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points by an edge whenever the distance between the two points is exactly one.… … Wikipedia**Claw-free graph**— A claw In graph theory, an area of mathematics, a claw free graph is a graph that does not have a claw as an induced subgraph. A claw is another name for the complete bipartite graph K1,3 (that is, a star graph with three edges, three leaves, and … Wikipedia**Clique (graph theory)**— A graph with 23 1 vertex cliques (its vertices), 42 2 vertex cliques (its edges), 19 3 vertex cliques (the light blue triangles), and 2 4 vertex cliques (dark blue). Six of the edges and 11 of the triangles form maximal cliques. The two dark blue … Wikipedia**Paley graph**— infobox graph name = Paley graph image caption = The Paley graph of order 13 namesake = Raymond Paley vertices = edges = chromatic number = chromatic index = properties = Strongly regularIn mathematics, and specifically graph theory, Paley graphs … Wikipedia**Line graph of a hypergraph**— The line graph of a hypergraph is the graph whose vertex set is the set of the hyperedges of the hypergraph, with two edges adjacent when they have nonempty intersection. In other words, the line graph of a hypergraph is the intersection graph of … Wikipedia**Cubic graph**— Not to be confused with graphs of cubic functions. The Petersen graph is a Cubic graph … Wikipedia**Median graph**— The median of three vertices in a median graph In mathematics, and more specifically graph theory, a median graph is an undirected graph in which any three vertices a, b, and c have a unique median: a vertex m(a,b,c) that belongs to shortest… … Wikipedia