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](http://arxiv.org/abs/1012.2470) 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](http://www.sciencedirect.com/science/article/pii/S0021869307003924), which zero-divisor graphs are planar, and there are similar results for [projective](http://www.sciencedirect.com/science/article/pii/S0021869307005716) 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?
> 
> 
> 



Which graphs are zero-divisor graphs for some ring?
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$. 


