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

Abstract

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

How to cite

top

Shannon 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. [1] M. Aigner and M. Fromme, A game of cops and robbers, Discrete Appl. Math. 8 (1984) 1-12. MR 85f:90124. 
  2. [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. [3] G. Chartrand and L. Lesniak, Graphs and Digraphs (second edition, Wadsworth, 1986). Zbl0666.05001
  4. [4] S.L. Fitzpatrick, A polynomial-time algorithm for determining if idim(G) ≤ 2,preprint 1998. 
  5. [5] S.L. Fitzpatrick and R.J. Nowakowski, Copnumber of graphs with strong isometric dimension two, to appear in Ars Combinatoria. Zbl1066.05118
  6. [6] J.R. Isbell, Six theorems about injective metric spaces, Comment. Math. Helv. 39 (1964) 65-76. MR 32#431. Zbl0151.30205
  7. [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. [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. [9] S. Neufeld, The Game of Cops and Robber, M.Sc Thesis, Dalhousie University, 1990. 
  10. [10] R. Nowakowski and I. Rival, The smallest graph variety containing all paths, Discrete Math. 43 (1983) 223-234. MR 84k:05057. 
  11. [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. [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. [13] E. Pesch, Minimal extensions of graphs to absolute retracts, J. Graph Theory 11 (1987) 585-598. MR 89g:05102 Zbl0649.05050
  14. [14] A. Quilliot, These d'Etat (Université de Paris VI, 1983). 
  15. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.