Gráfico de amistad

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

La amistad grafica F ₂ , F ₃ y F ₄ .

En el campo matemático de la teoría de grafos , el gráfico de la amistad (o gráfico del molino de viento holandés o n -fan ) F _n es un gráfico 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 gráfico de amistad F _n es isomorfo al gráfico de molino de viento Wd(3, n ) . Es una distancia unitaria con circunferencia 3, diámetro 2 y radio 1. La gráfica F ₂ es isomorfa a la gráfica de mariposa . Los gráficos de amistad se generalizan mediante los gráficos triangulares de cactus .

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 la 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 gráficos infinitos, puede haber muchos gráficos diferentes con la misma cardinalidad que tengan esta propiedad. ^[4]

Mertzios y Unger dieron una prueba combinatoria del teorema de la amistad. ^[5] Craig Huneke proporcionó otra prueba. ^[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 coloreado

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

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

El gráfico de amistad F _n tiene bordes elegantes si y sólo si n es impar. Es elegante si y sólo si n ≡ 0 (mod 4) o n ≡ 1 (mod 4) . ^{[8] [9]}

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

Teoría de grafos extremos

Según la teoría de grafos extremos , cada gráfico 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 gráfico 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 gráfico sin triángulos , y son los mejores límites posibles para este problema, en el sentido de que para cualquier número menor de aristas existen gráficos 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}$

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, Antón ; Rosenberg, Ivo G.; Davies, Roy O. (1976), "Hay gráficas de amistad de cardenales ", 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 gráficos" (PDF) , Relaciones, órdenes y gráficos: 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 de 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 cruzan", Journal of Combinatorial Theory , Serie B, 64 (1): 89–100, doi : 10.1006/jctb.1995.1026 , MR  1328293.