Bipartite half

In graph theory, the bipartite half or half-square of a bipartite graph is a graph whose vertex set is one of the two sides of the bipartition and in which there is an edge for each pair of vertices in that are at distance two from each other in. That is, in a more compact notation, the bipartite half is where the superscript 2 denotes the square of a graph and the square brackets denote an induced subgraph.

Examples

For instance, the bipartite half of the complete bipartite graph is the complete graph and the bipartite half of the hypercube graph is the halved cube graph.
When is a distance-regular graph, its two bipartite halves are both distance-regular. For instance, the halved Foster graph is one of finitely many degree-6 distance-regular locally linear graphs.

Representation and hardness

Every graph is the bipartite half of another graph, formed by subdividing the edges of into two-edge paths. More generally, a representation of as a bipartite half can be found by taking any clique edge cover of and replacing each clique by a star. Every representation arises in this way. Since finding the smallest clique edge cover is NP-hard, so is finding the graph with the fewest vertices for which is the bipartite half.

Special cases

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