Isometric embedding in products of complete graphs

DOI10.1016/0166-218X(84)90069-6zbMath0529.05055WikidataQ60587841 ScholiaQ60587841MaRDI QIDQ787171

Peter M. Winkler

Publication date: 1984

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

isometric embeddingHamming distancevertex-labellingcartesian productdistance-preserving

Mathematics Subject Classification ID

Graph theory (05C99)

Related Items (only showing first 100 items - show all)

An algorithm for embedding Turán graphs into incomplete hypercubes with minimum wirelength ⋮ Recognizing binary Hamming graphs inO(n 2 logn) time ⋮ On dominating graph of graphs, median graphs, partial cubes and complement of minimal dominating sets ⋮ Hypercube embeddings and Cayley graphs generated by transpositions ⋮ Edge general position sets in Fibonacci and Lucas cubes ⋮ Subquadratic-time algorithm for the diameter and all eccentricities on median graphs ⋮ Factorization and pseudofactorization of weighted graphs ⋮ First-order logic axiomatization of metric graph theory ⋮ Isometric subgraphs of Hamming graphs and d-convexity ⋮ Efficient proper embedding of a daisy cube ⋮ There are no finite partial cubes of girth more than 6 and minimum degree at least 3 ⋮ Faster isometric embedding in products of complete graphs ⋮ Cut method and Djoković-Winkler's relation ⋮ Convex excess in partial cubes ⋮ Recognizing Hamming graphs in linear time and space ⋮ Convexity in finite metric spaces ⋮ Topes of oriented matroids and related structures ⋮ The classification of finite connected hypermetric spaces ⋮ A theorem on Wiener-type invariants for isometric subgraphs of hypercubes ⋮ Tiled partial cubes ⋮ On the natural imprint function of a graph ⋮ Distance Preserving Ramsey Graphs ⋮ Computing distance moments on graphs with transitive Djoković-Winkler relation ⋮ Constructions of 1-uniform dcsl graphs using well-graded families of sets ⋮ The \(t\)-median function on graphs ⋮ Vertex cut method for degree and distance-based topological indices and its applications to silicate networks ⋮ Isometric embeddings in Hamming graphs ⋮ On cube-free median graphs ⋮ Fast recognition of classes of almost-median graphs ⋮ A correction of a characterization of planar partial cubes ⋮ Characterizing almost-median graphs ⋮ On finding convex cuts in general, bipartite and plane graphs ⋮ Generalizations of Wiener polarity index and terminal Wiener index ⋮ Wiener number of vertex-weighted graphs and a chemical application ⋮ Fibonacci-run graphs. I: Basic properties ⋮ Partial cubes and their \(\tau\)-graphs ⋮ Hamming polynomials and their partial derivatives ⋮ On some properties of antipodal partial cubes ⋮ On bipartite graphs whose interval space is a closed join space ⋮ On the extendability of code isometries ⋮ FUNDAMENTALS OF MEDIA THEORY ⋮ A counterexample to Thiagarajan's conjecture on regular event structures ⋮ Bounds on the \(\alpha \)-distance energy and \(\alpha \)-distance Estrada index of graphs ⋮ On partial cubes, well-graded families and their duals with some applications in graphs ⋮ Quasi-median graphs, their generalizations, and tree-like equalities ⋮ Convexity in partial cubes: the hull number ⋮ Isometric embeddings of subdivided wheels in hypercubes ⋮ Fast recognition algorithms for classes of partial cubes ⋮ Partition distance in graphs ⋮ Isometric Hamming embeddings of weighted graphs ⋮ Hyperplane arrangements with a lattice of regions ⋮ Structure of Fibonacci cubes: a survey ⋮ Wiener index in weighted graphs via unification of \(\varTheta^\ast\)-classes ⋮ Tree-like partial Hamming graphs ⋮ Mostar index ⋮ Distance-based topological indices of nanosheets, nanotubes and nanotori of SiO\(_2\) ⋮ Further Results on Two Families of Nanostructures ⋮ Graphene Derivatives: Carbon Nanocones and CorSu Lattice: A Topological Approach ⋮ Mathematical Aspects of Omega Polynomial ⋮ Cubic inflation, mirror graphs, regular maps, and partial cubes ⋮ On some characterizations of antipodal partial cubes ⋮ Projection of a medium ⋮ Fibonacci \((p,r)\)-cubes as Cartesian products ⋮ Generalized Fibonacci cubes ⋮ Weak geodesic topology and fixed finite subgraph theorems in infinite partial cubes. I: Topologies and the geodesic convexity ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ On the dimension of vertex labeling of k-uniform dcsl of an even cycle ⋮ Netlike partial cubes. I. General properties ⋮ Fast recognition of Fibonacci cubes ⋮ The Szeged index and the Wiener index of partial cubes with applications to chemical graphs ⋮ On the geodetic number of median graphs ⋮ Distance-preserving subgraphs of Johnson graphs ⋮ Computing equivalence classes among the edges of a graph with applications ⋮ On the remoteness function in median graphs ⋮ The lattice dimension of a graph ⋮ \(\Theta\)-graceful labelings of partial cubes ⋮ Isometric Diamond Subgraphs ⋮ A characterization of planar partial cubes ⋮ Partial cubes: Structures, characterizations, and constructions ⋮ Searching for realizations of finite metric spaces in tight spans ⋮ On tope graphs of complexes of oriented matroids ⋮ On antipodal and diametrical partial cubes ⋮ On semicube graphs ⋮ Fully gated graphs: Recognition and convex operations ⋮ Daisy cubes: a characterization and a generalization ⋮ Subdivided graphs as isometric subgraphs of Hamming graphs ⋮ Netlike partial cubes, IV: Fixed finite subgraph theorems ⋮ On the geodesic pre-hull number of a graph ⋮ Netlike partial cubes II. Retracts and netlike subgraphs ⋮ Netlike partial cubes III. The median cycle property ⋮ Daisy cubes and distance cube polynomial ⋮ A poset-based approach to embedding median graphs in hypercubes and lattices ⋮ Topological indices of the subdivision of a family of partial cubes and computation of \(\mathrm{SiO}_2\) related structures ⋮ On verifying and engineering the wellgradedness of a union-closed family ⋮ Netlike partial cubes, V: completion and netlike classes ⋮ Isometric embeddings of subdivided connected graphs into hypercubes ⋮ Induced cycles in crossing graphs of median graphs ⋮ Not all partial cubes are \(\Theta \)-graceful ⋮ An Euler-type formula for median graphs ⋮ The edge general position problem

Cites Work

• Unnamed Item
• Proof of the squashed cube conjecture
• Distance-preserving subgraphs of hypercubes
• On the Addressing Problem for Loop Switching

This page was built for publication: Isometric embedding in products of complete graphs