Bipartite half

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 Template:Math is a graph whose vertex set is one of the two sides of the bipartition (without loss of generality, Template:Mvar) and in which there is an edge Template:Mvar for each pair of vertices Template:Math in Template:Mvar that are at distance two from each other in Template:Mvar. That is, in a more compact notation, the bipartite half is Template:Math 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 Template:Math is the complete graph Template:Mvar and the bipartite half of the hypercube graph is the halved cube graph. When Template:Mvar 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 Template:Mvar is the bipartite half of another graph, formed by subdividing the edges of Template:Mvar into two-edge paths. More generally, a representation of Template:Mvar as a bipartite half can be found by taking any clique edge cover of Template:Mvar 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 Template:Mvar 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