Convex bipartite graph

From HandWiki
Revision as of 11:59, 8 May 2022 by imported>Unex (over-write)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

In the mathematical field of graph theory, a convex bipartite graph is a bipartite graph with specific properties. A bipartite graph, (U ∪ VE), 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 ∪ VE) that is convex over both U and V is said to be biconvex or doubly convex.

Formal definition

Let G = (U ∪ VE) be a bipartite graph, i.e., the vertex set is U ∪ V where U ∩ V = ∅. Let NG(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, fU → {1, …, |U|}, such that for all v ∈ V, for any two vertices x,y ∈ NG(v) ⊆ U there does not exist a z ∉ NG(v) such that f(x) < f(z) < f(y).

See also

  • Convex plane graph

References