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