Which graphs are zero-divisor graphs for some ring? Given a (non commutative) ring $R$, we construct a (directed) graph $G_0(R)$ with vertex set $Z(R)\backslash \{0\}$, the zero divisors of $R$ except for $0$. And an edge from $x$ to $y$ whenever $xy=0$. This is called the zero divisor graph of $R$.
My question is, what are the known obstructions to a graph being a zero divisor graph for some ring $R$?

(Edit) Following the reference by M. Sapir below, I found several articles which give partial answers. By this result of Dolžan and Oblak we learn that there are restrictions on the diameter and girth (they work over semirings). In the case of commutative rings, one knows by a result of Belshoff and Chapman, which zero-divisor graphs are planar, and there are similar results for projective zero-divisor graphs and other genera. Another restriction is that the number of edges must be even.
It seems that a characterisation of the set of zero-divisor graphs is open and complicated enough that is only worth studying over special subclasses of graphs. Because of this I would like to focus just on the second question below, which I have the feeling should have an easy counter-example.

I'd also like to ask the same question for a weaker notion of graphs associated to a ring. Let $G_{k}(R)$ be defined for every ring $R$ and $k\in R$ as above but with edges going from $x$ to $y$ whenever $xy=k$ (we can start with the vertex set being all of $R$ and then throw away the isolated vertices).
What graphs can be written as $G_k(R)$ for some pair $(R,k)$? 

Are there graphs which are isomorphic to $G_k(R)$ for some $k\neq 0$ but are not isomorphic to any zero divisor graph?

 A: See Akbari, S.; Mohammadian, A.
Zero-divisor graphs of non-commutative rings. 
J. Algebra 296 (2006), no. 2, 462–479, for example. The second question is answered below. 
A: The answer to the second question is "no". Consider first the case of semigroups. Take the bicyclic semigroup $B=\langle a,b \mid ab=1\rangle$. It consists of elements of the form $b^ma^n$, $m,n\ge 0$ (that representation is unique because $ab\to 1$ is a confluent and terminating rewriting system, see also A. H. Clifford and G. B. Preston, "The algebraic theory of semigroups" or http://en.wikipedia.org/wiki/Bicyclic_semigroup). Take $k=1$. The corresponding graph consists of countably many disjoint edges $a^m\to b^m$, $m\ge 0$. Now suppose that this graph is the zero divisor graph of some semigroup $S$ with 0. Then it should have $p,q$ with $pq=0$. Since for every $x\in S$ we have $(xp)q=0$, we should have $xp\to q$ in the zero-divisor graph (the option  $xp=0$ does not occur because in our graph there are no edges $x\to p$). Hence $xp=p$ for every $x\ne 0\in S$. Similarly for every $x\ne 0\in S$ we have $qx=q$. Therefore $q=qp=p$, a contradiction. This argument works also for rings. One needs to consider the semigroup ring $FB$ for any field $F$, and take $k=1$. The corresponding graph is not the zero divisor graph of any (associative) ring.
In general if $R$ is a ring with 1 containing two elements $a,b$ such that $ab=1$ but $ba\ne 1$, and $a,b$ are not zero divisors, then the graph corresponding to 1 in $R$ is not a zero divisor graph of any ring $R'$. Indeed, in such a ring $R'$ we would have $ab=0, ba\ne 0$, and $xa=a, bx=b$ for every $x\ne 0$. Hence $a=ba=b$. The fact that $xa\ne 0$ (hence $xa=a$ in $R'$ is true because in $R$ we have $xa\ne 1$ for every $x$ (if $xa=1$, then $x=xab=b$, so $ba=1$, a contradiction). The fact that $xa=a$ is true because in $R$, $zb=1$ implies $z=a$ since $b$ is not a zero divisor. Similar for $bx=b$. 
A: Here is an idea which is not fully worked out.  At best, it is a refinement of Gjergji's refinement.  However, a negative answer would also answer Gjergji's question above, and on the other hand a construction might provide insight on building a zero divisor graph which is isomorphic to a graph for other kinds of nonzero k.
I am thinking in terms of semigroups, and have not checked that a ring will have this kind of multiplication.  One major difference between 0 and a nonzero k is that nilpotent x will have all powers greater than some power equal to 0; this does not always hold for nonzero k which is a power of some x.  In particular, if $x^{n+m}=x^n$ for some nonzero x and m > 1, there will be a subgraph of the graph for $x^n$ which will have at most one loop and a bunch of disjoint pairs of vertices with edges going in both directions between the members of the pair.  It might be arranged in the ring that k can only be a power of x, in which case there will be no edges in the graph for k other than among powers of x.  Now for the refinement:  Assuming a ring exists with $x$ not nilpotent, $k= x^j$ and satisfying $x^n=x^{n+m}$, with appropriate choices for integers j,n and m, can one build a different ring with zero divisor graph matching the graph for k in this ring?  I think choosing the integers mod q for some really large q will work for certain tuples of parameters j,n, and m, but I haven't checked all tuples.
Gerhard "Ask Me About System Design" Paseman, 2011.07.22
