# The strong isometric dimension of finite reflexive graphs

Shannon L. Fitzpatrick; Richard J. Nowakowski

Discussiones Mathematicae Graph Theory (2000)

- Volume: 20, Issue: 1, page 23-38
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topShannon L. Fitzpatrick, and Richard J. Nowakowski. "The strong isometric dimension of finite reflexive graphs." Discussiones Mathematicae Graph Theory 20.1 (2000): 23-38. <http://eudml.org/doc/270276>.

@article{ShannonL2000,

abstract = {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.},

author = {Shannon L. Fitzpatrick, Richard J. Nowakowski},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {isometric; embedding; strong product; injective hull; paths; distance; metric; strong isometric dimension; bounds; cycles; hypercubes; trees},

language = {eng},

number = {1},

pages = {23-38},

title = {The strong isometric dimension of finite reflexive graphs},

url = {http://eudml.org/doc/270276},

volume = {20},

year = {2000},

}

TY - JOUR

AU - Shannon L. Fitzpatrick

AU - Richard J. Nowakowski

TI - The strong isometric dimension of finite reflexive graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2000

VL - 20

IS - 1

SP - 23

EP - 38

AB - 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.

LA - eng

KW - isometric; embedding; strong product; injective hull; paths; distance; metric; strong isometric dimension; bounds; cycles; hypercubes; trees

UR - http://eudml.org/doc/270276

ER -

## References

top- [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. Zbl0641.90110
- [3] G. Chartrand and L. Lesniak, Graphs and Digraphs (second edition, Wadsworth, 1986). Zbl0666.05001
- [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. Zbl1066.05118
- [6] J.R. Isbell, Six theorems about injective metric spaces, Comment. Math. Helv. 39 (1964) 65-76. MR 32#431. Zbl0151.30205
- [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. Zbl0597.54028
- [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. Zbl0508.05058
- [13] E. Pesch, Minimal extensions of graphs to absolute retracts, J. Graph Theory 11 (1987) 585-598. MR 89g:05102 Zbl0649.05050
- [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. Zbl0624.05042

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.