En teoría de grafos, un grafo rueda (Wn), o simplemente rueda, es un grafo con nvértices que se forma conectando un único vértice a todos los vértices de un ciclo-(n-1).
Los grafos rueda son grafos planos, y como tales pueden ser "incrustado" en un plano. Más específicamente, todo gráfico rueda es un grafo de Halin. Son auto-duales: el dual de cualquier grafo rueda es un grafo isomórfico.
En un grafo rueda siempre hay un ciclo hamiltoniano, habiendo n2-3n+3 ciclos en Wn (sucesión A002061 en OEIS).
Los 7 ciclos de un grafo rueda W4.
Para valores impares de n, Wn es un grafo perfecto con número cromático 3: Los vértices del ciclo pueden proporcionar dos colores, y el vértice centro proporciona un tercer color. Para valores pares de n, Wn tiene número cromático 4, y (cuando n ≥ 6) no es perfecto. W7 es el único grafo rueda que es un grafo de distancia unidad en el plano euclidiano.[1]
El polinomio cromático de un grafo rueda Wn es :
Referencias
Buckley, Fred; Harary, Frank (1988), «On the euclidean dimension of a wheel», Graphs and Combinatorics4 (1): 23-30, doi:10.1007/BF01864150..
Enlaces externos
Grafos. Nociones básicas - Teoría de Redes. Universidad de Antioquia.
Datos:Q948887
Multimedia:Wheel graphs
Agosto 16, 2021
grafo, rueda, teoría, grafos, grafo, rueda, simplemente, rueda, grafo, vértices, forma, conectando, único, vértice, todos, vértices, ciclo, algunos, ejemplos, grafos, ruedavérticesnaristas2, diámetro2, 4cintura3número, cromático3, impar4, parpropiedadeshamilto. En teoria de grafos un grafo rueda Wn o simplemente rueda es un grafo con n vertices que se forma conectando un unico vertice a todos los vertices de un ciclo n 1 Grafo ruedaAlgunos ejemplos de grafos ruedaVerticesnAristas2 n 1 Diametro2 si n gt 41 si n 4Cintura3Numero cromatico3 si n es impar4 si n es parPropiedadesHamiltoniano Auto dual Planar editar datos en Wikidata Los grafos rueda son grafos planos y como tales pueden ser incrustado en un plano Mas especificamente todo grafico rueda es un grafo de Halin Son auto duales el dual de cualquier grafo rueda es un grafo isomorfico En un grafo rueda siempre hay un ciclo hamiltoniano habiendo n2 3n 3 ciclos en Wn sucesion A002061 en OEIS Los 7 ciclos de un grafo rueda W4 Para valores impares de n Wn es un grafo perfecto con numero cromatico 3 Los vertices del ciclo pueden proporcionar dos colores y el vertice centro proporciona un tercer color Para valores pares de n Wn tiene numero cromatico 4 y cuando n 6 no es perfecto W7 es el unico grafo rueda que es un grafo de distancia unidad en el plano euclidiano 1 El polinomio cromatico de un grafo rueda Wn es P W n x x x 2 n 1 n 1 x 2 displaystyle P W n x x x 2 n 1 n 1 x 2 Referencias Editar Buckley Fred Harary Frank 1988 On the euclidean dimension of a wheel Graphs and Combinatorics 4 1 23 30 doi 10 1007 BF01864150 Enlaces externos EditarGrafos Nociones basicas Teoria de Redes Universidad de Antioquia Datos Q948887 Multimedia Wheel graphsObtenido de https es wikipedia org w index php title Grafo rueda amp oldid 120689384, wikipedia, wiki, leyendo, leer, libro, biblioteca,
