Brainiac's Skull Ship (sometimes called his Head-Ship) is an interstellar warship commanded by Brainiac. In fact, the ship can be considered an extension of Brainiac's body, as it's hooked directly into his brain. There have been many variations of the Skull Ship, although they mostly seem to share the form of a humanoid skull with tentacles.
A Post-Crisis version first appeared in the "Panic in the Sky" storyline. This version lacks the tentacles. According to Brainiac, it came to him "in a dream."