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?

-
 If you disallow the one-element ring, there are easy examples for G_k(R), including the two element ring. So I conclude that the one-element ring is allowed. Also, just to check, are loops (edges with one vertex) allowed? Gerhard "Let's Not Mention Empty Rings" Paseman, 2011.07.20 – Gerhard Paseman Jul 21 2011 at 6:06 I messed up the definition of the graph. I apologize for the previous (erroneous) remarks and question. Gerhard "Back To The Scratch Pad" Paseman, 2011.07.20 – Gerhard Paseman Jul 21 2011 at 6:10 For $\mathbb F_2$ one has $G_0(\mathbb F_2)=G_1(\mathbb F_2)=\emptyset$ according to the definitions above. I would like to have a generic counter-example with a number of vertices that is arbitrarily large, and have $G_k(R)$ connected. I'm going to allow loops for now. – Gjergji Zaimi Jul 21 2011 at 6:13

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$.

-
 I like your answer. It is a lot simpler than my other idea of pairs of left and right ideals for the case k=0, which did not extend nicely to nonzero k. Just as well I kept quiet about that. Gerhard "Ask Me About System Design" Paseman, 2011.07.23 – Gerhard Paseman Jul 23 2011 at 21:18 Sorry it took me a while to accept this answer. I just played around to convince myself that small variations of this really produce counterexamples under all sorts of requirements. – Gjergji Zaimi Aug 3 2011 at 0:24

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.

-
 Thank you for this reference. At the moment I don't have access to the paper, but I can read from the abstract that one of their results is that they classify the rings for which the zero-divisor graph is a complete graph, a bipartite graph or a tree. Does their result imply which bipartite graphs or trees appear as zero-divisor graphs? If so, I'd appreciate it if you could add this information to the answer. +1 – Gjergji Zaimi Jul 21 2011 at 1:40 I have sent you the paper. – Mark Sapir Jul 21 2011 at 2:28 Ah, thanks again! – Gjergji Zaimi Jul 21 2011 at 2:42

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.

 It is true that the case of semigroups is similar but easier than the case of rings, and one should start with semigroups. I would also first consider the case when $k=1$ (the identity element). Use the fact that in the bicyclic semigroup $\langle a,b\mid ab=1\rangle$, the product $ba$ is not 1. – Mark Sapir Jul 23 2011 at 2:58