Explore relationships

Bipartite half

In graph theory, the bipartite half or half-square of a bipartite graphG = (U,V,E) is a graph whose vertex set is one of the two sides of the bipartition (without loss of generality, U) and in which there is an edge uiuj for each pair of vertices ui, uj in U that are at distance two from each other in G. That is, in a more compact notation, the bipartite half is G[U] where the superscript 2 denotes the square of a graph and the square brackets denote an induced subgraph.

Use + to expand a branch. Click a topic name to open its summary.