Graph problem known to be $NP$-complete only under Cook reduction
I know an example of a problem that is missing two of the four features you ask for - it is not NP-complete, and it is not a problem on graphs.

Buchfuhrer and Umans (2011) show that the minimum equivalent expression problem in Boolean logic is complete for $\Sigma^P_2$ under polynomial-time Turing reductions.

Given a Boolean $(\wedge;\vee;\neg)$-formula $F$ and
an integer $k$, is there an equivalent $(\wedge;\vee;\neg)$-formula of size at most $k$?

On p. 143, the authors state:


  This provides a somewhat rare example of a natural problem for which a Turing reduction seems crucial (in the sense that we do not know of any simple modification or alternative methods that would give a many-one
  reduction).


They do not cite any other such examples from the literature. I suspect that "somewhat rare" is possibly an understatement.

References

David Buchfuhrer and Christopher Umans: "The complexity of Boolean formula minimization" Journal of Computer and System Sciences, Volume 77, Issue 1, January 2011, Pages 142-153