logo móvil
Contáctanos

El gráfico de resolución fuerte simultánea y la dimensión métrica fuerte simultánea de familias de gráficos

Autores: González Yero, Ismael

Idioma: Inglés

Editor: MDPI

Año: 2020

Descargar PDF

Acceso abierto

Artículo científico
2020

El gráfico de resolución fuerte simultánea y la dimensión métrica fuerte simultánea de familias de gráficos


Categoría

Matemáticas

Subcategoría

Matemáticas generales

Palabras clave

Enfoque
Estudio
Familias de grafos
Dimensión métrica fuerte
Grafo de resolución fuerte
Simultáneo

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 36

Citaciones: Sin citaciones


Descripción
Consideramos en este trabajo un nuevo enfoque para estudiar la dimensión métrica fuerte simultánea de familias de grafos, al mismo tiempo que introducimos la versión simultánea del grafo resolvente fuerte. En concordancia, consideramos aquí grafos conectados cuyos conjuntos de vértices están representados como , y la siguiente terminología. Dos vértices son resueltos fuertemente por un vértice , si hay un camino más corto que contiene o un camino más corto que contiene . Un conjunto de vértices del grafo se dice que es un generador métrico fuerte para si cada par de vértices de son resueltos fuertemente por algún vértice de . La cardinalidad posible más pequeña de cualquier generador métrico fuerte (SSMG) para el grafo se toma como la dimensión métrica fuerte del grafo . Dada una familia de grafos definida sobre un conjunto de vértices común , un conjunto es un SSMG para , si dicho conjunto es un generador métrico fuerte para cada grafo . La dimensión métrica fuerte simultánea de es la cardinalidad mínima de cualquier generador métrico fuerte para , y se denota por . La noción de grafo resolvente fuerte simultáneo de una familia de grafos se introduce en este trabajo, y se describe su utilidad en el estudio de . Es decir, se demuestra que calcular es equivalente a calcular el número de cubierta de vértices del grafo resolvente fuerte simultáneo de . Luego se deducen varias consecuencias (computacionales y combinatorias) de dicha relación. Entre ellas, destacamos por ejemplo que hemos demostrado la NP-dificultad de calcular la dimensión métrica fuerte simultánea de familias de caminos, lo cual es una mejora (con respecto a la creciente dificultad del problema) sobre los resultados conocidos en la literatura.

Otros recursos que podrían interesarte

Temas Virtualpro