Geodesic
The strong isometric dimension of finite reflexive graphs
Discussiones Mathematicae. Graph Theory, Tome 20 (2000) no. 1, pp. 23-38.

Voir la notice de l'article provenant de la source Library of Science

The strong isometric dimension of a reflexive graph is related to its injective hull: both deal with embedding reflexive graphs in the strong product of paths. We give several upper and lower bounds for the strong isometric dimension of general graphs; the exact strong isometric dimension for cycles and hypercubes; and the isometric dimension for trees is found to within a factor of two.
Keywords: isometric, embedding, strong product, injective hull, paths, distance, metric 
@article{DMGT_2000_20_1_a1,
     author = {Fitzpatrick, Shannon and Nowakowski, Richard},
     title = {The strong isometric dimension of finite reflexive graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {23--38},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2000},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2000_20_1_a1/}
}
TY  - JOUR
AU  - Fitzpatrick, Shannon
AU  - Nowakowski, Richard
TI  - The strong isometric dimension of finite reflexive graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2000
SP  - 23
EP  - 38
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2000_20_1_a1/
LA  - en
ID  - DMGT_2000_20_1_a1
ER  - 
%0 Journal Article
%A Fitzpatrick, Shannon
%A Nowakowski, Richard
%T The strong isometric dimension of finite reflexive graphs
%J Discussiones Mathematicae. Graph Theory
%D 2000
%P 23-38
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2000_20_1_a1/
%G en
%F DMGT_2000_20_1_a1
Fitzpatrick, Shannon; Nowakowski, Richard. The strong isometric dimension of finite reflexive graphs. Discussiones Mathematicae. Graph Theory, Tome 20 (2000) no. 1, pp. 23-38. http://geodesic.mathdoc.fr/item/DMGT_2000_20_1_a1/

[1] M. Aigner and M. Fromme, A game of cops and robbers, Discrete Appl. Math. 8 (1984) 1-12. MR 85f:90124.

[2] T. Andreae, On a pursuit game played on graphs for which the minor is excluded, J. Combin. Theory (B) 41 (1986) 37-47. MR 87i:05179.

[3] G. Chartrand and L. Lesniak, Graphs and Digraphs (second edition, Wadsworth, 1986).

[4] S.L. Fitzpatrick, A polynomial-time algorithm for determining if idim(G) ≤ 2,preprint 1998.

[5] S.L. Fitzpatrick and R.J. Nowakowski, Copnumber of graphs with strong isometric dimension two, to appear in Ars Combinatoria.

[6] J.R. Isbell, Six theorems about injective metric spaces, Comment. Math. Helv. 39 (1964) 65-76. MR 32#431.

[7] E.M. Jawhari, D. Misane and M. Pouzet, Retracts: graphs and ordered sets from the metric point of view, Contemp. Math. 57 (1986) 175-226. MR 88i:54022.

[8] E.M. Jawhari, M. Pouzet and I. Rival, A classification of reflexive graphs: the use of 'holes', Canad. J. Math. 38 (1986) 1299-1328. MR 88j:05038.

[9] S. Neufeld, The Game of Cops and Robber, M.Sc Thesis, Dalhousie University, 1990.

[10] R. Nowakowski and I. Rival, The smallest graph variety containing all paths, Discrete Math. 43 (1983) 223-234. MR 84k:05057.

[11] R. Nowakowski and I. Rival, A fixed edge theorem for graphs with loops, J. Graph Theory 3 (1979) 339-350. MR 80j:05098.

[12] R. Nowakowski and P. Winkler, Vertex to vertex pursuit in a graph, Discrete Math. 43 (1983) 235-239. MR 84d:05138.

[13] E. Pesch, Minimal extensions of graphs to absolute retracts, J. Graph Theory 11 (1987) 585-598. MR 89g:05102

[14] A. Quilliot, These d'Etat (Université de Paris VI, 1983).

[15] P. Winkler, The metric structure of graphs: theory and applications (London Math. Soc. Lecture Note Ser., 123, Cambridge Univ. Press, Cambridge-New York, 1987). MR 88h:05090.