| dc.description.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
NG(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
gG,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 gG,T (x, y) ≤ dG(x, y)+r
for each ordered pair x, y ∈ V . In this paper, we investigate the problem,
given a graph family F, whether a small integer r exists such that
any graph G ∈ 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. | |
