stringtranslate.com

Mitad bipartita

El gráfico cúbico dividido por la mitad de orden 4, obtenido como la mitad bipartita de un gráfico hipercubo de orden 4

En teoría de grafos , la mitad bipartita o medio cuadrado de un grafo bipartito G = ( U , V , E ) es un grafo cuyo conjunto de vértices es uno de los dos lados de la bipartición ( sin pérdida de generalidad , U ) y en el que hay una arista u i u j para cada par de vértices u i , u j en U que estén a distancia dos entre sí en G . [1] Es decir, en una notación más compacta, la mitad bipartita es G 2 [ U ] donde el superíndice 2 denota el cuadrado de un grafo y los corchetes denotan un subgrafo inducido .

Ejemplos

Por ejemplo, la mitad bipartita del grafo bipartito completo K n , n es el grafo completo K n y la mitad bipartita del grafo hipercubo es el grafo cúbico partido por la mitad . Cuando G es un grafo regular en distancias , sus dos mitades bipartitas son ambas regulares en distancias. [2] Por ejemplo, el grafo de Foster partido por la mitad es uno de los muchos grafos localmente lineales regulares en distancias de grado 6 . [3]

Representación y dureza

Cada grafo G es la mitad bipartita de otro grafo, formado al subdividir las aristas de G en dos caminos de aristas. De manera más general, una representación de G como una mitad bipartita se puede encontrar tomando cualquier cobertura de aristas de clique de G y reemplazando cada clique por una estrella . [4] Toda representación surge de esta manera. Dado que encontrar la cobertura de aristas de clique más pequeña es NP-hard, también lo es encontrar el grafo con la menor cantidad de vértices para el cual G es la mitad bipartita. [5]

Casos especiales

Los gráficos de mapas , es decir, los gráficos de intersección de regiones simplemente conexas disjuntas interiores en el plano, son exactamente las mitades bipartitas de los gráficos planares bipartitos . [6]

Véase también

Referencias

  1. ^ Wilson, Robin J. (2004), Temas de teoría de grafos algebraicos, Enciclopedia de matemáticas y sus aplicaciones, vol. 102, Cambridge University Press, pág. 188, ISBN 9780521801973.
  2. ^ Chihara, Laura; Stanton, Dennis (1986), "Esquemas de asociación y transformaciones cuadráticas para polinomios ortogonales", Graphs and Combinatorics , 2 (2): 101–112, doi :10.1007/BF01788084, MR  0932118, S2CID  28803214.
  3. ^ Hiraki, Akira; Nomura, Kazumasa; Suzuki, Hiroshi (2000), "Gráficos regulares a distancia de valencia 6 y ", Journal of Algebraic Combinatorics , 11 (2): 101–134, doi : 10.1023/A:1008776031839 , MR  1761910
  4. ^ Le, Hoàng-Oanh; Le, Van Bang (2019), "Representaciones restringidas de gráficos de mapas y semicuadrados", en Rossmanith, Peter; Heggernes, Pinar; Katoen, Joost-Pieter (eds.), 44.º Simposio internacional sobre fundamentos matemáticos de la informática, MFCS 2019, 26 al 30 de agosto de 2019, Aquisgrán, Alemania , LIPIcs, vol. 138, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, págs. 13:1–13:15, doi : 10.4230/LIPIcs.MFCS.2019.13 , ISBN 9783959771177
  5. ^ Garey, Michael R. ; Johnson, David S. (1979). Computadoras e intratabilidad: una guía para la teoría de la NP-completitud . Serie de libros sobre ciencias matemáticas (1.ª ed.). Nueva York: WH Freeman and Company . ISBN 9780716710455. Sr.  0519066. OCLC  247570676., Problema GT59.
  6. ^ Chen, Zhi-Zhong; Grigni, Miguel Ángel; Papadimitriou, Christos H. (2002), "Gráficos de mapas", Journal of the ACM , 49 (2): 127–138, arXiv : cs/9910013 , doi :10.1145/506147.506148, MR  2147819, S2CID  2657838.