En teoría de grafos , el medio o medio cuadrado bipartito 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 un borde u i u j para cada dos vértices u i y u j en U que están a una distancia de dos entre sí en G . [1] Es decir, en una notación más compacta, la mitad bipartita esG 2 [ U ] donde el superíndice 2 denota el cuadrado de un gráfico y los corchetes denotan un subgrafo inducido .
Ejemplos de
Por ejemplo, la mitad bipartita del grafo bipartito completo K n , n es el grafo completo K n y la mitad bipartita del grafo de hipercubo es el grafo de cubo reducido a la mitad . Cuando G es un gráfico regular a la distancia , sus dos mitades bipartitas son regulares a la distancia. [2] Por ejemplo, la gráfica de Foster dividida a la mitad es una de las finitas gráficas lineales locales de distancia regular de grado 6 . [3]
Representación y dureza
Cada grafico es la mitad bipartita de otro gráfico, formado al subdividir los bordes de en caminos de dos bordes. De manera más general, una representación decomo una mitad bipartita se puede encontrar tomando cualquier cubierta de borde de camarilla dey reemplazando cada camarilla por una estrella . [4] Toda representación surge de esta manera. Dado que encontrar la cobertura de borde de la camarilla más pequeña es NP-hard, también lo es encontrar la gráfica con la menor cantidad de vértices para la cuales la mitad bipartita. [5]
Casos especiales
Los gráficos de mapa , es decir, los gráficos de intersección de regiones interiores disjuntas simplemente conectadas en el plano, son exactamente las mitades bipartitas de gráficos planos bipartitos . [6]
Ver también
Referencias
- ^ Wilson, Robin J. (2004), Temas de la teoría de gráficos algebraicos , Enciclopedia de las matemáticas y sus aplicaciones, 102 , Cambridge University Press, p. 188, ISBN 9780521801973.
- ^ Chihara, Laura; Stanton, Dennis (1986), "Esquemas de asociación y transformaciones cuadráticas para polinomios ortogonales", Gráficos y combinatorios , 2 (2): 101–112, doi : 10.1007 / BF01788084 , MR 0932118 , S2CID 28803214.
- ^ 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
- ^ Le, Hoàng-Oanh; Le, Van Bang (2019), "Representaciones restringidas de gráficos de mapas y medios cuadrados", en Rossmanith, Peter; Heggernes, Pinar; Katoen, Joost-Pieter (eds.), 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019, 26-30 de agosto de 2019, Aquisgrán, Alemania , LIPIcs, 138 , Schloss Dagstuhl - Leibniz-Zentrum für Informatik, págs.13 : 1–13: 15, doi : 10.4230 / LIPIcs.MFCS.2019.13
- ^ Garey, Michael R .; Johnson, David S. (1979), Computadoras e intratabilidad: una guía para la teoría de NP-Completeness , W. H. Freeman , ISBN 0-7167-1045-5, Problema GT59.
- ^ Chen, Zhi-Zhong; Grigni, Miguel Ángel; Papadimitriou, Christos H. (2002), "Gráficos de mapa", Journal of the ACM , 49 (2): 127-138, arXiv : cs / 9910013 , doi : 10.1145 / 506147.506148 , MR 2147819 , S2CID 2657838.