En el campo matemático de la teoría de grafos , el grafo de Frucht es un grafo regular 3 con 12 vértices, 18 aristas y sin simetrías no triviales . [1] Fue descrito por primera vez por Robert Frucht en 1939. [2]
Gráfico de Frucht | |
---|---|
Lleva el nombre de | Robert Frucht |
Vértices | 12 |
Bordes | 18 |
Radio | 3 |
Diámetro | 4 |
Circunferencia | 3 |
Automorfismos | 1 ({ id }) |
Número cromático | 3 |
Índice cromático | 3 |
Propiedades | Cúbico Halin Pancyclic |
Tabla de gráficos y parámetros |
El gráfico de Frucht es un gráfico de Halin pancíclico con número cromático 3, índice cromático 3, radio 3 y diámetro 4. Al igual que con todos los gráficos de Halin, el gráfico de Frucht es poliédrico ( plano y conectado a 3 vértices ) y hamiltoniano , con circunferencia 3 Su número de independencia es el 5.
El gráfico de Frucht se puede construir a partir de la notación LCF : [−5, −2, −4,2,5, −2,2,5, −2, −5,4,2].
Propiedades algebraicas
El gráfico de Frucht es uno de los cinco gráficos cúbicos más pequeños que posee un solo automorfismo gráfico , la identidad [3] (es decir, cada vértice se puede distinguir topológicamente de cualquier otro vértice). Estos gráficos se denominan gráficos asimétricos (o de identidad). El teorema de Frucht establece que cualquier grupo puede realizarse como el grupo de simetrías de un gráfico, [2] y un fortalecimiento de este teorema también debido a que Frucht establece que cualquier grupo puede realizarse como las simetrías de un gráfico 3-regular; [4] el gráfico de Frucht proporciona un ejemplo de esta realización para el grupo trivial .
El polinomio característico del gráfico de Frucht es.
Galería
El número cromático del gráfico Frucht es 3.
El gráfico de Frucht es hamiltoniano .
Ver también
Referencias
- ^ Weisstein, Eric W. "Gráfico de Frucht" . MathWorld .
- ^ a b Frucht, R. (1939), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe". , Compositio Mathematica (en alemán), 6 : 239–250, ISSN 0010-437X , Zbl 0020.07804.
- ^ Bussemaker, FC; Cobeljic, S .; Cvetkovic, DM; Seidel, JJ (1976), Investigación informática de gráficos cúbicos , informe EUT, 76-WSK-01, Departamento de Matemáticas y Ciencias de la Computación, Universidad Tecnológica de Eindhoven
- ^ Frucht, R. (1949), "Gráficos de grado tres con un grupo de resumen dado", Canadian Journal of Mathematics , 1 : 365–378, doi : 10.4153 / CJM-1949-033-6 , ISSN 0008-414X , MR 0032987.