Graphs with dangling edges

Question

In conventional Graph Theory the role of Nodes and Edges is skewed: nodes are perfectly ok being aloof, but poor edges are always drawn between existing nodes (that is, the two maps from EDGES to NODES are total).

Now, I am curious to know if there is somewhere in the Mare Magnum of mathematics an extension of Graph Theory, let us call it provisionally the Theory Partial Graphs (it may have already a well-established name, in which case I apologize), which contemplates dangling edges (ie edges which either stand alone, or are attached only to one node).

To be more specific, I would like to see some refs on TYPED partial graphs: dangling edges hare equipped with types, and there is an algebra of sorts which tells which dangling nodes can "merge" with other kindred typed dangling nodes to make up a genuine edge of the graph

(think of nodes which protrude some edges like an octopus, with the possibility of two arms joining and forming a perfectly traditional edge).

Anything along the lines above?

PS Although I do not have any specific preconceptions around the way this theory may appear (for instance, as some kind of algebra, or as a chapter of topology), ideally it would be codes within a categorical framework

Answer 1

Yes, there are such things.

Consider the monoid $M$ of endomaps $\{0,1\} \to \{0,1\}$. It has four elements: the constant maps 0 and 1, the identity map $i$ and the "swap" map $s$. Let $\mathcal{G}$ be the category of right $M$-actions. These are sets equipped with a map $m : A \times M \to A$ such that $m(x, i) = x$ and $m(x, f \circ g) = m(m(x, f), g)$. A morphism is a map which commutes with the actions. I will write $x \cdot f$ instead of $m(x, f)$. (All this is very common, except that we have a monoid instead of a group.)

Let us think of the elements of an $M$-set $A$ as half-edges. Each half-edge $e \in A$ has an associated opposite half-edge $e \cdot s$. Call a half-edge $e$ a vertex when $e \cdot 0 = e$ (exercise: $e \cdot 0 = e \iff e \cdot 1 = e$). Each half-edge $e$ has an origin which is $e \cdot 0$, while $e \cdot 1$ is the origin of its opposite half-edge $e \cdot s$. It is possible to have a half-edge which is its own opposite, $e \cdot s = e$ (these are your dangling edges). The graphs are reflexive because every vertex $v$ has a distinguished half-edge attached to it, namely $v$ itself.

Explicitly, we have the following equivalent presentation of $\mathcal{G}$:

1. objects are sets $(V, H)$ of vertices and half edges such that:

   • each half-edge $e \in H$ has an origin $o(e) \in V$
   • each half-edge $e$ has an opposite half-edge $s(e) \in E$
   • each vertex $v \in V$ has a distinguished half-edge $\ell(v) \in H$ such that $o(\ell(v)) = v$ and $s(\ell(v)) = \ell(v)$

2. A morphism $(V,H) \to (V',H')$ is a pair of maps $f : V \to V'$ and $g : H \to H'$ such that $g(\ell(v)) = \ell(f(v))$, $f(o(e)) = o(g(e))$, and $s(g(e)) = g(s(e))$. Morphisms are composed component-wise.

This an more can be read about in:

William F. Lawvere, Qualitative distinctions between some toposes of generalized graph, Contemporary mathematics, Vol. 92, 1989, pp. 261-299.

Answer 2

The theory of signed graphs might be helpful. Although they were conceived in the social sciences (hey, how many math concepts do you know that can claim that...?), they are can be viewed as a type-B analogue of graphs (in the representation-theoretic sense), and as such half edges appear quite natural. (They can also have loose edges, which have no endpoint. That's arguably a bit weird, but again, it fits naturally into the theory.) If this sounds remotely interesting, start with Zaslavsky's excellent survey article or his annotated bibliography.

Answer 3

Once you are in the setting where vertices have types (which usually would be called "colours" in the graph literature), there is little point in having edges with missing endpoints - just use introduce a new colour for vertices that are "not really there" (and if you want to distinguish different kinds of edges, give the virtual vertices different colours).

Now the situation that vertices in a graph are identified according to some rules seems to be pretty common occurrance. E.g. a simple system of the kind you are interested in could be described in the following way using a more typical graph theory language:

Let G, H be a graph where the vertices are coloured red, green and white. Write $G \preceq H$ if there are two vertices $v, u$ in $H$ such that $v$ is coloured red, $u$ is coloured green and that $G$ is obtained from $H$ by identifying $v$ and $u$ and colouring the resulting vertex white.

Question: Given some particular coloured graph $H$, what are the graphs $G \preceq H$ coloured completely white?

I'm not aware of any good overview on such approaches, but hopefully such a reformulation can help you finding the kind of results you are looking for.

Answer 4

Such graphs were used in differential geometry to describe the gluing construction. See

Kapouleas, Nicolaos, Complete constant mean curvature surfaces in Euclidean three-space, Ann. Math. (2) 131, No. 2, 239-330 (1990). ZBL0699.53007.

for the gluing construction of constant mean curvature (CMC) surfaces, and

Traizet, Martin, Construction de surfaces minimales en recollant des surfaces de Scherk. (Minimal surfaces constructed by gluing Scherk surfaces.), Ann. Inst. Fourier 46, No. 5, 1385-1442 (1996). ZBL0860.53004.

Traizet, Martin, Weierstrass representation of some simply-periodic minimal surfaces, Ann. Global Anal. Geom. 20, No. 1, 77-101 (2001). ZBL1033.53008.

for the gluing construction of minimal surfaces (MS). A formal treatment of such graph (in the context of MS) can be found in a recent preprint of mine https://arxiv.org/abs/2107.06957 , where I used "pseudo rotation system" to define them.

In these context, the vertices are glued components (spheres for CMC, saddle towers for MS), edges indicate gluing patters, and rays are ends (Delaunay ends for CMC, Scherk ends for MS).

Answer 5

A graph with dangling edges can be simply a bipartitioned graph where the set of vertices splits into a union $\ V:=A\cup B\ $ of disjoint sets $\ A\ B, $ and vertices $\ b\in B\ $ can have at the most two neighbors (from $\ A).\ $

The partition into $\ A\ B\ $ has to be specified in the general case if we want a unique representation of the bi-partitioned graph as a graph with dangling edges so that vertices from $\ B\ $ would be interpreted as the dangling edges.

Answer 6

There exist partial algebras ( having nontotal basic operations ), multi-typed structures, hypergraphs, and various flavors of categories, so why not partial multigraphs?

Unfortunately, your description is too brief for me to provide specific references. You may want some version of multi-typed clone or n-category variant. Also, you should come up with a sound reason for why you want a dangling edge instead of a terminated edge. (Electrical engineers do it for safety, so should data scientists.)

I recommend talking to yourself more about what you want to do with these objects, and then hit the data modeling literature or perhaps those texts applying categories to computer science. Waiting a couple days and then asking a better version on data or CS forums wouldn't hurt, not much anyway.