{{Short description|Graph whose nodes are one of the vertex sets of a bipartite graph}} [[File:Demi-4-cube.svg|thumb|240px|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 {{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}}.<ref>{{citation|title=Topics in Algebraic Graph Theory|volume=102|series=Encyclopedia of Mathematics and its Applications|first=Robin J.|last=Wilson|author-link=Robin Wilson (mathematician)|publisher=Cambridge University Press|year=2004|isbn=9780521801973|page=188|url=https://books.google.com/books?id=z2K26gZLC1MC&pg=PA188}}.</ref> 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.<ref>{{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 }}.</ref> For instance, the halved Foster graph is one of finitely many degree-6 distance-regular locally linear graphs.<ref>{{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 <math>a_1=1</math> | volume = 11 | year = 2000| doi-access = free }}</ref>
==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.<ref>{{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 }}</ref> 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.<ref>{{Garey-Johnson}}, Problem GT59.</ref>
==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.<ref>{{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 }}.</ref>
==See also== *Bipartite double cover
==References== {{reflist}}
Category:Graph operations Category:Bipartite graphs