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 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.[1] That is, in a more compact notation, the bipartite half is G^2[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.[2] For instance, the halved Foster graph is one of finitely many degree-6 distance-regular locally linear graphs.[3]

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.[4] 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.[5]

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.[6]

See also

• Bipartite double cover

References

1. Wilson, Robin J. (2004), Topics in Algebraic Graph Theory, Encyclopedia of Mathematics and its Applications, vol. 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 0932118, S2CID 28803214.
3. Hiraki, Akira; Nomura, Kazumasa; Suzuki, Hiroshi (2000), "Distance-regular graphs of valency 6 and ${\displaystyle a_{1}=1}$", Journal of Algebraic Combinatorics, 11 (2): 101–134, doi:10.1023/A:1008776031839, MR 1761910
4. Le, Hoàng-Oanh; Le, Van Bang (2019), "Constrained representations of map graphs and half-squares", in Rossmanith, Peter; Heggernes, Pinar; Katoen, Joost-Pieter (eds.), 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany, LIPIcs, vol. 138, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 13:1–13:15, doi:10.4230/LIPIcs.MFCS.2019.13, ISBN 9783959771177
5. Garey, Michael R.; Johnson, David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Series of Books in the Mathematical Sciences (1st ed.). New York: W. H. Freeman and Company. ISBN 9780716710455. MR 0519066. OCLC 247570676., Problem GT59.
6. Chen, Zhi-Zhong; Grigni, Michelangelo; Papadimitriou, Christos H. (2002), "Map graphs", Journal of the ACM, 49 (2): 127–138, arXiv:cs/9910013, doi:10.1145/506147.506148, MR 2147819, S2CID 2657838.