Seminari de Geometria Computacional (grup DCCG)

Un vèrtex v d'un graf connex G es diu que és un vèrtex límit de G si, per a algun altre vèrtex u de G, cap veí de v està més lluny d'u que v. El límit ∂(G) de G és el conjunt de tots els seus vèrtexs límit. La matriu de distàncies DG d'un graf G = ([n], E) és la matriu quadrada d'ordre n, tal que per a cada i, j ∈ [n], [DˆG]ij = dG(i, j). La matriu de distàncies límit DˆG de G és la matriu quadrada d'ordre κ, sent κ l'ordre de ∂(G), tal que per a cada i, j ∈ ∂(G), [DˆG]ij = dG(i, j). Donada una matriu quadrada B d'ordre n, mostrem sota quines condicions B és la matriu de distàncies DT d'un arbre T. Donada una matriu quadrada Bˆ d'ordre κ, provem sota quines condicions Bˆ és la matriu de distàncies DˆT del conjunt de fulles d'un arbre T, que és precisament el seu límit. Mostrem que si G és un arbre o un graf unicíclic, aleshores G està determinat únicament per la matriu de distàncies DˆG del límit de G i també conjecturem que aquesta afirmació és vàlida per a cada graf connex G, sempre que tant l'ordre n com el límit (i per tant també la seva matriu de distàncies) de G estiguin prefixats.