Hispanopedia WikiEn teoría de grafos , el grafo de Frucht es un grafo cúbico con 12 vértices , 18 aristas y sin simetrías no triviales . [ 1 ] Fue descrito por primera vez por Robert Frucht en 1949. [ 2 ]
El grafo de Frucht se puede construir a partir de la notación LCF : [−5,−2,−4,2,5,−2,2,5,−2,−5,4,2] . Esto lo describe como un grafo cúbico en el que dos de las tres adyacencias de cada vértice forman parte de un ciclo hamiltoniano y los números especifican qué tan lejos en el ciclo se debe encontrar el tercer vecino de cada vértice. [ 3 ]
Propiedades
El grafo de Frucht es un grafo cúbico , porque tres vértices son incidentes a cada vértice, por lo que el grado de cada vértice es 3. Es uno de los cinco grafos cúbicos más pequeños que poseen un único automorfismo de grafo , la identidad: cada vértice puede distinguirse topológicamente de cualquier otro vértice. [ 4 ] Dichos grafos se denominan grafos asimétricos (o identidad). El teorema de Frucht establece que cualquier grupo finito puede realizarse como el grupo de simetrías de un grafo, [ 5 ] y un fortalecimiento de este teorema, también debido a Frucht, establece que cualquier grupo finito puede realizarse como las simetrías de un grafo 3-regular . [ 2 ] El grafo de Frucht proporciona un ejemplo de esta realización fortalecida para el grupo trivial .
El grafo de Frucht es un grafo de Halin , un tipo de grafo planar formado a partir de un árbol sin vértices de grado dos mediante la adición de un ciclo que conecta sus hojas. [ 1 ] Todo grafo de Halin es 3-conexo por vértices : la eliminación de dos de sus vértices no puede desconectarlo. Por el teorema de Steinitz , el grafo de Frucht es, por lo tanto, poliédrico , lo que significa que sus 12 vértices y 18 aristas forman el esqueleto de un poliedro convexo. [ 6 ] También es hamiltoniano .
Es pancíclico , [ 7 ] con número cromático 3, índice cromático 3, radio 3 y diámetro 4. Su circunferencia es 3. Su número de independencia es 5.
El polinomio característico del grafo de Frucht es.
Galería
El número cromático del gráfico de Frucht es 3.
El grafo de Frucht es hamiltoniano .
Referencias
- ^ Ali , Akbar; Chartrand, Gary; Zhang, Ping (2021), Irregularidad en gráficos , Springer, págs. 24-25 , doi : 10.1007/978-3-030-67993-4 , ISBN 978-3-030-67993-4
- 1 2 Frucht, R. (1949), "Grafos de grado tres con un grupo abstracto dado", Canadian Journal of Mathematics , 1 (4): 365– 378, doi : 10.4153/CJM-1949-033-6 , ISSN 0008-414X , MR 0032987 , S2CID 124723321
- ^ Weisstein, Eric W. , "Gráfico de Frucht" , MathWorld
{{cite web}}: Mantenimiento de CS1: configuración sobrescrita ( enlace ) - ↑ Bussemaker, FC; Cobeljic, S.; Cvetkovic, DM; Seidel, JJ (1976), Investigación computacional de grafos cúbicos , Informe EUT, vol. 76-WSK-01, Departamento de Matemáticas e Informática, Universidad Tecnológica de Eindhoven
- ^ Frucht, R. (1939), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe". , Compositio Mathematica (en alemán), 6 : 239–250 , ISSN 0010-437X , Zbl 0020.07804
- ^ Weisstein, Eric W. , "Halin Graph" , MathWorld
- ↑ Parrochia, Daniel (2023), Matemáticas y filosofía 2: Grafos, órdenes, infinitos y filosofía , John & Wiley , ISTE Ltd., pág. 18, ISBN 978-1-78630-897-9
Lecturas adicionales
- Sudev, NK; Germina, KA (2014), "Una nota sobre el número de grafos superfluos", Advances and Applications in Discrete Mathematics , 14 (1): 51– 65, arXiv : 1402.4871
- Fullarton, Neil J. (2016), "Sobre el número de automorfismos externos del grupo de automorfismos de un grupo de Artin de ángulo recto", Mathematical Research Letters , 23 (1): 145–162 , arXiv : 1306.6549 , doi : 10.4310/MRL.2016.v23.n1.a8 , MR 3512881
- Gráficos individuales
- Gráficos regulares
- Grafos planares