Teorema de la amistad: En ciertas redes hay siempre un amigo de todos

Grafo de la Amistad

Wikipedia



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

El grafo de amistad F_n se puede construir uniendo n copias del grafo de ciclo C3 con un vértice común. [2]

Por construcción, el grafo de amistad F_n es isomorfo al grafo de molino de viento Wd(3,n). Es la unidad de distancia con circunferencia 3, diámetro 2 y radio 1. El gráfico F₂ es isomorfo al grafo de mariposa.

Teorema de la amistad

El teorema de amistad de Paul Erdős, Alfréd Rényi y Vera T. Sós (1966) [3] afirma 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 todos los demás. Sin embargo, para los grafos infinitos, puede haber muchos grafos diferentes con la misma cardinalidad que tienen esta propiedad. [4]

Mertzios y Unger dieron una prueba combinatoria del teorema de la amistad. [5] Craig Huneke dio otra prueba. [6] Alexander van der Vekens reportó una prueba formal en Metamath en octubre de 2018 en la lista de correo de Metamath. [7]

Etiquetado y coloración.

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

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 grafo de amistad es factor-crítico.

Teoría de grafos extremos

De acuerdo con la teoría de los grafos extremos, cada grafo con suficientes enlaces (en relación con su número de vértices) debe contener un ${\displaystyle k}$-fan como subgrafo. Más específicamente, esto es cierto para un grafo de n vértices si el número de enlaces es



donde es si k es impar y si si k es par. Estos límites generalizan el teorema de Turán sobre el número de bordes en un gráfico sin triángulos, y son los mejores límites posibles para este problema, ya que para un número menor de bordes existen gráficos que no contienen k-fan.

Referencias

1. Weisstein, Eric W. "Dutch Windmill Graph". MathWorld.
2. Gallian, J. A. (January 3, 2007), "Dynamic Survey DS6: Graph Labeling" (PDF), Electronic Journal of Combinatorics, DS6, 1-58. 
3. Erdős, Paul; Rényi, Alfréd; Sós, Vera T. (1966), "On a problem of graph theory" (PDF), Studia Sci. Math. Hungar., 1: 215–235. 
4. Chvátal, Václav; Kotzig, Anton; Rosenberg, Ivo G.; Davies, Roy O. (1976),  "There are ${\displaystyle \scriptstyle 2^{\aleph _{\alpha }}}$ friendship graphs of cardinal ${\displaystyle \scriptstyle \aleph _{\alpha }}$", Canadian Mathematical Bulletin, 19 (4): 431–433, doi:10.4153/cmb-1976-064-1.
5. Mertzios, George; Walter Unger (2008), "The friendship problem on graphs" (PDF), Relations, Orders and Graphs: Interaction with Computer Science
6. Huneke, Craig (1 January 2002), "The Friendship Theorem", The American Mathematical Monthly, 109 (2): 192–194, doi:10.2307/2695332, JSTOR 2695332 
7. Alexander van der Vekens, Friendship Theorem (#83 of "100 theorem list") (11 October 2018) https://groups.google.com/forum/#!msg/metamath/j3EjD6ibhvo/ZVlOD3noBAAJ 
8. Bermond, J.-C.; Brouwer, A. E.; Germa, A. (1978), "Systèmes de triplets et différences associées", Problèmes Combinatoires et Théorie des Graphes (Univ. Orsay, 1976), Colloq. Intern. du CNRS, 260, CNRS, Paris, pp. 35–38, MR 0539936.
9. Bermond, J.-C.; Kotzig, A.; Turgeon, J. (1978), "On a combinatorial problem of antennas in radioastronomy", Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, Colloq. Math. Soc. János Bolyai, 18, North-Holland, Amsterdam-New York, pp. 135–149, MR 0519261. 
10. Erdős, P.; Füredi, Z.; Gould, R. J.; Gunderson, D. S. (1995), "Extremal graphs for intersecting triangles", Journal of Combinatorial Theory, Series B, 64 (1): 89–100, doi:10.1006/jctb.1995.1026, MR 1328293.