Hostname: page-component-6898cfcb55-cbk24 Total loading time: 0 Render date: 2026-11-11T10:45:25.659Z Has data issue: false hasContentIssue false
  • English
  • Français

Strong Isometric Dimension, Biclique Coverings, and Sperner's Theorem

Published online by Cambridge University Press:  01 March 2007

DALIBOR FRONČEK,
JANJA JEREBIC,
SANDI KLAVŽAR and
PETR KOVÁŘ
DALIBOR FRONČEK
Affiliation:
Department of Mathematics and Statistics, University of Minnesota Duluth, 1117 University Drive, Duluth, MN 55812, USA (e-mail: dfroncek@d.umn.edu)
JANJA JEREBIC
Affiliation:
Department of Mathematics and Computer Science, PeF, University of Maribor, Korošska cesta 160, 2000 Maribor, Slovenia (e-mail: janja.jerebic@uni-mb.si, sandi.klavzar@uni-mb.si)
SANDI KLAVŽAR
Affiliation:
Department of Mathematics and Computer Science, PeF, University of Maribor, Korošska cesta 160, 2000 Maribor, Slovenia (e-mail: janja.jerebic@uni-mb.si, sandi.klavzar@uni-mb.si)
PETR KOVÁŘ
Affiliation:
Department of Mathematics and Descriptive Geometry, Technical University of Ostrava, 17. listopadu 15, 708 33 Ostrava-Poruba, Czech Republic (e-mail: petr.kovar@vsb.cz)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The strong isometric dimension of a graph G is the least number k such that G isometrically embeds into the strong product of k paths. Using Sperner's theorem, the strong isometric dimension of the Hamming graphs K2 □ Kn is determined.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 16 , Issue 2 , March 2007, pp. 271 - 275
Copyright
Copyright © Cambridge University Press 2006

References

[1]Chung, F. R. K. (1980) On the coverings of graphs. Discrete Math. 30 89–93.CrossRefGoogle Scholar
[2]Chung, F. R. K. (1981) On the decomposition of graphs. SIAM J. Algebraic Discrete Methods 2 1–12.CrossRefGoogle Scholar
[3]Dewdney, A. K. (1980) The embedding dimension of a graph. Ars Combin. 9 77–90.Google Scholar
[4]Engel, K. (1997) Sperner Theory, Vol. 65 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge.CrossRefGoogle Scholar
[5]Fitzpatrick, S. L. and Nowakowski, R. J. (2000) The strong isometric dimension of finite reflexive graphs. Discuss. Math. Graph Theory 20 23–38.CrossRefGoogle Scholar
[6]Fitzpatrick, S. L. and Nowakowski, R. J. (2001) Copnumber of graphs with strong isometric dimension two. Ars Combin. 59 65–73.Google Scholar
[7]Füredi, Z. and Kündgen, A. (2001) Covering a graph with cuts of minimum total size. Discrete Math. 237 129–148.CrossRefGoogle Scholar
[8]Imrich, W. and Klavžar, S. (2000) Product Graphs: Structure and Recognition, Wiley, New York.Google Scholar
[9]Isbell, J. R. (1964) Six theorems about injective metric spaces. Comment. Math. Helv. 39 65–76.CrossRefGoogle Scholar
[10]Jerebic, J. and Klavžar, S. (2006) On induced and isometric embeddings of graphs into the strong product of paths. Discrete Math. 306 1358–1363.CrossRefGoogle Scholar
[11]Nešetřil, J. and Rödl, V. (1985) Three remarks on dimensions of graphs. Ann. Discrete Math. 28 199–207.Google Scholar
[12]Nowakowski, R. J. and Winkler, P. (1983) Vertex to vertex pursuit in a graph. Discrete Math. 43 235–239.CrossRefGoogle Scholar
[13]Poljak, S. and Pultr, A. (1981) Representing graphs by means of strong and weak products. Comment. Math. Univ. Carolin. 22 449–466.Google Scholar
[14]Schoenberg, I. J. (1938) Metric spaces and positive definite functions. Trans. Amer. Math. Soc. 44 522–536.CrossRefGoogle Scholar
[15]Tomescu, I. (2002) Irreducible coverings by cliques and Sperner's theorem. Electron. J. Combin. 9 #N11, 4 pp.CrossRefGoogle Scholar