Bipartite half

Short description: Graph whose nodes are one of the vertex sets of a bipartite graph

The halved cube graph of order 4, obtained as the bipartite half of an order-4 hypercube graph

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 pair of vertices u_i, 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.

Examples

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. For instance, the halved Foster graph is one of finitely many degree-6 distance-regular locally linear graphs.

Representation and hardness

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. 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 G 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.

See also

• Bipartite double cover