Gráfico de molino de viento

En el campo matemático de la teoría de grafos , el gráfico de molino de viento $Wd(k, n)$ es un gráfico no dirigido construido para $k \geq 2$ y $n \geq 2$ uniendo $n$ copias del gráfico completo $K k$ en un vértice universal compartido . Es decir, es una suma de 1 clique de estos gráficos 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értice 1 porque su vértice central es un punto de articulación; sin embargo, al igual que los gráficos completos a partir de los cuales se forma, está $(k - 1)$ -conectado por bordes. Es trivialmente perfecto y un gráfico 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 .

Etiquetar y colorear

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

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

Se ha demostrado que el gráfico del molino de viento $Wd(k, n)$ no es elegante si $k > 5$ . ^[3] En 1979, Bermond conjeturó 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 grácil si y sólo 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 gráficos" (PDF) . Revista Electrónica de Combinatoria . DS6 : 1–58. SEÑOR 1668059.
^ Weisstein, Eric W. "Gráfico del molino de viento". MundoMatemático .
^ Koh, KM; Rogers, director general; Teo, HK; Sí, KY (1980). "Gráficos elegantes: algunos resultados y problemas adicionales". Congreso Numerantium . 29 : 559–571. SEÑOR 0608456.
^ Bermond, J.-C. (1979). "Gráficos 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) . Apuntes de investigación en matemáticas. vol. 34. Pitman. págs. 18–37. ISBN 978-0273084358. SEÑOR 0587620. OCLC 757210583.
^ Ge, G.; Miao, Y.; Sol, 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. SEÑOR 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. SEÑOR 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. SEÑOR 0539936.