Gráfico de amistad
| Gráfico de amistad | |
|---|---|
| picos | 2n+1 |
| costillas | 3n |
| Radio | una |
| Diámetro | 2 |
| Circunferencia | 3 |
| Número cromático | 3 |
| índice cromático | 2n |
| Propiedades |
Gráfico de distancia unitaria factor de euler plano crítico |
| Designacion | f norte |
| Archivos multimedia en Wikimedia Commons | |
Gráfico de amistad (o gráfico de molino danés , o abanico de n aspas ) Fn es un gráfico plano no dirigido con 2n+1 vértices y 3n aristas [1] .
El grafo de amistad F n se puede construir conectando n copias del ciclo C 3 en un vértice común [2] .
Por construcción, el grafo de amistad F n es isomorfo al molino de viento Wd(3, n ). El gráfico es un gráfico de unidad de distancia y tiene una circunferencia de 3, un diámetro de 2 y un radio de 1. El gráfico F 2 es isomorfo a una mariposa .
Teorema del gráfico de amistad
El teorema del gráfico de amistad de Erdős, Rényi y Vera Sos [3] [4] establece que los gráficos finitos con la propiedad de que dos vértices cualesquiera tienen exactamente un vecino común son exactamente gráficos de amistad. De manera informal, si un grupo de personas tiene la propiedad de que cualquier par de personas tiene exactamente un amigo en común, entonces debe haber una persona que sea amiga de los otros miembros del grupo. Sin embargo, para gráficos infinitos, puede haber muchos gráficos diferentes de la misma cardinalidad que tengan esta propiedad [5] .
Mertzios y Unger [6] dieron una demostración combinatoria del teorema del grafo de la amistad . Otra prueba fue dada por Craig Huneke [7] .
Marcado y coloreado
El gráfico de la amistad tiene el número cromático 3 y el índice cromático 2n . Su polinomio cromático se puede obtener del polinomio cromático del ciclo C 3 y es igual a .
El grafo de amistad F n tiene etiquetado de borde perfecto si y solo si n es impar. Tiene un etiquetado elegante si y solo si n ≡ 0 (mod 4) o n ≡ 1 (mod 4) [8] [9] .
Cualquier gráfico de amistad es un factor crítico .
Teoría de grafos extremos
De acuerdo con la teoría de grafos extremos, cualquier gráfico con un número suficientemente grande de aristas (en relación con el número de vértices) debe contener un abanico de k palas como subgrafo. Más precisamente, esto es cierto para un gráfico con n vértices si el número de aristas es
donde f ( k ) es igual a k 2 − k si k es impar y f ( k ) es igual a k 2 − 3 k /2 si k es par. Estos límites generalizan el teorema de Turan sobre el número de aristas en un grafo sin triángulos, y son los mejores límites para este problema, ya que para cualquier número menor de aristas hay gráficos que no contienen un abanico de álabes k [10] .
Notas
- ↑ Weisstein, Eric W. Dutch Windmill Graph en el sitio web de Wolfram MathWorld .
- ↑ Gallian, 2007 , pág. 1-58.
- ↑ Erdős, Rényi, Sos, 1966 .
- ↑ Erdős, Rényi, Sós, 1966 , p. 215–235.
- ↑ Chvátal, Kotzig, Rosenberg, Davies, 1976 , p. 431–433.
- ↑ Mertzios, Unger, 2008 .
- ↑ Huneke, 2002 , pág. 192–194.
- ↑ Bermond, Brouwer, Germa, 1978 , p. 35-38.
- ↑ Bermond, Kotzig, Turgeon, 1978 , p. 135-149.
- ↑ Erdős, Furedi, Gould, Gunderson, 1995 , p. 89–100.
Literatura
- JA Gallian. Encuesta Dinámica DS6: Etiquetado de Gráficos // Electronic J. Combinatorics. - 2007. - Enero. Archivado desde el original el 31 de enero de 2012.
- J. C. Bermond, A. E. Brouwer, A. Germa. Systèmes de triplets et différences associées // Problèmes Combinatoires et Théorie des Graphes. - París, 1978. - Vol. 260, Editions du Centre Nationale de la Recherche Scientifique. - (Coloq. Intern. du CNRS).
- JC Bermond, A. Kotzig, J. Turgeon. Sobre un problema combinatorio de antenas en radioastronomía, en Combinatorics // Colloq. Matemáticas. soc. János Bolyai, / A. Hajnal, VT Sos, eds.. - Holanda Septentrional, Ámsterdam, 1978. - T. 18, 2 vols..
- Paul Erdős , Alfred Rényi , Vera T. Sos. Sobre un problema de teoría de grafos // Studia Sci. Matemáticas. Hungría.. - 1966. - T. 1 . — S. 215–235 .
- Václav Chvátal, Anton Kotzig, Ivo G. Rosenberg, Roy O. Davies. Hay gráficos de amistad del cardenal // Canadian Mathematical Bulletin. - 1976. - T. 19 , núm. 4 . — S. 431–433 . -doi : 10.4153 / cmb-1976-064-1 .
- George Mertzio, Walter Unger. El problema de la amistad en grafos // Relaciones, Órdenes y Grafos: Interacción con la Informática. — 2008.
- Craig Huneke. El teorema de la amistad // The American Mathematical Monthly. - 2002. - enero ( vol. 109 , número 2 ). — S. 192–194 . -doi : 10.2307/ 2695332 . — .
- Paul Erdős , Z. Furedi, RJ Gould, DS Gunderson. Gráficos extremos para triángulos que se intersecan // Journal of Combinatorial Theory. - 1995. - T. 64 , núm. 1 . — S. 89–100 . -doi : 10.1006/ jctb.1995.1026.
