When a graph has parallel edges and self loops one cannot identify an edge with the set of two adjacent vertices it connects. I have failed to find a good formal definition of a non-simple graph. This is my attempt:

An edge weighted graph $G = (V, E, \omega, \gamma)$ is a set of vertices $V$ together with a set of edge $E$, a function $\gamma: E \rightarrow \{\{u, v\}: u, v \in V\}$ and a weight function $\omega: E\rightarrow R$.

I am wondering whether this is sound, and what is a good standard name for the function $\gamma$ in this context.

  • 1
    $\begingroup$ No, it should not be defined as a multiset. Otherwise one cannot assign different weights to two edges with the same endpoints. $\endgroup$ – George Octavian Rabanca Apr 20 '15 at 17:35
  • 3
    $\begingroup$ The definition looks correct, and except for weights, it’s identical to the one given in en.wikipedia.org/wiki/… . $\endgroup$ – Emil Jeřábek Apr 20 '15 at 17:35
  • $\begingroup$ Thank you. I guess my main question is whether there is a standard name for the function $\gamma$. I wouldn't want to confuse the readers by make up a new name for something standard. $\endgroup$ – George Octavian Rabanca Apr 21 '15 at 15:37

Your Answer

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

Browse other questions tagged or ask your own question.