Hispanopedia WikiEn el campo matemático de la teoría de grafos , el grafo de escalera L n es un grafo plano , no dirigido, con 2 n vértices y 3 n – 2 aristas. [1]
El gráfico de escalera se puede obtener como el producto cartesiano de dos gráficos de trayectoria , uno de los cuales tiene solo una arista: L n ,1 = P n × P 2 . [2] [3]
Propiedades
Por construcción, el grafo en escalera L n es isomorfo al grafo en cuadrícula G 2, n y parece una escalera con n peldaños. Es hamiltoniano con circunferencia 4 (si n > 1 ) e índice cromático 3 (si n > 2 ).
El número cromático del gráfico de escalera es 2 y su polinomio cromático es .
-
El número cromático del gráfico de escalera es 2.
Gráfico de peldaños de escalera
A veces se utiliza el término "gráfico de escalera" para el gráfico de escalera de n × P 2 , que es la unión gráfica de n copias del gráfico de ruta P 2 .
Gráfica de escalera circular
El grafo circular en escalera CL n se puede construir conectando los cuatro vértices de 2 grados de forma recta , o mediante el producto cartesiano de un ciclo de longitud n ≥ 3 y una arista. [4] En símbolos, CL n = C n × P 2 . Tiene 2 n nodos y 3 n aristas. Al igual que el grafo en escalera, es conexo , planar y hamiltoniano , pero es bipartito si y solo si n es par.
Los gráficos de escalera circular son los gráficos poliédricos de prismas, por lo que se les llama más comúnmente gráficos prismáticos .
Gráficas de escalera circular:
Escalera de Möbius
Conectando los cuatro vértices de 2 grados en forma transversal se crea un gráfico cúbico llamado escalera de Möbius.
Referencias
- ^ Weisstein, Eric W. "Gráfico de escalera". MundoMatemático .
- ^ Hosoya, H. y Harary, F. "Sobre las propiedades de correspondencia de tres gráficos de valla". J. Math. Chem. 12, 211-218, 1993.
- ^ Noy, M. y Ribó, A. "Familias de grafos construibles recursivamente". Adv. Appl. Math. 32, 350-363, 2004.
- ^ Chen, Yichao; Gross, Jonathan L.; Mansour, Toufik (septiembre de 2013). "Distribuciones de incrustación total de escaleras circulares". Revista de teoría de grafos . 74 (1): 32–57. CiteSeerX 10.1.1.297.2183 . doi :10.1002/jgt.21690. S2CID 6352288.
