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 uiuj for each pair of vertices ui, uj in U that are at distance two from each other in G.[1] That is, in a more compact notation, the bipartite half is G2[U] where the superscript 2 denotes the square of a graph and the square brackets denote an induced subgraph.

[2] For instance, the halved Foster graph is one of finitely many degree-6 distance-regular locally linear graphs.

[3] Every graph G is the bipartite half of another graph, formed by subdividing the edges of G into two-edge paths.

More generally, a representation of G as a bipartite half can be found by taking any clique edge cover of G and replacing each clique by a star.

Since finding the smallest clique edge cover is NP-hard, so is finding the graph with the fewest vertices for which G is the bipartite half.