Propiedades estructurales de grafos críticos de dominación conectada
Autores: Almalki, Norah; Kaemawichanurat, Pawaton
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Grafo
Crítico
Vértices de corte
Emparejamiento perfecto
Factor crítico
Bloque
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 43
Citaciones: Sin citaciones
Un grafo se dice crítico si el número de dominación conectada es igual a y para cualquier par de vértices no adyacentes y de . Sea el número de vértices de corte de y sea el número máximo de vértices de corte que puede contener un bloque. Para un entero , un grafo es -crítico si tiene un emparejamiento perfecto para cualquier subconjunto de vértices de tamaño . Fue demostrado por Ananchuen en 2007 para , Kaemawichanurat y Ananchuen en 2010 para y por Kaemawichanurat y Ananchuen en 2020 para que todo grafo crítico tenga a lo sumo vértices de corte y se caracterizaron los grafos con el número máximo de vértices de corte. En 2020, Kaemawichanurat y Ananchuen demostraron además que, para , todos los grafos críticos cumplen la desigualdad . En este artículo, caracterizamos todos los grafos críticos que tienen vértices de corte. Además, establecemos la realizabilidad de que, dados , y , existe un grafo crítico con vértices de corte que tiene un bloque que contiene vértices de corte. Finalmente, demostramos que todo grafo crítico de orden impar con grado mínimo dos es 1-crítico si y solo si . Además, demostramos que todo grafo -libre crítico de orden par con grado mínimo tres es 2-crítico si y solo si .
Descripción
Un grafo se dice crítico si el número de dominación conectada es igual a y para cualquier par de vértices no adyacentes y de . Sea el número de vértices de corte de y sea el número máximo de vértices de corte que puede contener un bloque. Para un entero , un grafo es -crítico si tiene un emparejamiento perfecto para cualquier subconjunto de vértices de tamaño . Fue demostrado por Ananchuen en 2007 para , Kaemawichanurat y Ananchuen en 2010 para y por Kaemawichanurat y Ananchuen en 2020 para que todo grafo crítico tenga a lo sumo vértices de corte y se caracterizaron los grafos con el número máximo de vértices de corte. En 2020, Kaemawichanurat y Ananchuen demostraron además que, para , todos los grafos críticos cumplen la desigualdad . En este artículo, caracterizamos todos los grafos críticos que tienen vértices de corte. Además, establecemos la realizabilidad de que, dados , y , existe un grafo crítico con vértices de corte que tiene un bloque que contiene vértices de corte. Finalmente, demostramos que todo grafo crítico de orden impar con grado mínimo dos es 1-crítico si y solo si . Además, demostramos que todo grafo -libre crítico de orden par con grado mínimo tres es 2-crítico si y solo si .