Download PDF - The strong isometric dimension of finite reflexive graphsAll rights reserved. Copyright exceptions and limitations apply

ArticleOriginal scientific text

Title

The strong isometric dimension of finite reflexive graphs

Authors 1, 2

Affiliations

  1. University of Victoria, Victoria, British Columbia
  2. Dalhousie University, Halifax, Nova Scotia

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.

Keywords

ENG
isometric, embedding, strong product, injective hull, paths, distance, metric

Bibliography

  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.
Discussiones Mathematicae Graph Theory
2000/20/1
Export to PBN, Opens in new tab
Pages:
23-38
Main language of publication
English
Received
1998-11-30
Accepted
1999-12-13
Published
2000

DOI: 10.7151/dmgt.1104

Exact and natural sciences