Navigating in a Graph by Aid of Its Spanning Tree

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 tree-distances). 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 r

-carcass

for

G

if

g

G

,

T

(

x

,

y

) ≤ 

d

G

(

x

,

y

) + 

r

for each ordered pair

x

,

y

 ∈ 

V

. In this paper, we investigate the problem, given a graph family

${\cal F}$

, whether a small integer

r

exists such that any graph

$G\in {\cal F}$

admits an additive

r

-carcass. We show that rectilinear

p

×

q

grids, hypercubes, distance-hereditary graphs, dually chordal graphs (and, therefore, strongly chordal graphs and interval graphs), all admit additive 0-carcasses. Furthermore, every chordal graph

G

admits an additive (

ω

(

G

) + 1)-carcass (where

ω

(

G

) is the size of a maximum clique of

G

), each 3-sun-free chordal graph admits an additive 2-carcass, each chordal bipartite graph admits an additive 4-carcass. In particular, any

k

-tree admits an additive (

k

 + 2)-carcass. All those carcasses are easy to construct.