Convex bipartite graph

In the mathematical field of graph theory, a convex bipartite graph is a bipartite graph with specific properties. A bipartite graph, (U ∪ V, E), is said to be convex over the vertex set U if U can be enumerated such that for all v ∈ V the vertices adjacent to v are consecutive.

Convexity over V is defined analogously. A bipartite graph (U ∪ V, E) that is convex over both U and V is said to be biconvex or doubly convex.

Formal definition

Let G = (U ∪ V, E) be a bipartite graph, i.e, the vertex set is U ∪ V where U ∩ V = ∅. Let N_G(v) denote the neighborhood of a vertex v ∈ V. The graph G is convex over U if and only if there exists a bijective mapping, f: U → { 1, 2, ..., |U| − 1, |U|}, such that for all v ∈ V, for any two vertices x,y ∈ N_G(v) ⊆ U there does not exist a z ∉ N_G(v) such that f(x) < f(z) < f(y).

See also

• Convex plane graph

References

• W. Lipski Jr.; Franco P. Preparata (August 1981). "Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems". Acta Informatica 15 (4): 329–346. doi:10.1007/BF00264533. http://www.springerlink.com/content/u18656lrg6424n3u/. Retrieved 2009-07-20. 
• Ten-hwang Lai; Shu-shang Wei (April 1997). "Bipartite permutation graphs with application to the minimum buffer size problem". Discrete Applied Mathematics 74 (1): 33–55. doi:10.1016/S0166-218X(96)00014-5. http://citeseer.ist.psu.edu/old/lai94bipartite.html. Retrieved 2009-07-20. 
• Jeremy P. Spinrad (2003). Efficient graph representations. AMS Bookstore. p. 128. ISBN 9780821828151. http://books.google.com/?id=RrtXSKMAmWgC&pg=PA128&lpg=PA128&dq=%22a+bipartite+graph+is+a+convex+graph%22. Retrieved 2009-07-20. 
• Andreas Brandstädt; Van Bang Le; Jeremy P. Spinrad (1999). Graph classes: a survey. SIAM. p. 94. ISBN 9780898714326. http://books.google.com/?id=es9ZbB6qHRYC&pg=PA94&lpg=PA94&dq=%22convex+if+there+is+an+ordering%22. Retrieved 2009-07-20. 

This combinatorics-related article is a stub. You can help Wikipedia by expanding it.v · Categories: Combinatorics stubs Graph families Wikimedia Foundation. 2010. Игры ⚽ Нужен реферат? Convex Software Library Convex curve Look at other dictionaries: Convex — A convex set. The word convex means curving out or bulging outward, as opposed to concave. Convex or convexity may refer to: Mathematics: Convex set, a set of points containing all line segments between each pair of its points Convex function, a… …   Wikipedia Convex graph — In mathematics, a convex graph may be a convex bipartite graph a convex plane graph the graph of a convex function This disambiguation page lists articles associated with the same title. If an …   Wikipedia Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and …   Wikipedia Glossary of graph theory — Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with… …   Wikipedia Line graph — This article is about the mathematical concept. For statistical presentation method, see line chart. In graph theory, the line graph L(G) of undirected graph G is another graph L(G) that represents the adjacencies between edges of G. The name… …   Wikipedia Crossing number (graph theory) — A drawing of the Heawood graph with three crossings. This is the minimum number of crossings among all drawings of this graph, so the graph has crossing number cr(G) = 3. In graph theory, the crossing number cr(G) of a graph G is the… …   Wikipedia Planar graph — Example graphs Planar Nonplanar Butterfly graph K5 The complete graph K4 …   Wikipedia Hypohamiltonian graph — In the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G does not itself have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian.HistoryHypohamiltonian graphs were first… …   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 Dilworth's theorem — In mathematics, in the areas of order theory and combinatorics, Dilworth s theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains. It is named for the mathematician …   Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”