En el campo matemático de la teoría de grafos , el grafo de escalera L n es un grafo plano no dirigido con 2n vértices y 3n-2 aristas. [1]
Gráfico de escalera | |
---|---|
Vértices | 2n |
Bordes | 3n-2 |
Número cromático | 2 |
Índice cromático | 3 para n> 2 2 para n = 2 1 para n = 1 |
Propiedades | Unidad de distancia Hamiltoniano Planar Bipartito |
Notación | L n |
Tabla de gráficos y parámetros |
El gráfico de escalera se puede obtener como el producto cartesiano de dos gráficos de trayectoria , uno de los cuales tiene solo un borde: L n , 1 = P n × P 2 . [2] [3]
Propiedades
Por construcción, el gráfico de escalera L n es isomorfo al gráfico de 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, el término "gráfico de escalera" se utiliza para el gráfico de escalón de escalera de n × P 2 , que es la unión gráfica de n copias del gráfico de trayectoria P 2 .
Gráfico de escalera circular
El gráfico de escalera circular 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 2n nodos y 3n bordes. Al igual que el gráfico de escalera, está conectado , es plano 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 los prismas, por lo que se denominan más comúnmente gráficos de prismas .
Gráficos de escalera circular:
CL3 | CL4 | CL5 | CL6 | CL7 | CL8 |
Escalera de moebius
Al conectar 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" . MathWorld .
- ^ Hosoya, H. y Harary, F. "Sobre las propiedades coincidentes de tres gráficos de valla". J. Math. Chem. 12, 211-218, 1993.
- ^ Noy, M. y Ribó, A. "Familias de gráficos recursivamente construibles". Adv. Apl. Matemáticas. 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 .