Sometime you want to model some data from the real world using a graph, but such that edges don't just connect to a vertex; rather, they connect to some aspect of that vertex - some connection if you will.

For example, a node in a family tree would be a person, and they have a mother and father (never mind about adoptions etc.). Now, when you connect one of the parents to the child you want to connect it as "the father" or "the mother"; so a "connections graph" model for this tree would see each vertex have a set of 3 possible connections: "father, mother, child" (with the child being used to connect it to its biological children's nodes).

It's true that you can always get around really needing connections, e.g. with gadgets in their stead (say, each connection has a gadget vertex, so an original vertex is now surrounded by its connections as satellites and edges only exist between these satellites). But I'm interested in dealing with such connections explicitly.

So, connections can be represented by a set; or as an ordered sequence (perhaps even always $0...\Delta$ with $\Delta$ being the maximum degree of the graph); or the edge set could incorporate the connections apriori, i.e. an endpoint could always be a tuple of a vertex and something else. And the connection set might be shared, or per-vertex; and so on.

My question is: What are some specific formalizations of this concept which are used often (if there are such at all)?


  • I don't care whether it's a directed graph or not, you can always switch from directed to undirected and back in a relatively straightforward way.
  • Here's a diagram of one of these:

    digraph G {
        a->b [taillabel="x"; headlabel="y"]
        b->c [taillabel="z"; headlabel="w"]

    enter image description here

  • 1
    $\begingroup$ Maybe I'm misunderstanding you, but don't you simply mean that you have different types of edges, and you want to make a distinction between each type (i.e. saying there is an edge from $u$ to $v$ isn't enough to encode the information you have). If so, this is referred to as a labeled graph (with labeling on the edges). $\endgroup$ – Ariel Jun 10 '17 at 16:53
  • $\begingroup$ @Ariel: Not quite, since the "types" of edges might be vertex-specific. If every vertex has $k$ connections, all distinct, and $|V(G)| = n$, then there are $(kn)^2$ possible types of edges. Still, if you decided that the connections are always $0,...,k-1$, then there are $k^2$ types of edges and that's fine. I mean, that's one possible way to formalize connections. $\endgroup$ – einpoklum Jun 10 '17 at 16:57
  • $\begingroup$ Just the part "endpoint could always be a tuple of a vertex". Is this part covered by the notion of hypergraph? $\endgroup$ – Apiwat Chantawibul Jun 10 '17 at 22:24
  • $\begingroup$ Also the part "connections can be represented by a set; or as an ordered sequence" is confusing. because a set is not the same as an ordered sequence. Typical set is not ordered. $\endgroup$ – Apiwat Chantawibul Jun 10 '17 at 22:27
  • $\begingroup$ @Billiska: While it's possible to model a "graph with connections" as a 4-uniform oriented hypergraph, that's quite unnecessary; a pair of vertex-connection tuples would be quite sufficient, i.e. just a digraph. About the set vs ordered sequence - of course it's not the same, but those are two options for representing the connections. $\endgroup$ – einpoklum Jun 10 '17 at 23:09

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.