What is the most general definition of a graph?

Question

I would like to give the most general definition of a graph. Based on what I read about graphs, I came up with the following definition:

Let us introduce some symbols. They are

(a) $V$:: a non-empty set of vertices;

(b) $E$:: a set of edges $E$;

(c) $\mathcal{P}(X)$:: the power set of a set $X$;

(d) $\mathit{\Pi}(X)=(\mathcal{P}(X)\cup \bigcup \limits_{i=2}^{\infty}X^i)\setminus \varnothing$:: the alternative power set (with ordered and unordered tuples);

(e) $F$:: a class of functions defined over any subset of $\mathit{\Pi}(V \cup E) \cup (V \cup E)$.

The structure $G=(V,E,F)$ is a (general) graph if there is an $I \in F$ with $I: E \rightarrow \mathit{\Pi}(V \cup E)$, which is called incidence function.

Is this a specification which includes all versions of graphs known in the literature (or at least the most important ones)? Can it happen that an even more general definition is needed for some very special graphs?

It would be also interesting if this formalism could be reduced.

Answer 1

The most general definition that I am aware of is the one of Ubergraphs which generalize Hypergraphs. And Ubergraphs are not included in your definition.

A hypergraph is a pair $(V,E)$ whereby $V$ is a set whose elements are called vertices and $E \subseteq \mathcal{P}(V)$ is a non-empty subset of $V$ whose elements are called hyperedges. A hypergraph allows more than two vertices in an edge of the graph. Hypergraphs can also be directed, and thus generalizing directed graphs.

An Ubergraph goes one step further by allowing not only more than two vertices in each edge but also other edges. All hypergraphs are therefore just some special ubergraphs. And the usual graphs are some special $2$-hypergraphs. Making both versions directed is usually done by introducing an incidence mapping defining two additional mappings for each endpoint (source, target). How this is generalized to Ubergraphs, I do not know.

Answer 2

Common definition is that a graph $G = (V, E)$ is a finite set of vertices $V$ and a set of edges $E$, where an edge $e \in E$ is a set of exactly two vertices. Some allow an infinite set of vertices.

The other stuff (neighbors of $v$, and so on) can be deduced from this.

Note that digraphs (directed graphs) $D = (V, E)$ add a significant difference: The set of edges is a set of pairs of vertices, $E \subseteq V \times V$. They are very different beasts.