Consider - for the sake of simplicity - only *graphs* as structures.

For undirected graphs $(V, E\subseteq \binom{V}{2})$ let

$E(v)$ be the set of edges $e\in E$ incident with $v$, i.e. $\lbrace e \ |\ v \in e\rbrace$

$N(v)$ be the set of vertices $w\in V$ connected with $v$, i.e. $\lbrace w \ |\ v - w\rbrace$

where $v - w$ denotes $\exists\ e = \lbrace v,w\rbrace$.

Let for arbitrary sets $X$, $Y$ denote $X\ \text{o}\mkern-5mu\text{o}\ Y$ the fact that $X \cap Y \neq \emptyset$.

It's a trivial matter of fact that in every undirected graph

$$v - w\quad \text{iff}\quad E(v)\ \text{o}\mkern-5mu\text{o}\ E(w)\quad\quad(\ast) $$

In this respect every undirected graph is supposed to be a *self-modelling structure*, because it provides a model of itself by a set construction over its vertices.

For directed graphs $(V, E\subseteq V^2)$ things are not so simple. Let

$E_{in}(v)$ be the set of in-arrows $e\in E$ of $v$, i.e. $\lbrace e \ |\ \exists w\ e = (w,v)\rbrace$

$E_{out}(v)$ be the set of out-arrows of $v$, i.e. $\lbrace e \ |\ \exists w\ e = (v,w)\rbrace$

$N_{in}(v)$ be the set $\lbrace w \ |\ w \rightarrow v\rbrace$

$N_{out}(v)$ be the set $\lbrace w \ |\ v \rightarrow w\rbrace$

where $v \rightarrow w$ denotes $\exists\ e = (v,w)$.

The first sensible "proposition" half-way similar to $(\ast)$ seems to be

$$v \rightarrow w\quad \text{iff}\quad N_{in}(v)\ \subseteq\ N_{in}(w)\quad\quad(\ast\ast) $$

but this holds only for a resctricted family of digraphs: the transitive digraphs. Interesting enough.

I wonder whether there are other set constructions $F$ over the vertices of a (di)graph and other (un)directed relations $\approx$/$\Rightarrow$ between sets such that

$$v - w\quad \text{iff}\quad F(v)\ \approx \ F(w) $$

resp.

$$v \rightarrow w\quad \text{iff}\quad F(v)\ \Rightarrow\ F(w) $$

for other interesting families of (di)graphs.

twoset constructions would be involved: $E_{in}$ and $E_{out}$. On the other side: why not? – Hans Stricker Jun 20 '13 at 0:26