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 ≥ 2 yn ≥ 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 gráficos completos. [1]
Gráfico de molino de viento | |
---|---|
Vértices | (k-1) n + 1 |
Bordes | nk (k − 1) / 2 |
Radio | 1 |
Diámetro | 2 |
Circunferencia | 3 si k> 2 |
Número cromático | k |
Índice cromático | n (k-1) |
Notación | Wd ( k , n ) |
Tabla de gráficos y parámetros |
Propiedades
Tiene (k-1) n + 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á conectado por bordes (k-1) . 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 .
Etiquetado y coloración
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
Se demuestra 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 ≥ 4. [4] A través de una equivalencia con perfecto familias de diferencias, esto se ha demostrado para n ≤ 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 m = 2. [6] El molino de viento Wd (3, n ) es agraciado si y sólo si n ≡ 0 (mod 4) o n ≡ 1 (mod 4). [7]
Galería
Referencias
- ^ Gallian, JA (3 de enero de 2007). "Un estudio dinámico de etiquetado de gráficos" (PDF) . Revista electrónica de combinatoria . DS6 : 1-58. Señor 1668059 .
- ^ Weisstein, Eric W. "Gráfico de molino de viento" . MathWorld .
- ^ Koh, KM; Rogers, DG; Teo, HK; Yap, KY (1980). "Gráficos agraciados: algunos resultados y problemas adicionales". Congressus Numerantium . 29 : 559–571. Señor 0608456 .
- ^ Bermond, J.-C. (1979). "Gráficos agraciados, 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. 34 . Minero. 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 .
- ^ 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. Yo . Coloquia matemática Societatis János Bolyai. 18 . Holanda Septentrional. págs. 135-149. ISBN 978-0-444-85095-9. Señor 0519261 .
- ^ Bermond, J.-C .; Brouwer, AE ; Germa, A. (1978). "Systèmes de triplets et différences associées" . Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976) . Colloques internationaux du Centre National de la Recherche Scientifique. 260 . Éditions du Centre national de la recherche scientifique. págs. 35–38. ISBN 978-2-222-02070-7. Señor 0539936 .