# Is a graph with edges between edges and nodes still a graph? [closed]

I am interested in how a structure of the following representation would be called or if there even is an established definition of such a thing.

The structure is similar to a graph. The representation shown here has the following meaning:

• There are nodes A, B and C.
• There are edges x and y.
• Node A has an edge x to node B.
• Node C has an edge y to edge x.

The first three sentences are typical descriptions for a graph. The last one does not fit into the definition of a graph. Here is a representation:

(A)---x------>(B)
^
|
|
y
|
|
(C)


This example could too be modeled using multiple graphs, lists or other structures, but I hope to find something more 'native'.

I'm not aware of a name for such an object, but it can easily be modeled by a single vertex-colored directed graph $$\Gamma$$:

As vertex set of $$\Gamma$$, take the union of the vertices and edges of your original directed graph. Color the original vertices blue and the original edges red. Each original edge has a "source" and a "target", which in your case can be a vertex or an edge.

For the edge set of $$\Gamma$$, add two directed edges for each original edge: one from the source to the edge, and one from the edge to the target.

Now $$\Gamma$$ is a directed graph. (If your initial "thing" was an honest graph, then $$\Gamma$$ is bipartite.)

(sorry for posting as a comment before) A directed graph is a pair of sets $$V$$ and $$E$$ (I use "E", since "A" is already in use in the PO's question.). The first set, $$V$$, contains the vertices, the second set , $$E$$, contains ordered pairs of elements of the vertex set, the "arcs" or directed edges. Nothing prevents you from adding an ordered pair $$(A,B)$$ to the vertex set and then an ordered pair of two elements of the vertex set, say, $$(C,(A, B))$$ to the arcs set.

So one has for the example in the question: $$V=\{A, B, (A,B)\}$$ and $$E=\{(A ,B), (C, (A, B)\}$$. And I would call the OP's example a directed graph.

• Notice that this description does not allow to recover the original object from the resulting directed graph alone: you have to "remember" the description of the elements of $V$. – Tom De Medts Nov 25 '19 at 10:40