Convex bipartite graph
Encyclopedia
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.
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, f: U → { 1, 2, ..., |U| − 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).
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 a collection of edges that connect pairs of...
, a convex bipartite graph is a bipartite graph
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
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 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, f: U → { 1, 2, ..., |U| − 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).