# Self-referentially defined graph structures

It is possible to define graphs $G$ such that whether an edge exists between two vertices $v_1$ and $v_2$ depends on non-local properties of $G$.

In particular, I am interested in directed graphs where an edge $(v_1, g(v_1, w))$ exists for each leaf vertex $w$ that is reachable from $f(v_1)$. Here, $f$ maps vertices to vertices, $g$ maps pairs of vertices to vertices.

Is there research on data structures and algorithms for working with such self-referentially defined graph structures?

-
For your example you must impose some restrictions of $f$ and $g$. If the set of vertices is $\{0,1\}$ and $f(x)=x$ and $g(x,y)=1-y$, then is $(0,1)$ an edge? –  Radu GRIGore Mar 8 '12 at 17:20
@RaduGRIGore Right, the setup allows self-defeating and underspecified definitions. Any existing work that fills in $f$ and $g$ in consistent, non-trivial ways would be an answer to my question. –  Andreas Mar 8 '12 at 17:51
I was recently thinking about self-referential paradoxes on graphs. nice question ! –  Suresh Venkat Mar 8 '12 at 18:00
there are recursively defined graphs that exhibit self-similarity properties, e.g. the diamond graphs used for dimension reduction lower bounds: www.cs.washington.edu/homes/jrl/papers/diamond1.pdf –  Sasho Nikolov Mar 8 '12 at 21:51