logo móvil
Contáctanos

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

Descargar PDF

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


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í.

Otros recursos que podrían interesarte

Temas Virtualpro