Grafo de la amistad

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Grafo de la amistad Fn
Friendship graph 8.svg
Grafo de la amistad F8
Vértices 2n+1
Aristas 3n
Radio 1
Diámetro 2
Cintura (girth) 3
Número cromático 3
Índice cromático 2n
Propiedades
[editar datos en Wikidata ]
Grafos de la amistad F2, F3 y F4.

En el campo matemático de la teoría de grafos, el grafo de la amistad Fn también llamado grafo molino de viento holandés, grafo ventilador o grafo n-fan es un grafo plano con 2n+1 vértices y 3n aristas.[1]

El grafo de la amistad Fn puede ser formado construyendo n copias del ciclo C3 con un vértice común.[2] Por construcción, el grafo de la amistad Fn es isomorfo al grafo molino de viento Wd(3,n). Y el grafo F2 es isomorfo al grafo mariposa

Teorema de la amistad[editar]

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

Coloración[editar]

El grafo de la amistad tiene número cromático 3 e índice cromático 2n. Su polinomio cromático puede ser deducido del polinomio cromático del ciclo C3 y es igual a (x-2)^n (x-1)^n x.

Teoría de grafos extrema[editar]

De acuerdo con la teoría de grafos extrema, cada grafo con un número suficientemente grande de aristas en comparación con el número de vértices, debe contener un grafo k-fan. Más específicamente, esto es cierto para un grafo de orden n si el número de aristas es

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

donde f(k) es k2 − k si k es impar, y f(k) es k2 − 3k/2 si k es par.

Referencias[editar]

  1. Weisstein, Eric W. «Dutch Windmill Graph» (en inglés). MathWorld. Wolfram Research.
  2. Gallian, J. A. "Dynamic Survey DS6: Graph Labeling." Electronic J. Combinatorics, DS6, 1-58, Jan. 3, 2007. [1].
  3. Erdős, Paul; Rényi, Alfréd; Sós, Vera T. (1966), «On a problem of graph theory», Studia Sci. Math. Hungar. 1: 215–235, http://www.renyi.hu/~p_erdos/1966-06.pdf .
  4. Chvátal, Václav; Kotzig, Anton; Rosenberg, Ivo G.; Davies, Roy O. (1976), «There are \scriptstyle 2^{\aleph_\alpha} friendship graphs of cardinal \scriptstyle\aleph_\alpha», Canadian Mathematical Bulletin 19 (4): 431–433 .