Bipartite half
{{Short description|Graph whose nodes are one of the vertex sets of a bipartite graph}}
In graph theory, the bipartite half or half-square of a bipartite graph {{math|1=G = (U,V,E)}} is a graph whose vertex set is one of the two sides of the bipartition (without loss of generality, {{mvar|U}}) and in which there is an edge {{mvar|u{{sub|i}}u{{sub|j}}}} for each pair of vertices {{math|u{{sub|i}}, u{{sub|j}}}} in {{mvar|U}} that are at distance two from each other in {{mvar|G}}.{{citation|title=Topics in Algebraic Graph Theory|volume=102|series=Encyclopedia of Mathematics and its Applications|first=Robin J.|last=Wilson|publisher=Cambridge University Press|year=2004|isbn=9780521801973|page=188|url=https://books.google.com/books?id=z2K26gZLC1MC&pg=PA188}}. That is, in a more compact notation, the bipartite half is {{math|G{{sup|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 {{math|K{{sub|n,n}}}} is the complete graph {{mvar|K{{sub|n}}}} and the bipartite half of the hypercube graph is the halved cube graph.
When {{mvar|G}} is a distance-regular graph, its two bipartite halves are both distance-regular.{{citation
| last1 = Chihara | first1 = Laura
| last2 = Stanton | first2 = Dennis
| doi = 10.1007/BF01788084
| issue = 2
| journal = Graphs and Combinatorics
| mr = 932118
| pages = 101–112
| title = Association schemes and quadratic transformations for orthogonal polynomials
| volume = 2
| year = 1986| s2cid = 28803214
}}. For instance, the halved Foster graph is one of finitely many degree-6 distance-regular locally linear graphs.{{citation
| last1 = Hiraki | first1 = Akira
| last2 = Nomura | first2 = Kazumasa
| last3 = Suzuki | first3 = Hiroshi
| doi = 10.1023/A:1008776031839
| issue = 2
| journal = Journal of Algebraic Combinatorics
| mr = 1761910
| pages = 101–134
| title = Distance-regular graphs of valency 6 and
| volume = 11
| year = 2000| doi-access = free
}}
Representation and hardness
Every graph {{mvar|G}} is the bipartite half of another graph, formed by subdividing the edges of {{mvar|G}} into two-edge paths. More generally, a representation of {{mvar|G}} as a bipartite half can be found by taking any clique edge cover of {{mvar|G}} and replacing each clique by a star.{{citation
| last1 = Le | first1 = Hoàng-Oanh
| last2 = Le | first2 = Van Bang
| editor1-last = Rossmanith | editor1-first = Peter
| editor2-last = Heggernes | editor2-first = Pinar
| editor3-last = Katoen | editor3-first = Joost-Pieter
| contribution = Constrained representations of map graphs and half-squares
| doi = 10.4230/LIPIcs.MFCS.2019.13
| pages = 13:1–13:15
| publisher = Schloss Dagstuhl - Leibniz-Zentrum für Informatik
| series = LIPIcs
| title = 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, August 26-30, 2019, Aachen, Germany
| volume = 138
| year = 2019| doi-access = free
| isbn = 9783959771177
}} 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 {{mvar|G}} is the bipartite half.{{Garey-Johnson}}, Problem GT59.
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.{{citation
| last1 = Chen | first1 = Zhi-Zhong
| last2 = Grigni | first2 = Michelangelo
| last3 = Papadimitriou | first3 = Christos H. | author3-link = Christos Papadimitriou
| doi = 10.1145/506147.506148
| issue = 2
| journal = Journal of the ACM
| mr = 2147819
| pages = 127–138
| title = Map graphs
| volume = 49
| year = 2002| arxiv = cs/9910013| s2cid = 2657838
}}.