 | This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
Name "partial cube"
editThe graphs were not "named partial cubes by Hans–Jürgen Bandelt in 1998" as the article formerly said. Source: H.-J. Bandelt, personal communication, April 2, 2013. We are not sure of the origin of the name. 139.124.3.100 (talk) 10:42, 2 April 2013 (UTC)
isometry
editIsometry article makes no mention of graphs, so what does isometry mean for a graph? —Tamfang (talk) 07:13, 4 March 2024 (UTC)
- That the unweighted shortest path distances are the same. What else could it mean? The term is defined (with a link to the definition of distance used) in the very next sentence, and the first sentence of a Wikipedia article is not exactly the place for long-winded pedantic detailed explanations. —David Eppstein (talk) 08:11, 4 March 2024 (UTC)
- Is it different from isomorphism? —Tamfang (talk) 06:53, 30 March 2024 (UTC)
- Yes. It is a stronger condition even than being an induced subgraph. For instance, consider a graph that looks like -<>- (a four-cycle with two leaves attached to opposite points on the four-cycle). It is isomorphic to an induced subgraph of a 3-cube, but not isometric: in -<>- the two leaves are at distance four but in the 3-cube they are at distance two. -<>- is a partial cube but representing it isometrically requires a 4-cube so the two leaves can point off in different directions. There are other induced subgraphs of hypercubes that are not partial cubes at all but they are more complicated; for instance, glue two copies of -<>- at their leaves. I think the wording "isometric to a subgraph of" is probably not the most precise. What is intended is that the distance between vertices in the partial cube is the same as the distances between the corresponding vertices in the whole cube. That wording was added by an anonymous editor in 2019 [1]; I have restored the older and more precise wording "isometric subgraph of" [2]. —David Eppstein (talk) 07:28, 30 March 2024 (UTC)
- Now I get it, thanks. —Tamfang (talk) 04:21, 31 March 2024 (UTC)
- Yes. It is a stronger condition even than being an induced subgraph. For instance, consider a graph that looks like -<>- (a four-cycle with two leaves attached to opposite points on the four-cycle). It is isomorphic to an induced subgraph of a 3-cube, but not isometric: in -<>- the two leaves are at distance four but in the 3-cube they are at distance two. -<>- is a partial cube but representing it isometrically requires a 4-cube so the two leaves can point off in different directions. There are other induced subgraphs of hypercubes that are not partial cubes at all but they are more complicated; for instance, glue two copies of -<>- at their leaves. I think the wording "isometric to a subgraph of" is probably not the most precise. What is intended is that the distance between vertices in the partial cube is the same as the distances between the corresponding vertices in the whole cube. That wording was added by an anonymous editor in 2019 [1]; I have restored the older and more precise wording "isometric subgraph of" [2]. —David Eppstein (talk) 07:28, 30 March 2024 (UTC)
- Is it different from isomorphism? —Tamfang (talk) 06:53, 30 March 2024 (UTC)