This vessel was among the list of ships that appeared on Captain Jean-Luc Picard's desktop monitor while he searched for "all Earth deep-space launches from 2123 until 2190 with destination in or near the Ficus sector" during an investigation of an SOS signal discovered in that sector in 2365. This vessel, however, did not fall within the parameters of his search, but was among the ships launched in that timeframe. (TNG: "Up The Long Ladder")
Named for Yuri Gagarin, first man in space, the VK Yuri Gagarin appeared on an okudagram on Picard's desk monitor and was not verbally referenced on screen. A legible version of the okudagram appeared in the reference book, Star Trek: The Next Generation - The Continuing Mission.
Based on usage it is probable that the VK prefix means a Russian ship in Star Trek – as might also be the case with the VK Velikan. In the real world, the Russians do not use prefixes for their ship names.
In the book The Hunt for Red October, the primary Alfa-class attack sub is named V.K. Konovalov, in honor of Vladimir Konstantinovich Konovalov. This suggests that the use of VK as a Russian prefix, is either an error on the part of the Star Trek writers, or an homage to Tom Clancy.
In universe, 'VK' could be explained as standing for Voenny Korabl, the romanization of Военный Корабль, which means Military Ship.