Isometric embeddings of subdivided wheels in hypercubes (Q1402086)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Isometric embeddings of subdivided wheels in hypercubes |
scientific article |
Statements
Isometric embeddings of subdivided wheels in hypercubes (English)
0 references
19 August 2003
0 references
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)\).
0 references
isometric embedding
0 references
hypercube
0 references
wheel
0 references