Directed multigraphs as minimal automata
Any absorbing node $n$ will have to be either accepting or not (so that either everything or nothing is accepted once $n$ is entered). If the graph has more than two absorbing nodes, then some of them will end up equivalent for any choice of labeling and accepting set. 

More generally, for any strongly connected graph $H$ there is only a finite number $n(H)$ of different possible labelings and accepting subsets; if your graph has more than $n(H)$ terminal strongly connected components equivalent to $H$ (attached at the leaves of a tree, say), it cannot correspond to any minimal automaton.

EDIT, regarding the follow-up question: This sounds tricky. One approach suggested by my argument might look like this:


Partition $G$ into SCCs. This is cheap; $O(|V|+|E|)$ using Tarjan's algorithm.
Sort the SCCs into isomorphism classes. Unfortunately graph isomorphism is not known to be in $P$.
For each terminal isomorphism class, determine the number of permissible corresponding sub-automata, and fail if there are not enough of them. Note that not every combination of accepting subset and edge labeling is permissible: for example, suppose our alphabet is $\{a,b\}$, and a component has two nodes, each with a self-loop and an edge to the other node. Making both nodes accepting and labeling both loops with $a$ (and the other edges with $b$) gives an automaton which is bisimilar to a single absorbing state, violating minimality.
Treat the remaining SCCs in the DAG similarly, taking into account the lower ones; I'm a bit fuzzy on the details of this part.


That is one step whose complexity is famously open, and another one which looks like it may require exponential time (since there may be exponentially many partitions into bisimilarity classes to be excluded when determining permissible automata). Can we do better?