Stephen Wilson's The Means of Naming provides insight into the naming of Roman public slaves. His discussion touches on the sources of personal names and names of slaves owned privately, but also includes treatment of the naming of the servus publicus.
First, he notes that the phrase servus publicus, or part of it, was often part of their name:
Public slaves belong to the State or to cities had the status indicator "servus publicus", from which "servus" was frequently omitted: for example, Herodes publicus; Laeus publicus populi Romani.
When a second name was employed, it often referred back to the previous owner:
During the Empire, two names were more common, with the second name referring usually to the previous owner who had sold the slave to the State, for example, Fortunatus publicus Sulpicianus; or Bithus publicus Paullianus.
The form here is neither nominative nor genitive, but rather the -ianus suffix is added to turn the noun into an adjective.
Slaves owned by towns and cities sometimes used the previous owner's name, but often employed the name of the town or city:
So we have Priscus colono. Aquil. s., from Aquileia, or Zosimus municipium Vercellensium vilicus, from Vercelli.
In addition, the occupation of the slave could be incorporated:
Diodumenus publicus aquae Annesis and Laeus publicus populi Romani... aquarius aquae Annionis Veteris both worked for the water services of Rome; Felix arcarius republicae Neapolitanorum was municipal cashier of Naples.
Slaves of the emperor were named differently from slaves of the state, as they were owned by the individual emperors. Thus:
"To the single personal name,... the emperor's slaves added the distinctive mark of status 'Caes(aris) ser(vus)' or 'Aug(usti) vern(a)', or simply 'Aug(usti)' or 'Caes(aris)'" with the "servus" understood. From the Flavian period the form Caes. n.(ostri) ser. became predominant, for example: Victorinus Caes. n. ser.; or Maximus Caes. n. vern..
Wilson's research indicates that the names of public slaves often included the name of the former masters, the city in which they worked, or their occupation. The forms of these second names varied, but often employed either a genitive or adjectival ending, just as was the case with privately owned slaves.
Stephen Wilson, The Means of Naming, 25–27.