Just had this thought and wondered if there was a name for this type of graph that satisfies this transitivity property (would more easily let me read what other people have learned about it if so).

A weighted graph where given any vertices $v_i, v_j, v_k$, the weight of edge $$w(v_i, v_k) = w(v_i, v_j) + w(v_j, v_k)$$

  • $\begingroup$ Does the existence of edges $(v_i,v_j)$ and $(v_j,v_k)$ mean that there must exist a $(v_i,v_k)$ with the weight you specify, or only that if it exists then its weight must be as given by your equation? $\endgroup$ – Henning Makholm Jul 3 '18 at 15:39

Suppose $G$ has at least $3$ vertices, and satisfies the specified edge-weight conditions.

Let $a,b,c$ be distinct vertices of $G$, and let $$r=w(a,b),\;\;\;s=w(b,c),\;\;t=w(c,a)$$ Then we get the system of equations $$ \begin{cases} r=s+t\\[4pt] s=t+r\\[4pt] t=r+s\\ \end{cases} $$ which implies $r=s=t=0$.

Thus, all edge weights must be zero.

  • 1
    $\begingroup$ that is assuming $G$ is a complete undirected graph $\endgroup$ – gt6989b Jul 3 '18 at 16:21
  • $\begingroup$ Yes, I'm assuming that for any two distinct vertices $a,b$, the edge $ab$ has some weight, and that $w(a,b)=w(b,a)$. $\endgroup$ – quasi Jul 3 '18 at 16:45
  • $\begingroup$ Clearly, not a realistic assumption, as your argument most vividly demonstrates. I think the OP is thinking to impose this on a directed incomplete graph $\endgroup$ – gt6989b Jul 3 '18 at 17:04
  • $\begingroup$ Well, I'll edit or delete my answer as soon as the OP clarifies the specs. In the meantime, my answer should at least alert the OP that more explicit assumptions need to be stated in order to avoid having only a trivial solution. $\endgroup$ – quasi Jul 3 '18 at 17:25
  • $\begingroup$ I am not saying you should delete your answer; on the contrary -- it's pointing out a very useful feature $\endgroup$ – gt6989b Jul 3 '18 at 19:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.