Sobre Grafos Unicíclicos Críticos con Ancho de Corte Cuatro
Autores: Zhang, Zhenkun; Lai, Hongjian
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
Categoría
Matemáticas
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 10
Citaciones: Sin citaciones
El problema de minimización del ancho de corte consiste en encontrar una disposición de los vértices de un grafo en una línea de tal manera que se minimice el número máximo de aristas superpuestas (es decir, la congestión). Un grafo con un ancho de corte de k es crítico en k-ancho de corte si cada subgrafo propio de G tiene un ancho de corte menor que k y es homeomórficamente mínimo. En este artículo, primero verificamos algunas propiedades estructurales de los grafos unicíclicos críticos en k-ancho de corte con k = 3. Luego, investigamos principalmente el conjunto de grafos unicíclicos críticos con un ancho de corte de cuatro que contiene cincuenta elementos, y obtuvimos una caracterización de subgrafos prohibidos de los grafos unicíclicos en 3-ancho de corte.
Descripción
El problema de minimización del ancho de corte consiste en encontrar una disposición de los vértices de un grafo en una línea de tal manera que se minimice el número máximo de aristas superpuestas (es decir, la congestión). Un grafo con un ancho de corte de k es crítico en k-ancho de corte si cada subgrafo propio de G tiene un ancho de corte menor que k y es homeomórficamente mínimo. En este artículo, primero verificamos algunas propiedades estructurales de los grafos unicíclicos críticos en k-ancho de corte con k = 3. Luego, investigamos principalmente el conjunto de grafos unicíclicos críticos con un ancho de corte de cuatro que contiene cincuenta elementos, y obtuvimos una caracterización de subgrafos prohibidos de los grafos unicíclicos en 3-ancho de corte.