Isometric embeddings in Hamming graphs (Q1110526): Difference between revisions

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.

0 references

Mathematics Subject Classification ID

05C10

0 references

zbMATH DE Number

4072992

0 references

zbMATH Keywords

embedding

0 references

gated subgraph

0 references

hypercube

0 references

isometric subgraph

0 references

algorithm

0 references

Hamming graph

0 references

Cartesian product

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1016/0095-8956(90)90073-9

0 references

0 references

0 references

Hypermetric Spaces and the Hamming Cone

0 references

Graphs with intrinsic s3 convexities

0 references

Distance-preserving subgraphs of hypercubes

0 references

Gated sets in metric spaces

0 references

On cubical graphs

0 references

On Isometric Embeddings of Graphs

0 references

On the Addressing Problem for Loop Switching

0 references

0 references

0 references

0 references

0 references

0 references

The retracts of Hamming graphs

0 references

Isometric embedding in products of complete graphs

0 references

On connectivity of triangulations of manifolds

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1110526

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/0095-8956(90)90073-9
+Normal rank
@@ Property / OpenAlex ID @@
+W1980124329
@@ Property / OpenAlex ID: W1980124329 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4091421
@@ Property / cites work: Q4091421 / rank @@
+Normal rank
@@ Property / cites work @@
+Hypermetric Spaces and the Hamming Cone
@@ Property / cites work: Hypermetric Spaces and the Hamming Cone / rank @@
+Normal rank
@@ Property / cites work @@
+Graphs with intrinsic s3 convexities
@@ Property / cites work: Graphs with intrinsic s3 convexities / rank @@
+Normal rank
@@ Property / cites work @@
+Distance-preserving subgraphs of hypercubes
@@ Property / cites work: Distance-preserving subgraphs of hypercubes / rank @@
+Normal rank
@@ Property / cites work @@
+Gated sets in metric spaces
@@ Property / cites work: Gated sets in metric spaces / rank @@
+Normal rank
@@ Property / cites work @@
+On cubical graphs
@@ Property / cites work: On cubical graphs / rank @@
+Normal rank
@@ Property / cites work @@
+On Isometric Embeddings of Graphs
@@ Property / cites work: On Isometric Embeddings of Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+On the Addressing Problem for Loop Switching
@@ Property / cites work: On the Addressing Problem for Loop Switching / rank @@
+Normal rank
@@ Property / cites work @@
+Q4052150
@@ Property / cites work: Q4052150 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3333644
@@ Property / cites work: Q3333644 / rank @@
+Normal rank
@@ Property / cites work @@
+On cliques in graphs
@@ Property / cites work: On cliques in graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q3890733
@@ Property / cites work: Q3890733 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3734453
@@ Property / cites work: Q3734453 / rank @@
+Normal rank
@@ Property / cites work @@
+The retracts of Hamming graphs
@@ Property / cites work: The retracts of Hamming graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Isometric embedding in products of complete graphs
+Normal rank
@@ Property / cites work @@
+On connectivity of triangulations of manifolds
@@ Property / cites work: On connectivity of triangulations of manifolds / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:1110526