×

Isometric embeddings in Hamming graphs. (English) Zbl 0657.05023

An \(O(n^ 3)\)-algorithm is established which embeds a given graph isometrically into a Hamming graph (i.e., a Cartesian product of complete graphs) whenever possible, and recognizes non-embeddable graphs. From the algorithm several characterizations of the embeddable graphs are derived.
Reviewer: E.Wilkeit

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., (The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA) · Zbl 0326.68005
[2] Avis, D., Hypermetric spaces and the Hamming cone, Canad. J. Math., 33, 795-802 (1981) · Zbl 0445.52008
[3] Bandelt, H.-J, Graphs with intrinsic \(S_3\) convexities, J. Graph Theory, 13, 215-228 (1989)
[4] Čepoj, V. D., Izometričeskie podgrafy grafov Hamminga, (VII. sesojuznaja Konferencija, Problemy Teoretičeskoj Kibernetiki (1985), Tezicy Doklodov: Tezicy Doklodov Irkutsk), 199
[5] Djoković, D.Ž, Distance-preserving subgraphs of hypercubes, J. Combin. Theory Ser. B, 14, 263-267 (1973) · Zbl 0245.05113
[6] Dress, A. W.M; Scharlau, R., Gated sets in metric spaces, Aequationes Math., 34, 112-120 (1987) · Zbl 0696.54022
[7] Eigen, M.; Winkler-Oswatitsch, R., Transfer-RNA: The early adaptor, Naturwissenschaften, 68, 217-228 (1981)
[8] Firsov, V. V., Isometric embedding of a graph in a Boolean cube, Kibernetika. Kibernetika, Cybernetics, 1, 112-113 (1965), [Russian]; Ensl. transl
[9] Garey, M. R.; Graham, R. L., On cubical graphs, J. Combin. Theory Ser. B, 18, 84-95 (1975) · Zbl 0301.05104
[10] Goldman, A. J.; Witzgall, C. J., A localization theorem for optimal facility placement, Transportation Sci., 4, 406-409 (1970)
[11] Graham, R. L.; Winkler, P. M., On isometric embeddings of graphs, Trans. Amer. Math. Soc., 288, 527-536 (1985) · Zbl 0576.05017
[12] Graham, R. L.; Pollak, H. O., On the addressing problem for loop switching, Bell. Syst. Tech. J., 50, 2495-2519 (1971) · Zbl 0228.94020
[13] Harary, F., Graphentheorie (1974), Oldenbourg: Oldenbourg München/Wien, English transl. Addison-Wesley Reading, MA, 1969 · Zbl 0298.05102
[14] Hedlíková, J., Ternary spaces, media and Chebyshev sets, Czechoslovak Math. J., 33, 373-389 (1983) · Zbl 0544.51011
[15] Moon, J.; Moser, L., On cliques in graphs, Israel J. Math., 3, 23-28 (1965) · Zbl 0144.23205
[16] Mulder, H. M., The Interval Function of a Graph, (Math. Centre Tracts, Vol. 132 (1980), Mathematisch Centrum: Mathematisch Centrum Amsterdam) · Zbl 0446.05039
[17] Turán, P., On an extremal problem in graph theory, Mat. Fiz. Lapok, 48, 436-452 (1941), [Hungarian]
[18] Wilkeit, E., Isometrische Untergraphen von Hamming-Graphen, (Tagungsband zum Kolloquium über Kombinatorik (1982), Universität Bielefeld) · Zbl 0599.05059
[19] Wilkeit, E., Isometrische Untergraphen von Hamming-Graphen, (Dissertation (1986), Universität Oldenburg) · Zbl 0599.05059
[20] E. WilkeitDiscrete Math.; E. WilkeitDiscrete Math. · Zbl 0759.05085
[21] Winkler, P. M., Isometric embedding in products of complete graphs, Discrete Appl. Math., 7, 221-225 (1984) · Zbl 0529.05055
[22] Winkler, P. M., The metric structure of graphs, (Whitehead, C., Surveys in Combinatorics 1987 (1987), Cambridge Univ. Press: Cambridge Univ. Press Cambridge) · Zbl 0436.05040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.