Sesión Matemática DiscretaReconstrucción de grafos a partir de coordenadas métricas.
Mercè Mora
Universitat Politècnica de Catalunya, España - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Dado un grafo G y un conjunto ordenado W de k vértices de G, podemos asociar a cada vértice u del grafo un vector con k coordenadas, donde la coordenada i-ésima es la distancia de u al k-ésimo vértice de W. Llamamos coordenadas métricas a dichas distancias.
Se dice que el conjunto W es resolutivo si a vértices distintos del grafo les corresponden vectores de coordenadas métricas distintos. En este caso, el conjunto de vectores de coordenadas métricas de los vértices del grafo forman un conjunto S de vectores con coordenadas enteras no negativas de cardinal el orden del grafo.
En este trabajo estudiamos el problema inverso, es decir, dado un conjunto S de vectores con coordenadas enteras no negativas, determinar si existen un grafo G y un conjunto resolutivo W de forma que S sea precisamente el conjunto de todos los vectores de coordenadas métricas de los vértices de G respecto al conjunto resolutivo W. En caso de existir tales G y W, decimos que S es realizable.
En este trabajo hemos caracterizado los conjuntos realizables y analizado la unicidad de la realización. Además, hemos estudiado algunas propiedades del grafo que se pueden deducir directamente del conjunto S, como por ejemplo, realizaciones minimales respecto al número de aristas del grafo y conjuntos que se pueden realizar con árboles.
Trabajo en conjunto con: María Luz Puertas (Universidad de Almería, España) y Víctor Franco-Sánchez (Universitat Politècnica de Catalunya, España).
Referencias
[1] M. Mora, M.L. Puertas, On the metric representation of the vertices of a graph, Bull. Malays. Math. Sci. Soc. 46 (2023), #187.