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 two vertices ui and 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.

The halved cube graph of order 4, obtained as the bipartite half of an order-4 hypercube graph

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 is the bipartite half of another graph, formed by subdividing the edges of into two-edge paths. More generally, a representation of as a bipartite half can be found by taking any clique edge cover of 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 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
  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 0932118, S2CID 28803214.
  3. 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
  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, 138, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 13:1–13:15, doi:10.4230/LIPIcs.MFCS.2019.13
  5. Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5, 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.