Gráfico de amistad

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 -ventilador ) F _n es un grafo planar no dirigido con 2 n + 1 vértices y 3 n aristas. ^{[ 1 ]}

El grafo de amistad F _n se puede construir uniendo n copias del grafo cíclico C ₃ con un vértice común, que se convierte en un vértice universal para el grafo. ^{[ 2 ]}

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

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 par de vértices tiene exactamente un vecino en común son precisamente 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 demostración combinatoria del teorema de la amistad. ^{[ 5 ]} Craig Huneke dio otra demostración . ^{[ 6 ]} Alexander van der Vekens informó en octubre de 2018 en la lista de correo de Metamath una demostración formalizada en Metamath . ^{[ 7 ]}

_{El grafo de} amistad tiene número cromático 3 e índice cromático 2n . Su polinomio cromático se puede deducir del polinomio cromático del grafo cíclico C3 y es igual a

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

El grafo de amistad F _n es elegante en sus aristas 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 crítico en cuanto a factores .

Según la teoría extremal de grafos , todo grafo con suficientes aristas (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${\displaystyle n}$-grafo de vértices (para${\displaystyle n}$suficientemente grande en términos de${\displaystyle k}$) si el número de aristas es

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

dónde${\displaystyle f(k)}$es${\displaystyle k^{2}-k}$si${\displaystyle k}$es extraño, y ${\displaystyle f(k)}$es${\displaystyle k^{2}-3k/2}$si${\displaystyle k}$es par. Estos límites generalizan el teorema de Turán sobre el número de aristas en un grafo libre de triángulos , y son los mejores límites posibles para este problema (cuando${\displaystyle n\geq 50k^{2}}$), en el sentido de que para cualquier número menor de aristas existen grafos que no contienen una${\displaystyle k}$-fan. ^{[ 10 ]}

Que dos vértices cualesquiera 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${\displaystyle P_{k}}$-grafos, en los que cualesquiera dos vértices están conectados por un único camino de longitud${\displaystyle k}$. Para${\displaystyle k\geq 3}$No se conocen tales gráficos, y la afirmación de su inexistencia es una conjetura de Kotzig .

• Digrafo central , un grafo dirigido con la propiedad de que cada par de vértices puede conectarse mediante un único camino de dos aristas.