DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 20(1) (2000) 23-38
DOI: 10.7151/dmgt.1104

THE STRONG ISOMETRIC DIMENSION OF FINITE REFLEXIVE GRAPHS

Shannon L. Fitzpatrick

University of Victoria
Victoria, British Columbia

Richard J. Nowakowski

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: isometric, embedding, strong product, injective hull, paths, distance, metric.

1991 Mathematics Subject Classification: 05C12, 05C75.

References

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

Received 30 November 1998
Revised 13 December 1999