Bipartite half

In graph theory, the bipartite half or half-square of a bipartite graph G = (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 u_iu_j for each two vertices u_i and u_j 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.

For instance, the bipartite half of the complete bipartite graph K_n,n is the complete graph K_n and the bipartite half of the hypercube graph is the halved cube graph. When G is a distance-regular graph, its two bipartite halves are both distance-regular.

The map graphs, that is, the intersection graphs of interior-disjoint simply-connected regions in the plane, are exactly the bipartite halves of planar graphs.