Timeline for A question about minimal graph of diameter $2$
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 28, 2016 at 1:31 | vote | accept | user173856 | ||
| Aug 31, 2016 at 14:14 | comment | added | benblumsmith | In case of $C_4$, for each edge there is a pair of vertices (namely, the pair incident to that edge) such that the unique path of length $\leq 2$ connecting them goes through that edge. | |
| Aug 31, 2016 at 14:13 | comment | added | benblumsmith | @GerhardPaseman - Actually I think the OP is right. The condition stated in the OP is: for any edge, there exists a pair of vertices u,v with a path of length ≤2 connecting them and containing that edge, and there does not exist any other path of length ≤2 connecting those vertices (whether containing the given edge or not). The OP is right that this condition is implied by being min of diam 2, since for deletion of an edge to increase the diam there must be a pair of vertices with the only path of length ≤2 between them going through the deleted edge. | |
| Aug 30, 2016 at 20:09 | comment | added | Gerhard Paseman | I challenge your implication. Let $G$ be a four-vertex cycle. It is a minimal graph of diameter 2, but there are not unique paths for all pairs u-v. (Every edge does belong to a unique u-v path such that the path contains u and contains v and contains that edge, but this is a different condition from what you have stated.) In spite of this, I think the answer to your question is yes. Gerhard "Don't Have A Proof Now" Paseman, 2016.08.30. | |
| Aug 30, 2016 at 19:47 | answer | added | benblumsmith | timeline score: 2 | |
| Aug 30, 2016 at 16:03 | history | edited | user173856 | CC BY-SA 3.0 |
added 4 characters in body
|
| Aug 30, 2016 at 15:51 | history | asked | user173856 | CC BY-SA 3.0 |