Caracterización de todos los gráficos con un número de forzamiento de cero sesgado fallido de 1
Autores: Johnson, Aidan; Vick, Andrew E.; Narayan, Darren A.
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Caracterización de todos los gráficos con un número de forzamiento de cero sesgado fallido de 1
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Número de forzamiento cero
Vértices
Regla de forzamiento
Número de forzamiento cero fallido
Forzamiento cero sesgado.
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 68
Citaciones: Sin citaciones
Dado un grafo G, el número de forzamiento cero de G es la cardinalidad mínima de cualquier conjunto de vértices de los cuales aplicaciones repetidas de la regla de forzamiento resultan en todos los vértices estando en G. La regla de forzamiento es: si un vértice está en G, y exactamente un vecino de G no está en G, entonces se agrega a G en la siguiente iteración. Por lo tanto, el número de forzamiento cero fallido de un grafo se define como la cardinalidad del conjunto más grande de vértices que no logra forzar a todos los vértices en el grafo. Se definió una propiedad similar llamada forzamiento cero sesgado de manera que si exactamente un vecino de G no está en G, entonces se agrega a G en la siguiente iteración. La diferencia es que los vértices que no están en G pueden forzar a otros vértices. Esto lleva al número de forzamiento cero sesgado fallido de un grafo, que se denota como . En este documento, proporcionamos una caracterización completa de todos los grafos con . Fetcie, Jacob y Saavedra demostraron que los únicos grafos con un número de forzamiento cero fallido de 1 son: la unión de dos vértices aislados; ; ; o . En este documento, proporcionamos un resultado sorprendente: cambiar la regla de forzamiento a una regla de forzamiento sesgado resulta en un número infinito de grafos con .
Descripción
Dado un grafo G, el número de forzamiento cero de G es la cardinalidad mínima de cualquier conjunto de vértices de los cuales aplicaciones repetidas de la regla de forzamiento resultan en todos los vértices estando en G. La regla de forzamiento es: si un vértice está en G, y exactamente un vecino de G no está en G, entonces se agrega a G en la siguiente iteración. Por lo tanto, el número de forzamiento cero fallido de un grafo se define como la cardinalidad del conjunto más grande de vértices que no logra forzar a todos los vértices en el grafo. Se definió una propiedad similar llamada forzamiento cero sesgado de manera que si exactamente un vecino de G no está en G, entonces se agrega a G en la siguiente iteración. La diferencia es que los vértices que no están en G pueden forzar a otros vértices. Esto lleva al número de forzamiento cero sesgado fallido de un grafo, que se denota como . En este documento, proporcionamos una caracterización completa de todos los grafos con . Fetcie, Jacob y Saavedra demostraron que los únicos grafos con un número de forzamiento cero fallido de 1 son: la unión de dos vértices aislados; ; ; o . En este documento, proporcionamos un resultado sorprendente: cambiar la regla de forzamiento a una regla de forzamiento sesgado resulta en un número infinito de grafos con .