Gráfico de amistad

Gráfica de triángulos con un vértice compartido

Los gráficos de amistad F ₂ , F ₃ y F ₄ .

En el campo matemático de la teoría de grafos , el grafo de la amistad (o grafo de molino de viento holandés o n -fan ) F _n es un grafo plano , no dirigido, con 2 n + 1 vértices y 3 n aristas. ^[1]

El gráfico de amistad F _n se puede construir uniendo n copias del gráfico de ciclo C ₃ con un vértice común, que se convierte en un vértice universal para el gráfico. ^[2]

Por construcción, el grafo de amistad F _n es isomorfo al grafo de molino de viento Wd(3, n ) . Es una distancia unitaria con circunferencia 3, diámetro 2 y radio 1. El grafo F ₂ es isomorfo al grafo de mariposa . Los grafos de amistad se generalizan mediante los grafos de cactus triangulares .

Teorema de la amistad

El teorema de la amistad de Paul Erdős , Alfréd Rényi y Vera T. Sós  (1966) ^[3] establece que los grafos finitos con la propiedad de que cada dos vértices tienen exactamente un vecino en común son exactamente los grafos de amistad. De manera informal, si un grupo de personas tiene la propiedad de que cada par de personas tiene exactamente un amigo en común, entonces debe haber una persona que sea amiga de todas las demás. Sin embargo, para grafos infinitos, puede haber muchos grafos diferentes con la misma cardinalidad que tengan esta propiedad. ^[4]

Mertzios y Unger dieron una prueba combinatoria del teorema de la amistad. ^[5] Otra prueba fue dada por Craig Huneke. ^[6] Alexander van der Vekens informó sobre una prueba formalizada en Metamath en octubre de 2018 en la lista de correo de Metamath. ^[7]

Etiquetado y coloración

El grafo de la amistad tiene número cromático 3 e índice cromático 2 n . Su polinomio cromático se puede deducir del polinomio cromático del grafo del ciclo C ₃ y es igual a

${\displaystyle (x-2)^{n}(x-1)^{n}x}$.

El grafo de amistad F _n es elegante si y solo si n es impar. Es elegante si y solo si n ≡ 0 (mod 4) o n ≡ 1 (mod 4) . ^{[8] [9]}

Cada gráfico de amistad es un factor crítico .

Teoría de grafos extremos

Según la teoría de grafos extremales , todo grafo con suficientes aristas (en relación con su número de vértices) debe contener un abanico como subgrafo. Más específicamente, esto es cierto para un grafo de vértices si el número de aristas es ${\displaystyle k}$ ${\displaystyle n}$

${\displaystyle \left\lfloor {\frac {n^{2}}{4}}\right\rfloor +f(k),}$

donde es si es impar, y es si es par. Estos límites generalizan el teorema de Turán sobre el número de aristas en un grafo sin triángulos , y son los mejores límites posibles para este problema, ya que para cualquier número menor de aristas existen grafos que no contienen un abanico. ^[10] ${\displaystyle f(k)}$ ${\displaystyle k^{2}-k}$ ${\displaystyle k}$ ${\displaystyle f(k)}$ ${\displaystyle k^{2}-3k/2}$ ${\displaystyle k}$ ${\displaystyle k}$

Generalizaciones

Dos vértices cualesquiera que tengan exactamente un vecino en común es equivalente a que dos vértices cualesquiera estén conectados por exactamente un camino de longitud dos. Esto se ha generalizado a los -grafos, en los que dos vértices cualesquiera están conectados por un único camino de longitud . Porque no se conocen tales grafos, y la afirmación de su no existencia es la conjetura de Kotzig . ${\displaystyle P_{k}}$ ${\displaystyle k}$ ${\displaystyle k\geq 3}$

Referencias

1. Weisstein, Eric W. , "Gráfico del molino de viento holandés", MathWorld
2. Gallian, Joseph A. (3 de enero de 2007), "Un estudio dinámico del etiquetado de gráficos", Electronic Journal of Combinatorics : DS6, doi : 10.37236/27.
3. Erdős, Paul ; Rényi, Alfred ; Sós, Vera T. (1966), "Sobre un problema de teoría de grafos" (PDF) , Studia Sci. Matemáticas. Hungría. , 1 : 215–235.
4. Chvátal, Václav ; Kotzig, Anton ; Rosenberg, Ivo G.; Davies, Roy O. (1976), "Existen grafos de amistad de cardinales ", Canadian Mathematical Bulletin , 19 (4): 431–433, doi : 10.4153/cmb-1976-064-1 ${\displaystyle \scriptstyle 2^{\aleph _{\alpha }}}$ ${\displaystyle \scriptstyle \aleph _{\alpha }}$.
5. Mertzios, George; Walter Unger (2008), "El problema de la amistad en los grafos" (PDF) , Relaciones, órdenes y grafos: interacción con la informática
6. Huneke, Craig (1 de enero de 2002), "El teorema de la amistad", The American Mathematical Monthly , 109 (2): 192–194, doi :10.2307/2695332, JSTOR  2695332
7. van der Vekens, Alexander (11 de octubre de 2018), "Teorema de la amistad (n.° 83 de la "lista de 100 teoremas")", lista de correo Metamath
8. Bermond, J.-C.; Brouwer, AE ; Germa, A. (1978), "Systèmes de triplets et différences associées", Problèmes Combinatoires et Théorie des Graphes (Univ. Orsay, 1976) , Colloq. Interno. del CNRS, vol. 260, CNRS, París, págs. 35–38, SEÑOR  0539936.
9. Bermond, J.-C.; Kotzig, A .; Turgeon, J. (1978), "Sobre un problema combinatorio de antenas en radioastronomía", Combinatoria (Proc. Quinto Coloq. Húngaro, Keszthely, 1976), vol. Yo , Coloq. Matemáticas. Soc. János Bolyai, vol. 18, Holanda Septentrional, Ámsterdam-Nueva York, págs. 135-149, MR  0519261.
10. Erdős, P. ; Füredi, Z. ; Gould, RJ ; Gunderson, DS (1995), "Gráficos extremos para triángulos que se intersecan", Journal of Combinatorial Theory , Serie B, 64 (1): 89–100, doi : 10.1006/jctb.1995.1026 , MR  1328293.