Abstract 
Let $G=(V,E)$ be a graph and T be a spanning tree of G. We consider the following strategy in advancing in G from a vertex x towards a target vertex y: from a current vertex z (initially, $z=x$), unless $z=y$, go to a neighbor of z in G that is closest to y in T (breaking ties arbitrarily). In this strategy, each vertex has full knowledge of its neighborhood in G and can use the distances in T to navigate in G. Thus, additionally to standard local information (the neighborhood $N_G(v)$), the only global information that is available to each vertex v is the topology of the spanning tree T (in fact, v can know only a very small piece of information about T and still be able to infer from it the necessary treedistances). For each source vertex x and target vertex y, this way, a path, called a greedy routing path, is produced. Denote by $g_{G,T}(x,y)$ the length of a longest greedy routing path that can be produced for x and y using this strategy and T. We say that a spanning tree T of a graph G is an additive rcarcass for G if $g_{G,T}(x,y)\leq d_G(x,y)+r$ for each ordered pair $x,y\in V$. In this paper, we investigate the problem, given a graph family $\mathcal{F}$, of whether a small integer r exists such that any graph $G\in\mathcal{F}$ admits an additive rcarcass. We show that rectilinear $p\times q$ grids, hypercubes, distancehereditary graphs, dually chordal graphs (and, therefore, strongly chordal graphs and interval graphs) all admit additive 0carcasses. Furthermore, every chordal graph G admits an additive $(\omega+1)$carcass (where $\omega$ is the size of a maximum clique of G), each 3sunfree chordal graph admits an additive 2carcass, and each chordal bipartite graph admits an additive 4carcass. In particular, any ktree admits an additive $(k+2)$carcass. All those carcasses are easy to construct in sequential as well as in distributed settings.

Recommended Citation 
Dragan, Feodor F; Matamala, Martin (2011). Navigating in a Graph by Aid of Its Spanning Tree Metric. SIAM Journal on Discrete Mathematics 25(1) 306332. Retrieved from https://oaks.kent.edu/cspubs/2

Copyright 2011 Society for Industrial and Applied Mathematics.