Isometric embeddings of subdivided wheels in hypercubes
For a graph \(G\), the distance \(d_G(u,v)\) between vertices \(u,v\) is defined as the number of edges on a shortest \(u,v\)-path. A subgraph \(H\) of \(G\) is called isometric if \(d_G(u,v)=d_H(u,v)\) for \(u,v\in V(H)\). Isometric subgraphs of hypercubes are called partial cubes. Let \(W_k(m_1,\dots,m_k; n_1,\dots,n_k)\) be the graph obtained by subdividing edges of \(W_k\), where \(m_i\) is the number of vertices added on the edge \(w_iw_{i+1}\), and \(n_i\) the number of vertices added on the inner edge \(uw_i\). In this note the following result is proved: Theorem 1. Let \(k\geq 3\). Then a subdivided wheel \(W\) is a partial cube if and only if \(W\) is isomorphic to \(W_k(m_1,\dots,m_k; n_1,\dots,n_k)\), where \(m_i\) is odd for \(i=1,\dots,k\) and \(n_1=\cdots=n_k=0\), or \(W=W_3(1,1,1;1,1,1)\).
- Isometric Embeddings of Subdivided Complete Graphs in the Hypercube
- Isometric embeddings of subdivided complete graphs in the hypercube
- Isometric embedding of subdivided Connected graphs in the hypercube
- Isometric embeddings of subdivided connected graphs into hypercubes
- Subdivided graphs as isometric subgraphs of Hamming graphs
- A note on \(l_ 1\)-rigid planar graphs
- Antipodal graphs and oriented matroids
- Clin d'oeil on L₁-embeddable planar graphs
- Collapse of the metric hierarchy for bipartite graphs
- Distance-preserving subgraphs of hypercubes
- Geometry of cuts and metrics
- scientific article; zbMATH DE number 2185257 (Why is no real title available?)
- scientific article; zbMATH DE number 1550912 (Why is no real title available?)
- Hypermetric Spaces and the Hamming Cone
- Isometric embedding in products of complete graphs
- Isometric embeddings in Hamming graphs
- Isometric subgraphs of Hamming graphs and d-convexity
- On the Addressing Problem for Loop Switching
- Partial cubes as subdivision graphs and as generalized Petersen graphs
- The structure of median graphs
- Wiener number of vertex-weighted graphs and a chemical application
- Subdivided graphs as isometric subgraphs of Hamming graphs
- Isometric embeddings of subdivided connected graphs into hypercubes
- A theorem on Wiener-type invariants for isometric subgraphs of hypercubes
- Isometric embedding of subdivided Connected graphs in the hypercube
- Isometric embeddings of subdivided complete graphs in the hypercube
- On quadratic embeddability of bipartite graphs and theta graphs
- A characterization of planar partial cubes
This page was built for publication: Isometric embeddings of subdivided wheels in hypercubes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1402086)
