Complejidad de Wiener versus la complejidad excéntrica
Autores: Knor, Martin; krekovski, Riste
Idioma: Inglés
Editor: MDPI
Año: 2020
Acceso abierto
Artículo científico
2020
Complejidad de Wiener versus la complejidad excéntrica
Categoría
Matemáticas
Subcategoría
Matemáticas generales
Palabras clave
Suma
Distancias
Vértices
Gráficos
Complejidad
Valores
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 23
Citaciones: Sin citaciones
Sea la suma de las distancias de a todos los otros vértices de . La complejidad de Wiener, , es el número de valores diferentes en , y la complejidad excéntrica, , es el número de excentricidades diferentes en . En este documento, demostramos que para cada entero hay infinitos grafos tales que . Además, demostramos esta afirmación usando grafos con el menor número cromático posible. Es decir, si demostramos esta afirmación usando árboles, y si lo demostramos usando grafos unicíclicos. Además, demostramos que si es un grafo unicíclico. En nuestras pruebas utilizamos que la función es convexa en caminos que consisten en puentes. Esta propiedad también implica de inmediato el límite ya conocido para árboles . Finalmente, respondemos positivamente a una pregunta abierta encontrando infinitos grafos con diámetro 3 tales que .
Descripción
Sea la suma de las distancias de a todos los otros vértices de . La complejidad de Wiener, , es el número de valores diferentes en , y la complejidad excéntrica, , es el número de excentricidades diferentes en . En este documento, demostramos que para cada entero hay infinitos grafos tales que . Además, demostramos esta afirmación usando grafos con el menor número cromático posible. Es decir, si demostramos esta afirmación usando árboles, y si lo demostramos usando grafos unicíclicos. Además, demostramos que si es un grafo unicíclico. En nuestras pruebas utilizamos que la función es convexa en caminos que consisten en puentes. Esta propiedad también implica de inmediato el límite ya conocido para árboles . Finalmente, respondemos positivamente a una pregunta abierta encontrando infinitos grafos con diámetro 3 tales que .