Gráfico de molino de viento

En el campo matemático de la teoría de grafos , el grafo de molino de viento $Wd(k, n)$ es un grafo no dirigido construido para $k \geq 2$ y $n \geq 2$ uniendo $n$ copias del grafo completo $K k$ en un vértice universal compartido . Es decir, es una suma de 1-clique de estos grafos completos. ^[1]

Propiedades

Tiene $n (k - 1) + 1$ vértices y $nk (k - 1)/2$ aristas, ^[2] circunferencia 3 (si $k > 2$ ), radio 1 y diámetro 2. Tiene conectividad de vértices 1 porque su vértice central es un punto de articulación; sin embargo, al igual que los grafos completos a partir de los cuales se forma, es $(k - 1)$ -aristas conexas. Es trivialmente perfecto y un grafo de bloques .

Casos especiales

Por construcción, el gráfico de molino de viento $Wd(3, n)$ es el gráfico de amistad $F n$ , el gráfico de molino de viento $Wd(2, n)$ es el gráfico de estrella $S n$ y el gráfico de molino de viento $Wd(3,2)$ es el gráfico de mariposa .

Etiquetado y coloración

El grafo del molino de viento tiene número cromático $k$ e índice cromático $n (k - 1)$ . Su polinomio cromático se puede deducir del polinomio cromático del grafo completo y es igual a

x\prod_{i=1}^{k-1}(xi)^{n}.

Se ha demostrado que el grafo de molino de viento $Wd(k, n)$ no es elegante si $k > 5$ . ^[3] En 1979, Bermond ha conjeturado que $Wd(4, n)$ es elegante para todo $n \geq 4$ . ^[4] Mediante una equivalencia con familias de diferencias perfectas, esto se ha demostrado para $n \leq 1000$ . ^[5] Bermond, Kotzig y Turgeon demostraron que $Wd(k, n)$ no es elegante cuando $k = 4$ y $n = 2$ o $n = 3$ , y cuando $k = 5$ y $n = 2$ . ^[6] El molino de viento $Wd(3, n)$ es elegante si y solo si $n \equiv 0 (mod 4)$ o $n \equiv 1 (mod 4)$ . ^[7]

Galería

Referencias

^ Gallian, JA (3 de enero de 2007). "Un estudio dinámico del etiquetado de grafos" (PDF) . Revista electrónica de combinatoria . DS6 : 1–58. MR 1668059.
^ Weisstein, Eric W. "Gráfico del molino de viento". MundoMatemático .
^ Koh, KM; Rogers, DG; Teo, HK; Yap, KY (1980). "Gráficos elegantes: algunos resultados y problemas adicionales". Congressus Numerantium . 29 : 559–571. MR 0608456.
^ Bermond, J.-C. (1979). "Grafos elegantes, antenas de radio y molinos de viento franceses". En Wilson, Robin J. (ed.). Teoría de grafos y combinatoria (Proc. Conf., Open Univ., Milton Keynes, 1978) . Notas de investigación en matemáticas. Vol. 34. Pitman. págs. 18–37. ISBN 978-0273084358. Sr. 0587620. OCLC 757210583.
^ Ge, G.; Miao, Y.; Sun, X. (2010). "Familias de diferencias perfectas, matrices de diferencias perfectas y estructuras combinatorias relacionadas". Revista de diseños combinatorios . 18 (6): 415–449. doi :10.1002/jcd.20259. MR 2743134. S2CID 120800012.
^ Bermond, J.-C.; Kotzig, A .; Turgeon, J. (1978). "Sobre un problema combinatorio de antenas en radioastronomía". En Hajnal, A.; Sos, Vera T. (eds.). Combinatoria (Proc. Quinto coloquio húngaro, Keszthely, 1976), vol. I . Colloquia mathematica Societatis János Bolyai. vol. 18. Holanda Septentrional. págs. 135-149. ISBN 978-0-444-85095-9.Sr. 0519261 .
^ Bermond, J.-C.; Brouwer, AE ; Germa, A. (1978). "Sistemas de tripletes y diferencias asociadas". Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) . Coloques internacionales del Centro Nacional de la Investigación Científica. vol. 260. Éditions du Centre national de la recherche scientifique. págs. 35–38. ISBN 978-2-222-02070-7.Sr. 0539936 .