  We associate a graph ${\mathcal N}_{S}$ with a semigroup $S$ (called the
upper non-nilpotent graph of $S$). The vertices of this graph are the elements
of $S$ and two vertices are adjacent if they generate a semigroup that is not
nilpotent (in the sense of Malcev). In case $S$ is a group this graph has been
introduced by A. Abdollahi and M. Zarrin and some remarkable properties have
been proved. The aim of this paper is to study this graph (and some related
graphs, such as the non-commuting graph) and to discover the algebraic
structure of $S$ determined by the associated graph. It is shown that if a
finite semigroup $S$ has empty upper non-nilpotent graph then $S$ is positively
Engel. On the other hand, a semigroup has a complete upper non-nilpotent graph
if and only if it is a completely simple semigroup that is a band. One of the
main results states that if all connected ${\mathcal N}_{S}$-components of a
semigroup $S$ are complete (with at least two elements) then $S$ is a band that
is a semilattice of its connected components and, moreover, $S$ is an iterated
total ideal extension of its connected components. We also show that some
graphs, such as a cycle $C_{n}$ on $n$ vertices (with $n\geq 5$), are not the
upper non-nilpotent graph of a semigroup. Also, there is precisely one graph on
4 vertices that is not the upper non-nilpotent graph of a semigroup with 4
elements. This work also is a continuation of earlier work by Okni\'nski, Riley
and the first named author on (Malcev) nilpotent semigroups.
