Hispanopedia Wiki
Articulo de referencia

Gráfico de Meredith

En el campo matemático de la teoría de grafos , el grafo de Meredith es un grafo no dirigido 4- regular con 70 vértices y 140 aristas descubierto por Guy HJ Meredith en 1973. [ ...

Hispanopedia WikiContenido en espanolLectura gratuita

En el campo matemático de la teoría de grafos , el grafo de Meredith es un grafo no dirigido 4- regular con 70 vértices y 140 aristas descubierto por Guy HJ Meredith en 1973. [ 1 ]

El grafo de Meredith es 4- conexo por vértices y 4- conexo por aristas , tiene número cromático 3, índice cromático 5, radio 7, diámetro 8, circunferencia 4 y no es hamiltoniano . [ 2 ] Tiene grosor de libro 3 y número de cola 2. [ 3 ]

Publicado en 1973, proporciona un contraejemplo a la conjetura de Crispin Nash-Williams de que todo grafo 4-regular con 4 vértices conexos es hamiltoniano. [ 4 ] [ 5 ] Sin embargo, WT Tutte demostró que todos los grafos planares 4-conexos son hamiltonianos. [ 6 ]

El polinomio característico del grafo de Meredith es(incógnita−4)(incógnita−1)10incógnita21(incógnita+1)11(incógnita+3)(incógnita2−13)(incógnita6−26incógnita4+3incógnita3+169incógnita2−39incógnita−45)4{\displaystyle (x-4)(x-1)^{10}x^{21}(x+1)^{11}(x+3)(x^{2}-13)(x^{6}-26x^{4}+3x^{3}+169x^{2}-39x-45)^{4}}.

Referencias

  1. ↑ Weisstein, Eric W. "Grafo de Meredith" . MathWorld .
  2. ↑ Bondy, JA y Murty, USR "Teoría de grafos". Springer, pág. 470, 2007.
  3. ↑ Jessica Wolz, Diseño de distribuciones lineales mediante SAT . Tesis de maestría, Universidad de Tubinga, 2018.
  4. ↑ Meredith, GHJ (1973). "Grafos regulares n -valentes n- conectados no hamiltonianos no n -coloreables por aristas" . Journal of Combinatorial Theory, Serie B. 14 : 55–60 . doi : 10.1016 /s0095-8956(73)80006-1 . MR 0311503 . 
  5. ↑ Bondy, JA y Murty, USR "Teoría de grafos con aplicaciones". Nueva York: North Holland, pág. 239, 1976.
  6. ↑ Tutte, WT, ed., Avances recientes en combinatoria. Academic Press, Nueva York, 1969.
Lecturas relacionadas
6 articulos
MatemáticasMatemáticasLas matemáticas son un campo de estudio que descubre y organiza métodos, teorías y teoremas que se desarrollan y prueban para las necesidades de la...Teoría de grafosTeoría de grafosEn matemáticas , la teoría de grafos es el estudio de los grafos , que son estructuras matemáticas utilizadas para modelar relaciones por pares ent...Gráfica (matemática discreta)Gráfica (matemática discreta)En matemáticas discretas , particularmente en teoría de grafos , un grafo es una estructura que consiste en un conjunto de objetos donde algunos pa...Gráfico regularGráfico regularEn teoría de grafos , un grafo regular es un grafo en el que cada vértice tiene el mismo número de vecinos; es decir, cada vértice tiene el mismo g...grafo conexo con k vérticesgrafo conexo con k vérticesEn teoría de grafos , se dice que un grafo conexo G es k -vértice-conexo (o k -conexo ) si tiene más de k vértices y permanece conectado siempre qu...gráfico con conexión de k aristasgráfico con conexión de k aristasEn teoría de grafos , un grafo conexo es k -conexo por aristas si permanece conectado siempre que se eliminen menos de k aristas.