Comentarios sobre la dimensión métrica del vértice y del borde de grafos 2-conectados
Autores: Knor, Martin; Sedlar, Jelena; krekovski, Riste
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Comentarios sobre la dimensión métrica del vértice y del borde de grafos 2-conectados
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Vértice
Arista
Dimensión métrica
Grafo
Límites
Cacti
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 39
Citaciones: Sin citaciones
La dimensión métrica del vértice (respectivamente arista) de un grafo es el tamaño de un conjunto de vértices más pequeño en , que distingue todos los pares de vértices (respectivamente aristas) en , y se denota por (respectivamente ). Los límites superiores y donde denota el número ciclomático de , se establecieron para cactos sin hojas distintas de los ciclos, y además, se caracterizaron todos los cactos sin hojas que alcanzan los límites. Se postuló además que los mismos límites se cumplen para grafos conectados generales sin hojas, y esta conjetura fue respaldada al mostrar que el problema se reduce a grafos 2-conectados. En este documento, nos enfocamos en -gráficos, como los grafos 2-conectados más simples distintos del ciclo, y mostramos que el límite superior se cumple para ambas dimensiones métricas de -gráficos; caracterizamos todos los -gráficos para los cuales se alcanza el límite. Concluimos con la conjetura de que no hay otros grafos extremos para el límite en la clase de grafos sin hojas además de los cactos extremos ya conocidos y los -gráficos extremos mencionados aquí.
Descripción
La dimensión métrica del vértice (respectivamente arista) de un grafo es el tamaño de un conjunto de vértices más pequeño en , que distingue todos los pares de vértices (respectivamente aristas) en , y se denota por (respectivamente ). Los límites superiores y donde denota el número ciclomático de , se establecieron para cactos sin hojas distintas de los ciclos, y además, se caracterizaron todos los cactos sin hojas que alcanzan los límites. Se postuló además que los mismos límites se cumplen para grafos conectados generales sin hojas, y esta conjetura fue respaldada al mostrar que el problema se reduce a grafos 2-conectados. En este documento, nos enfocamos en -gráficos, como los grafos 2-conectados más simples distintos del ciclo, y mostramos que el límite superior se cumple para ambas dimensiones métricas de -gráficos; caracterizamos todos los -gráficos para los cuales se alcanza el límite. Concluimos con la conjetura de que no hay otros grafos extremos para el límite en la clase de grafos sin hojas además de los cactos extremos ya conocidos y los -gráficos extremos mencionados aquí.