Gráfica de distancia unitaria

Gráfica geométrica con longitudes de aristas unitarias

Un gráfico de distancia unitaria con 16 vértices y 40 aristas.

En matemáticas , particularmente en la teoría de grafos geométricos , un grafo de distancia unitaria es un grafo formado a partir de una colección de puntos en el plano euclidiano conectando dos puntos siempre que la distancia entre ellos sea exactamente uno. Para distinguir estos grafos de una definición más amplia que permite que algunos pares de vértices no adyacentes estén a una distancia de uno, también se los puede llamar grafos de distancia unitaria estrictos o grafos de distancia unitaria fieles . Como familia hereditaria de grafos , se pueden caracterizar por subgrafos inducidos prohibidos . Los grafos de distancia unitaria incluyen los grafos de cactus , los grafos de cerillas y los grafos de centavo , y los grafos de hipercubo . Los grafos de Petersen generalizados son grafos de distancia unitaria no estrictos.

Un problema no resuelto de Paul Erdős pregunta cuántas aristas puede tener un grafo de distancia unitaria sobre vértices. El límite inferior más conocido está ligeramente por encima de la linealidad en —lejos del límite superior , proporcional a . El número de colores necesarios para colorear los grafos de distancia unitaria también es desconocido (el problema de Hadwiger–Nelson ): algunos grafos de distancia unitaria requieren cinco colores, y cada grafo de distancia unitaria puede colorearse con siete colores. Para cada número algebraico hay un grafo de distancia unitaria con dos vértices que deben estar separados por esa distancia. Según el teorema de Beckman–Quarles , las únicas transformaciones planas que preservan todos los grafos de distancia unitaria son las isometrías . ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n^{4/3}}$

Es posible construir un grafo de distancia unitaria de manera eficiente, dados sus puntos. Encontrar todas las distancias unitarias tiene aplicaciones en la comparación de patrones , donde puede ser un primer paso para encontrar copias congruentes de patrones más grandes. Sin embargo, determinar si un grafo dado puede representarse como un grafo de distancia unitaria es NP-hard y, más específicamente, completo para la teoría existencial de los números reales .

Definición

El grafo de distancia unitaria para un conjunto de puntos en el plano es el grafo no dirigido que tiene esos puntos como sus vértices , con una arista entre dos vértices siempre que su distancia euclidiana sea exactamente uno. Se dice que un grafo abstracto es un grafo de distancia unitaria si es posible encontrar ubicaciones distintas en el plano para sus vértices, de modo que sus aristas tengan longitud unitaria y de modo que todos los pares de vértices no adyacentes tengan distancias no unitarias. Cuando esto es posible, el grafo abstracto es isomorfo al grafo de distancia unitaria de las ubicaciones elegidas. Alternativamente, algunas fuentes usan una definición más amplia, permitiendo que pares de vértices no adyacentes estén a una distancia unitaria. Los grafos resultantes son los subgrafos de los grafos de distancia unitaria (como se define aquí). ^[2] Cuando la terminología puede ser ambigua, los grafos en los que las no aristas deben estar a una distancia no unitaria pueden llamarse grafos de distancia unitaria estrictos ^[3] o grafos de distancia unitaria fieles . ^[2] Los subgrafos de los grafos de distancia unitaria son equivalentemente los grafos que se pueden dibujar en el plano utilizando solo una longitud de arista. ^[4] Para abreviar, este artículo se refiere a estos como "grafos de distancia unitaria no estrictos".

Los gráficos de distancia unitaria no deben confundirse con los gráficos de disco unitario , que conectan pares de puntos cuando su distancia es menor o igual a uno, y se utilizan con frecuencia para modelar redes de comunicación inalámbrica. ^[5]

Ejemplos

El grafo completo sobre dos vértices es un grafo de distancia unitaria, como lo es el grafo completo sobre tres vértices (el grafo triangular ), pero no el grafo completo sobre cuatro vértices. ^[3] Generalizando el grafo triangular, cada grafo de ciclo es un grafo de distancia unitaria, realizado por un polígono regular . ^[4] Dos grafos de distancia unitaria finitos, conectados en un único vértice compartido, producen otro grafo de distancia unitaria, ya que uno puede rotarse con respecto al otro para evitar distancias unitarias adicionales no deseadas. ^[6] Al conectar grafos de esta manera, cada grafo de árbol o cactus finito puede realizarse como un grafo de distancia unitaria. ^[7]

Cualquier producto cartesiano de grafos de distancia unitaria produce otro grafo de distancia unitaria; sin embargo, no sucede lo mismo con otros productos de grafos comunes. Por ejemplo, el producto fuerte de grafos , aplicado a dos grafos cualesquiera no vacíos, produce subgrafos completos con cuatro vértices, que no son grafos de distancia unitaria. Los productos cartesianos de grafos de trayectoria forman grafos de cuadrícula de cualquier dimensión, los productos cartesianos del grafo completo en dos vértices son los grafos de hipercubo , ^[8] y los productos cartesianos de grafos triangulares son los grafos de Hamming . ^[9] ${\displaystyle H(d,3)}$

Otros gráficos específicos que son gráficos de distancia unitaria incluyen el gráfico de Petersen , ^[10] el gráfico de Heawood , ^[11] el gráfico de rueda (el único gráfico de rueda que es un gráfico de distancia unitaria), ^[3] y el gráfico de huso de Moser y el gráfico de Golomb (pequeños gráficos de distancia unitaria de 4 cromas ). ^[12] Todos los gráficos de Petersen generalizados , como el gráfico de Möbius-Kantor representado, son gráficos de distancia unitaria no estrictos. ^[13] ${\displaystyle W_{7}}$

Los grafos de cerillas son un caso especial de grafos de distancia unitaria, en los que no se cruzan aristas. Todo grafo de cerillas es un grafo plano ^[14] , pero algunos grafos de distancia unitaria que por lo demás son planos (como el huso de Moser) tienen un cruce en cada representación como grafo de distancia unitaria. Además, en el contexto de los grafos de distancia unitaria, el término "planar" debe usarse con cuidado, ya que algunos autores lo usan para referirse al plano en el que se definen las distancias unitarias, en lugar de a una prohibición de cruces ^[3] . Los grafos de centavo son un caso aún más especial de grafos de distancia unitaria y de cerillas, en los que cada par de vértices no adyacentes están separados por más de una unidad ^{[14] .}

Propiedades

Número de aristas

Problema sin resolver en matemáticas :

¿Cuántas distancias unitarias se pueden determinar mediante un conjunto de puntos? ${\displaystyle n}$

(más problemas sin resolver en matemáticas)

Paul Erdős  (1946) planteó el problema de estimar cuántos pares de puntos en un conjunto de puntos podrían estar a una distancia unitaria entre sí. En términos de teoría de grafos, la pregunta pregunta cuán denso puede ser un grafo de distancia unitaria, y la publicación de Erdős sobre esta cuestión fue uno de los primeros trabajos en teoría de grafos extremales . ^[15] Los grafos de hipercubo y los grafos de Hamming proporcionan un límite inferior en el número de distancias unitarias, proporcional a Al considerar puntos en una cuadrícula cuadrada con un espaciado cuidadosamente elegido, Erdős encontró un límite inferior mejorado de la forma para una constante , y ofreció $500 por una prueba de si el número de distancias unitarias también puede ser acotado por encima por una función de esta forma. ^[16] El límite superior más conocido para este problema es Este límite puede verse como el recuento de incidencias entre puntos y círculos unitarios, y está estrechamente relacionado con la desigualdad del número de cruces y con el teorema de Szemerédi-Trotter sobre incidencias entre puntos y líneas. ^[17] ${\displaystyle n}$ ${\displaystyle n\log n.}$ $${\displaystyle n^{1+c/\log \log n}}$$ ${\displaystyle c}$ $${\displaystyle {\sqrt[{3}]{\frac {29n^{4}}{4}}}\approx 1.936n^{4/3}.}$$

Para valores pequeños se conoce el número máximo exacto de aristas posibles. Para estos números de aristas son: ^[18] ${\displaystyle n}$ ${\displaystyle n=2,3,4,\dots }$

1, 3, 5, 7, 9, 12, 14, 18, 20, 23, 27, 30, 33, ... (secuencia A186705 en la OEIS )

Subgrafos prohibidos

Si un grafo dado no es un grafo de distancia unitaria no estricta, tampoco lo es ningún supergrafo de . Una idea similar funciona para los grafos de distancia unitaria estricta, pero utilizando el concepto de un subgrafo inducido , un subgrafo formado a partir de todas las aristas entre los pares de vértices en un subconjunto dado de vértices. Si no es un grafo de distancia unitaria estricta, entonces tampoco lo es ningún otro que tenga como subgrafo inducido. Debido a estas relaciones entre si un subgrafo o su supergrafo es un grafo de distancia unitaria, es posible describir los grafos de distancia unitaria por sus subgrafos prohibidos . Estos son los grafos mínimos que no son grafos de distancia unitaria del tipo dado. Se pueden utilizar para determinar si un grafo dado es un grafo de distancia unitaria, de cualquier tipo. es un grafo de distancia unitaria no estricta, si y solo si no es un supergrafo de un grafo prohibido para los grafos de distancia unitaria no estricta. es un grafo de distancia unitaria estricta, si y solo si no es un supergrafo inducido de un grafo prohibido para los grafos de distancia unitaria estricta. ^[8] ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$

Tanto para los grafos de distancia unitaria estrictos como para los no estrictos, los grafos prohibidos incluyen tanto el grafo completo como el grafo bipartito completo . Para , dondequiera que se coloquen los vértices en el lado de dos vértices de este grafo, hay como máximo dos posiciones a distancia unitaria de ellos para colocar los otros tres vértices, por lo que es imposible colocar los tres vértices en puntos distintos. ^[8] Estos son los únicos dos grafos prohibidos para los grafos de distancia unitaria no estrictos en hasta cinco vértices; hay seis grafos prohibidos en hasta siete vértices ^[6] y 74 en grafos de hasta nueve vértices. Debido a que pegar dos grafos de distancia unitaria (o subgrafos de los mismos) en un vértice produce grafos de distancia unitaria estrictos (respectivamente no estrictos), cada grafo prohibido es un grafo biconexo , uno que no se puede formar mediante este proceso de pegado. ^[19] ${\displaystyle K_{4}}$ ${\displaystyle K_{2,3}}$ ${\displaystyle K_{2,3}}$

El gráfico de rueda puede realizarse como un gráfico de distancia unitaria estricta con seis de sus vértices formando un hexágono regular unitario y el séptimo en el centro del hexágono. Quitar una de las aristas del vértice central produce un subgrafo que todavía tiene aristas de longitud unitaria, pero que no es un gráfico de distancia unitaria estricta. La colocación de sus vértices en hexágonos regulares es la única forma ( hasta la congruencia ) de colocar los vértices en ubicaciones distintas de modo que los vértices adyacentes estén separados por una distancia unitaria, y esta colocación también coloca los dos puntos finales de la arista faltante a una distancia unitaria. Por lo tanto, es un gráfico prohibido para los gráficos de distancia unitaria estricta, ^[20] pero no uno de los seis gráficos prohibidos para los gráficos de distancia unitaria no estricta. Otros ejemplos de gráficos que son gráficos de distancia unitaria no estricta pero no gráficos de distancia unitaria estricta incluyen el gráfico formado al quitar una arista exterior de y el gráfico de seis vértices formado a partir de un prisma triangular al quitar una arista de uno de sus triángulos. ^[19] ${\displaystyle W_{7}}$ ${\displaystyle W_{7}}$

Números algebraicos y rigidez

Para cada número algebraico , es posible construir un grafo de distancia unitaria en el que algún par de vértices estén a distancia en todas las representaciones de distancia unitaria de . ^[21] Este resultado implica una versión finita del teorema de Beckman-Quarles : para dos puntos cualesquiera y a distancia uno del otro, existe un grafo de distancia unitaria rígido finito que contiene y tal que cualquier transformación del plano que preserve las distancias unitarias en este grafo también preserva la distancia entre y . ^[22] El teorema completo de Beckman-Quarles establece que las únicas transformaciones del plano euclidiano (o un espacio euclidiano de dimensión superior) que preservan las distancias unitarias son las isometrías . De manera equivalente, para el grafo de distancia unitaria infinita generado por todos los puntos en el plano, todos los automorfismos del grafo preservan todas las distancias en el plano, no solo las distancias unitarias. ^[23] ${\displaystyle \alpha }$ ${\displaystyle G}$ ${\displaystyle \alpha }$ ${\displaystyle G}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle \alpha }$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle p}$ ${\displaystyle q}$

Si es un número algebraico de módulo 1 que no es raíz de la unidad , entonces las combinaciones enteras de potencias de forman un subgrupo finitamente generado del grupo aditivo de números complejos cuyo gráfico de distancia unitaria tiene grado infinito . Por ejemplo, puede elegirse como una de las dos raíces complejas del polinomio , lo que produce un gráfico de distancia unitaria de grado infinito con cuatro generadores. ^[24] ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle z^{4}-z^{3}-z^{2}-z+1}$

Colorante

Problema sin resolver en matemáticas :

¿Cuál es el número cromático más grande posible de un gráfico de distancia unitaria?

(más problemas sin resolver en matemáticas)

El problema de Hadwiger-Nelson se refiere al número cromático de grafos de distancia unitaria, y más específicamente del grafo de distancia unitaria infinita formado a partir de todos los puntos del plano euclidiano. Por el teorema de de Bruijn-Erdős , que supone el axioma de elección , esto es equivalente a preguntar por el número cromático más grande de un grafo de distancia unitaria finito. Existen grafos de distancia unitaria que requieren cinco colores en cualquier coloración adecuada, ^[25] y todos los grafos de distancia unitaria pueden colorearse con un máximo de siete colores. ^[26]

Una coloración de siete colores del gráfico de distancia unitaria infinita formado a partir de todos los puntos del plano, y el huso Moser de cuatro colores incrustado como un gráfico de distancia unitaria

Respondiendo a otra pregunta de Paul Erdős, es posible que los gráficos de distancia unitaria sin triángulos requieran cuatro colores. ^[27]

Enumeración

El número de gráficos de distancia unitaria estricta en vértices etiquetados es como máximo ^[2], como se expresa utilizando la notación O grande y la notación O pequeña. ${\displaystyle n\geq 4}$ $${\displaystyle {\binom {n(n-1)}{2n}}=O\left(2^{{\bigl (}4+o(1){\bigr )}n\log _{2}n}\right),}$$

Generalización a dimensiones superiores

La definición de un grafo de distancia unitaria puede generalizarse naturalmente a cualquier espacio euclidiano de dimensiones superiores . En tres dimensiones, los grafos de distancia unitaria de puntos tienen como máximo aristas, donde es una función de crecimiento muy lento relacionada con la función inversa de Ackermann . ^{[28] Este resultado conduce a un límite similar en el número de aristas de} los grafos de vecindad relativa tridimensionales . ^[29] En cuatro o más dimensiones, cualquier grafo bipartito completo es un grafo de distancia unitaria, realizado colocando los puntos en dos círculos perpendiculares con un centro común, por lo que los grafos de distancia unitaria pueden ser grafos densos . ^[7] Las fórmulas de enumeración para grafos de distancia unitaria se generalizan a dimensiones superiores y muestran que en dimensiones de cuatro o más el número de grafos de distancia unitaria estrictos es mucho mayor que el número de subgrafos de grafos de distancia unitaria. ^[2] ${\displaystyle n}$ ${\displaystyle n^{3/2}\beta (n)}$ ${\displaystyle \beta }$

Cualquier grafo finito puede ser incrustado como un grafo de distancia unitaria en una dimensión suficientemente alta. Algunos grafos pueden necesitar dimensiones muy diferentes para incrustaciones como grafos de distancia unitaria no estrictos y como grafos de distancia unitaria estrictos. Por ejemplo, el grafo de corona de vértice- ángulo puede ser incrustado en cuatro dimensiones como un grafo de distancia unitaria no estricto (es decir, de modo que todos sus bordes tengan longitud unitaria). Sin embargo, requiere al menos dimensiones para ser incrustado como un grafo de distancia unitaria estricto, de modo que sus bordes sean los únicos pares de distancia unitaria. ^[30] La dimensión necesaria para realizar cualquier grafo dado como un grafo de unidad estricto es como máximo el doble de su grado máximo. ^[31] ${\displaystyle 2n}$ ${\displaystyle n-2}$

Complejidad computacional

La construcción de un gráfico de distancia unitaria a partir de sus puntos es un paso importante para otros algoritmos que buscan copias congruentes de algún patrón en un conjunto de puntos más grande. Estos algoritmos utilizan esta construcción para buscar posiciones candidatas donde una de las distancias en el patrón está presente, y luego utilizan otros métodos para probar el resto del patrón para cada candidato. ^[32] Se puede aplicar un método de Matoušek (1993) a este problema, ^[32] produciendo un algoritmo para encontrar el gráfico de distancia unitaria de un conjunto de puntos planar en el tiempo donde es la función logarítmica iterada de crecimiento lento . ^[33] ${\displaystyle n^{4/3}2^{O(\log ^{*}n)}}$ ${\displaystyle \log ^{*}}$

Es NP-difícil —y más específicamente, completo para la teoría existencial de los números reales— comprobar si un gráfico dado es un gráfico de distancia unitaria (estricto o no estricto) en el plano. ^[34] También es NP-completo determinar si un gráfico de distancia unitaria planar tiene un ciclo hamiltoniano , incluso cuando todos los vértices del gráfico tienen coordenadas enteras conocidas. ^[35]

Referencias

Notas

1. Griffiths (2019).
2. Alon y Kupavskii (2014).
3. Gervacio, Lim y Maehara (2008).
4. Carmi y col. (2008).
5. Huson y Sen (1995).
6. Chilakamarri y Mahoney (1995).
7. Erdős, Harary y Tutte (1965).
8. Horvat y Pisanski (2010).
9. Brouwer y Haemers (2012).
10. Erdős, Harary y Tutte (1965); Griffiths (2019)
11. Gerbracht (2009).
12. Soifer (2008), págs. 14-15, 19.
13. Žitnik, Horvat y Pisanski (2012).
14. Lavollée & Swanepoel (2022).
15. Szemerédi (2016).
16. Erdős (1990).
17. Spencer, Szemerédi y Trotter (1984); Clarkson y cols. (1990); Pach y Tardos (2005); Ágoston y Pálvölgyi (2022)
18. Ágoston y Pálvölgyi (2022).
19. Globus y Parshall (2020).
20. Soifer (2008), pág. 94.
21. Maehara (1991, 1992).
22. Tszka (2000).
23. Beckman y Quarles (1953).
24. Radchenko (2021).
25. Langin (2018); de Grey (2018)
26. Soifer (2008), pág. 17.
27. Wormald (1979); Chilakamarri (1995); O'Donnell (1995).
28. Clarkson y otros (1990).
29. Jaromczyk y Toussaint (1992).
30. Erdős y Simonovits (1980).
31. Maehara y Rödl (1990).
32. Braß (2002).
33. Matoušek (1993); consulte también Chan y Zheng (2022) para un algoritmo estrechamente relacionado para enumerar incidencias de puntos y líneas en el tiempo . ${\displaystyle O(n^{4/3})}$
34. Schaefer (2013).
35. Itai, Papadimitriou y Szwarcfiter (1982).

Fuentes

• Ágoston, Peter; Pálvölgyi, Dömötör (abril de 2022), "Un factor constante mejorado para el problema de distancia unitaria", Studia Scientiarum Mathematicarum Hungarica , 59 (1), Akademiai Kiado Zrt.: 40–57, arXiv : 2006.06285 , doi :10.1556/012.2022.01517 , S2CID  218479287
• Alon, Noga ; Kupavskii, Andrey (2014), "Dos nociones de grafos de distancia unitaria" (PDF) , Journal of Combinatorial Theory , Serie A, 125 : 1–17, doi :10.1016/j.jcta.2014.02.006, MR  3207464, S2CID  12043969
• Beckman, FS; Quarles, DA Jr. (1953), "Sobre isometrías de espacios euclidianos", Actas de la American Mathematical Society , 4 (5): 810–815, doi : 10.2307/2032415 , JSTOR  2032415, MR  0058193
• Braß, Peter (2002), "Problemas de geometría combinatoria en el reconocimiento de patrones", Geometría discreta y computacional , 28 (4): 495–510, doi : 10.1007/s00454-002-2884-3 , MR  1949897
• Brouwer, Andries E .; Haemers, Willem H. (2012), Espectros de gráficos , Universitext, Nueva York: Springer, p. 178, doi :10.1007/978-1-4614-1939-6, ISBN 978-1-4614-1938-9, Sr.  2882891
• Carmi, Paz; Dujmović, Vida ; Morin, Pat ; Wood, David R. (2008), "Distancias distintas en dibujos de grafos", Electronic Journal of Combinatorics , 15 (1): Research Paper 107, arXiv : 0804.3690 , doi :10.37236/831, MR  2438579, S2CID  2955082
• Chan, Timothy M. ; Zheng, Da Wei (2022), "El problema de Hopcroft, el recorte de log-star, la cascada fraccionaria 2d y los árboles de decisión", en Naor, Joseph (Seffi); Buchbinder, Niv (eds.), Actas del Simposio ACM-SIAM 2022 sobre algoritmos discretos, SODA 2022, Conferencia virtual / Alexandria, VA, EE. UU., 9 al 12 de enero de 2022 , Society for Industrial and Applied Mathematics, págs. 190–210, arXiv : 2111.03744 , doi :10.1137/1.9781611977073.10, S2CID  243847672
• Chilakamarri, Kiran B. (1995), "Un gráfico de distancia unitaria de 4 cromas sin triángulos", Geombinatorics , 4 (3): 64–76, MR  1313386
• Chilakamarri, Kiran B.; Mahoney, Carolyn R. (1995), "Gráficos de distancias unitarias prohibidas máximas y mínimas en el plano", Boletín del Instituto de Combinatoria y sus Aplicaciones , 13 : 35–43, MR  1314500, citado por Globus y Parshall (2020)
• Clarkson, Kenneth L. ; Edelsbrunner, Herbert ; Guibas, Leonidas J. ; Sharir, Micha ; Welzl, Emo (1990), "Límites de complejidad combinatoria para arreglos de curvas y esferas", Geometría discreta y computacional , 5 (2): 99–160, doi : 10.1007/BF02187783 , MR  1032370, S2CID  28143698
• de Grey, Aubrey DNJ (2018), "El número cromático del plano es al menos 5", Geombinatorics , 28 : 5–18, arXiv : 1804.02385 , MR  3820926
• Erdős, Paul (1946), "Sobre conjuntos de distancias de puntos", American Mathematical Monthly , 53 (5): 248–250, doi :10.2307/2305092, JSTOR  2305092 ${\displaystyle n}$
• Erdős, Paul ; Harary, Frank ; Tutte, William T. (1965), "Sobre la dimensión de un gráfico" (PDF) , Mathematika , 12 (2): 118–122, doi :10.1112/S0025579300005222, hdl : 2027.42/152495 , MR  0188096
• Erdős, Paul ; Simonovits, Miklós (1980), "Sobre el número cromático de gráficos geométricos", Ars Combinatoria , 9 : 229–246, citado por Soifer (2008, p. 97)
• Erdős, Paul (1990), "Algunos de mis problemas favoritos sin resolver", en Baker, A.; Bollobás, B.; Hajnal, A. (eds.), Un homenaje a Paul Erdős , Cambridge University Press, págs. 467–478, ISBN 0-521-38101-0, Sr.  1117038; véase en particular la pág. 475
• Gerbracht, Eberhard H.-A. (2009), Once incrustaciones de distancia unitaria del gráfico de Heawood , arXiv : 0912.5395 , Bibcode :2009arXiv0912.5395G
• Gervacio, Severino V.; Lim, Yvette F.; Maehara, Hiroshi (2008), "Gráficos de distancia unitaria plana que tienen complemento de distancia unitaria plana", Discrete Mathematics , 308 (10): 1973–1984, doi : 10.1016/j.disc.2007.04.050
• Globus, Aidan; Parshall, Hans (2020), "Gráficos de unidades de distancia pequeñas en el plano", Boletín del Instituto de Combinatoria y sus Aplicaciones , 90 : 107–138, arXiv : 1905.07829 , MR  4156400
• Griffiths, Martin (junio de 2019), "103.27 Una propiedad de un gráfico de unidad-distancia particular", The Mathematical Gazette , 103 (557): 353–356, doi :10.1017/mag.2019.74, S2CID  233361952
• Horvat, Boris; Pisanski, Tomaž (2010), "Productos de gráficos de distancia unitaria", Discrete Mathematics , 310 (12): 1783–1792, doi : 10.1016/j.disc.2009.11.035 , MR  2610282
• Huson, Mark L.; Sen, Arunabha (1995), "Algoritmos de programación de transmisiones para redes de radio", Conferencia de Comunicaciones Militares, IEEE MILCOM '95 , vol. 2, págs. 647–651, doi :10.1109/MILCOM.1995.483546, ISBN 0-7803-2489-7, Número de identificación del sujeto  62039740
• Itai, Alon; Papadimitriou, Christos H .; Szwarcfiter, Jayme Luiz (1982), "Caminos de Hamilton en gráficos de cuadrícula", SIAM Journal on Computing , 11 (4): 676–686, CiteSeerX  10.1.1.383.1078 , doi :10.1137/0211056, MR  0677661
• Jaromczyk, Jerzy W.; Toussaint, Godfried T. (1992), "Gráficos de vecindad relativa y sus parientes", Actas del IEEE , 80 (9): 1502–1517, doi :10.1109/5.163414
• Langin, Katie (18 de abril de 2018), "Un matemático aficionado resuelve un problema matemático que tiene décadas de antigüedad", Science
• Lavollée, Jérémy; Swanepoel, Konrad J. (2022), "Limitar el número de aristas de los grafos de cerillas", SIAM Journal on Discrete Mathematics , 36 (1): 777–785, arXiv : 2108.07522 , doi :10.1137/21M1441134, MR  4399020, S2CID  237142624
• Maehara, Hiroshi (1991), "Distancias en un gráfico de distancia unitaria rígido en el plano", Matemáticas Aplicadas Discretas , 31 (2): 193–200, doi : 10.1016/0166-218X(91)90070-D
• Maehara, Hiroshi (1992), "Extensión de un marco de barras unitarias flexible a uno rígido", Discrete Mathematics , 108 (1–3): 167–174, doi : 10.1016/0012-365X(92)90671-2 , MR  1189840
• Maehara, Hiroshi; Rödl, Vojtech (1990), "Sobre la dimensión para representar un gráfico mediante un gráfico de distancia unitaria", Graphs and Combinatorics , 6 (4): 365–367, doi :10.1007/BF01787703, S2CID  31148911
• Matoušek, Jiří (1993), "Búsqueda de rangos con cortes jerárquicos eficientes", Geometría discreta y computacional , 10 (2): 157–182, doi : 10.1007/BF02573972 , MR  1220545
• O'Donnell, Paul (1995), "Un gráfico de distancia unitaria sin triángulos de 40 vértices y 4 cromáticos", Geombinatorics , 5 (1): 31–34, MR  1337155
• Pach, János ; Tardos, Gábor (2005), "Patrones prohibidos y distancias unitarias", en Mitchell, Joseph SB; Rote, Günter (eds.), Actas del 21.º Simposio ACM sobre geometría computacional, Pisa, Italia, 6-8 de junio de 2005 , Association for Computing Machinery, págs. 1–9, doi :10.1145/1064092.1064096, MR  2460341, S2CID  18752227
• Radchenko, Danylo (2021), "Gráficos de distancia unitaria y números enteros algebraicos", Geometría discreta y computacional , 66 (1): 269–272, doi :10.1007/s00454-019-00152-4, hdl : 21.11116/0000-0006-9CFD-E , MR  4270642, S2CID  119682489
• Schaefer, Marcus (2013), "Realización de grafos y vínculos", en Pach, János (ed.), Treinta ensayos sobre teoría de grafos geométricos , Springer, págs. 461–482, CiteSeerX  10.1.1.220.9651 , doi :10.1007/978-1-4614-0110-0_24, ISBN 978-1-4614-0109-4
• Soifer, Alexander (2008), El libro para colorear matemático , Springer-Verlag, ISBN 978-0-387-74640-1
• Spencer, Joel ; Szemerédi, Endre ; Trotter, William T. (1984), "Distancias unitarias en el plano euclidiano", en Bollobás, Béla (ed.), Graph Theory and Combinatorics , Londres: Academic Press, págs. 293–308, ISBN 978-0-12-111760-3, Sr.  0777185
• Szemerédi, Endre (2016), "El problema de la distancia unitaria de Erdős", en Nash, John Forbes Jr .; Rassias, Michael Th. (eds.), Problemas abiertos en matemáticas , Cham, Suiza: Springer, págs. 459–477, doi :10.1007/978-3-319-32162-2_15, MR  3526946
• Tyszka, Apoloniusz (2000), "Versiones discretas del teorema de Beckman-Quarles", Aequationes Mathematicae , 59 (1–2): 124–133, arXiv : math/9904047 , doi :10.1007/PL00000119, MR  1741475, S2CID  14803182
• Wormald, Nicholas (1979), "Un gráfico de 4 cromas con un dibujo de plano especial", Journal of the Australian Mathematical Society , Serie A, 28 (1): 1–8, doi : 10.1017/S1446788700014865 , MR  0541161, S2CID  124067465
• Žitnik, Arjana; Horvat, Boris; Pisanski, Tomaž (2012), "Todos los gráficos de Petersen generalizados son gráficos de distancia unitaria", Journal of the Korean Mathematical Society , 49 (3): 475–491, doi : 10.4134/JKMS.2012.49.3.475 , MR  2953031

Enlaces externos

• Venkatasubramanian, Suresh, "Problema 39: Distancias entre conjuntos de puntos en R2 y R3", The Open Problems Project
• Weisstein, Eric W. , "Gráfico de distancia unitaria", MathWorld