Isometric Hamming embeddings of weighted graphs.

Area of Science:

• Graph Theory
• Combinatorial Optimization
• Discrete Mathematics

Background:

• Isometric embeddings preserve shortest path distances between graph vertices.
• Hamming graphs are unweighted graphs relevant to coding theory and computer science.
• Prior work focused on Hamming embeddings of unweighted graphs into complete graphs.

Purpose of the Study:

• To investigate isometric embeddings of weighted graphs into unweighted Hamming graphs (Hamming embeddings).
• To leverage the canonical isometric representation of graphs for analyzing Hamming embeddings.
• To establish conditions for the existence of Hamming embeddings for weighted graphs.

Main Methods:

• Definition of Hamming embeddings for weighted graphs into unweighted Hamming graphs.
• Utilizing the Cartesian product decomposition of a graph, known as its canonical isometric representation.
• Introducing the concept of a canonical partition for Hamming embeddings.

Main Results:

• Every Hamming embedding of a graph can be partitioned into a canonical partition.
• The parts of the canonical partition provide Hamming embeddings for each factor of the graph's canonical isometric representation.
• A graph permits a Hamming embedding if and only if each factor in its canonical isometric representation is Hamming embeddable.

Conclusions:

• The study extends previous results on unweighted graphs to weighted graphs.
• The existence of a Hamming embedding for a graph is determined by the embeddability of its canonical isometric representation factors.
• For graphs with nontrivial isometric representations, determining Hamming embeddability can be simplified by analyzing smaller component graphs.