Bipartitní polovina - Bipartite half

Rozdělený krychlový graf řádu 4, získaný jako bipartitní polovina grafu hyperkrychle řádu 4

v teorie grafů, bipartitní polovina nebo napůl čtverec a bipartitní graf G = (U,PROTI,E) je graf, jehož množina vrcholů je jednou ze dvou stran bipartice (bez ztráty obecnosti, U) a ve kterém je hrana uiuj pro každé dva vrcholy ui a uj v U které jsou ve vzdálenosti dva od sebe v G.[1] To znamená, že v kompaktnější notaci je bipartitní polovina G2[U] kde horní index 2 označuje čtverec grafu a hranaté závorky označují indukovaný podgraf.

Například bipartitní polovina EU kompletní bipartitní graf K.n,n je kompletní graf K.n a bipartitní polovina hyperkrychlový graf je graf na polovinu krychle.Když G je vzdálenost-pravidelný graf, jeho dvě bipartitní poloviny jsou obě vzdálené pravidelné.[2] Například na polovinu Pěstounský graf je jedním z konečně mnoha pravidelných vzdáleností stupně 6 lokálně lineární grafy.[3]

The mapové grafy, toto je průsečíkové grafy vnitřně disjunktních jednoduše spojených oblastí v rovině, jsou přesně bipartitní poloviny bipartity rovinné grafy.[4]

Viz také

Reference

  1. ^ Wilson, Robin J. (2004), Témata v algebraické teorii grafů Encyklopedie matematiky a její aplikace, 102, Cambridge University Press, str. 188, ISBN  9780521801973.
  2. ^ Chihara, Laura; Stanton, Dennis (1986), „Asociační schémata a kvadratické transformace pro ortogonální polynomy“, Grafy a kombinatorika, 2 (2): 101–112, doi:10.1007 / BF01788084, PAN  0932118.
  3. ^ Hiraki, Akira; Nomura, Kazumasa; Suzuki, Hiroshi (2000), „Vzdálené pravidelné grafy valence 6 a ", Journal of Algebraic Combinatorics, 11 (2): 101–134, doi:10.1023 / A: 1008776031839, PAN  1761910
  4. ^ Chen, Zhi-Zhong; Grigni, Michelangelo; Papadimitriou, Christos H. (2002), "Mapové grafy", Deník ACM, 49 (2): 127–138, arXiv:cs / 9910013, doi:10.1145/506147.506148, PAN  2147819.