Concept# Convex bipartite graph

Summary

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 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, …, |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)

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related publications

Related people

No results

No results

Related units

Related concepts

No results

No results

Related lectures

Related courses

No results

No results