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 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.^[1] 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.^[2]

See also

• Bipartite double cover

References

1. Wilson, Robin J. (2004), Topics in Algebraic Graph Theory, Encyclopedia of Mathematics and its Applications 102, Cambridge University Press, p. 188, ISBN 9780521801973.
2. Chihara, Laura; Stanton, Dennis (1986), "Association schemes and quadratic transformations for orthogonal polynomials", Graphs and Combinatorics 2 (2): 101–112, doi:10.1007/BF01788084, MR 932118.