I would like to convert PNG images/graphs to EPS without losing even a bit on resolution. All the commands I tried (
gimp) decrease the resolution quality.
Some people have had success with png2eps.
Remember that whatever system you use to convert PNG to EPS it will be a tradeoff between image quality and file size. PNG is a compressed bitmap format while EPS is uncompressed vector graphics - the two formats couldn't be more different.
There is no resolution in a vector image until you attempt to convert it to a bitmap, or display it (a vector image is converted to bitmap for printing or displaying on a monitor). Unfortunately, converting "without losing even a bit on resolution" doesn't make sense in this instance.
Also note that the resulting EPS file will be much larger than the PNG input.