Bound graph

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

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

  • 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

  • Turán graph — The Turán graph T(13,4) Named after Pál Turán v · …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”