On Isometric Embeddings of Graphs

DOI10.2307/1999951zbMath0576.05017MaRDI QIDQ3697031

Peter M. Winkler, Ronald L. Graham

Publication date: 1985

Full work available at URL: https://doi.org/10.2307/1999951

zbMATH Keywords

eigenvalues; canonical embedding; distance matrix; irreducible factors; irredundancy

Mathematics Subject Classification ID

05C10: Planar graphs; geometric and topological aspects of graph theory

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

Related Items

Factoring cartesian‐product graphs, Isometric subgraphs of Hamming graphs and d-convexity, Metric Transforms and Euclidean Embeddings, Unnamed Item, Factoring a graph in polynomial time, A dynamic location problem for graphs, Computing equivalence classes among the edges of a graph with applications, A note on Winkler's algorithm for factoring a connected graph, A polynomial time algorithm for finding the prime factors of Cartesian- product graphs, Strict refinement for graphs and digraphs, Minimum dimension embedding of finite metric spaces, Collapse of the metric hierarchy for bipartite graphs, Isometric embeddings in Hamming graphs, Representations of graphs and networks (coding, layouts and embeddings), A new fixed point approach for stable networks and stable marriages, Cartesian graph factorization at logarithmic cost per edge, \(\ell_ 1\)-rigid graphs, Metric extensions and the \(L^ 1\) hierarchy, Isometric embeddings into cube-hypergraphs, On the natural imprint function of a graph, Recognizing Cartesian graph bundles, Characterization of products of trees and grids, Finite metric spaces of strictly negative type, Wiener number of vertex-weighted graphs and a chemical application, Retracts of infinite Hamming graphs, Quasi-median graphs, their generalizations, and tree-like equalities, An Euler-type formula for median graphs, Factoring cardinal product graphs in polynomial time, Distances in benzenoid systems: Further developments, On approximating planar metrics by tree metrics., Strong products of \(\chi\)-critical graphs, On subgraphs of Cartesian product graphs and S-primeness, Addressing the Petersen graph, Application of cut polyhedra. I, The geometry of graphs and some of its algorithmic applications, Recognizing halved cubes in a constant time per edge, A characterization of cube-hypergraphs, The algebra of metric betweenness. I: Subdirect representation and retraction, Partial cubes are distance graphs, On induced and isometric embeddings of graphs into the strong product of paths, Characterizing flag graphs and incuced subgraphs of Cartesian product graphs, On the canonical metric representation, average distance, and partial Hamming graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the distance matrix of a tree
• Distance matrix polynomials of trees
• Distance-preserving subgraphs of hypercubes
• Hypermetric Spaces and the Hamming Cone
• Espaces Métriques Plongeables Dans Un Hypercube: Aspects Combinatoires
• Extremal Metrics Induced by Graphs
• On the distance matrix of a directed graph
• On the Loop Switching Addressing Problem
• On the Addressing Problem for Loop Switching
• On the Addressing Problem of Loop Switching