Bipartite half
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 uiuj for each pair of vertices ui, uj in U that are at distance two from each other in G.[1] That is, in a more compact notation, the bipartite half is G2[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 Kn,n is the complete graph Kn 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
References
- ^ Wilson, Robin J. (2004), Topics in Algebraic Graph Theory, Encyclopedia of Mathematics and its Applications, vol. 102, Cambridge University Press, p. 188, ISBN 9780521801973.
- ^ 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.
- ^ Hiraki, Akira; Nomura, Kazumasa; Suzuki, Hiroshi (2000), "Distance-regular graphs of valency 6 and ", Journal of Algebraic Combinatorics, 11 (2): 101–134, doi:10.1023/A:1008776031839, MR 1761910
- ^ 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
{{citation}}: CS1 maint: unflagged free DOI (link) - ^ 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.
- ^ 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.
