Here are the relevant parts of the RFC's:
From RFC 952:
 ASSUMPTIONS
    1. A "name" (Net, Host, Gateway, or Domain name) is a text string up
    to 24 characters drawn from the alphabet (A-Z), digits (0-9), minus
    sign (-), and period (.).  Note that periods are only allowed when
    they serve to delimit components of "domain style names". (See
    RFC-921, "Domain Name System Implementation Schedule", for
    background).  No blank or space characters are permitted as part of a
    name. No distinction is made between upper and lower case.  The first
    character must be an alpha character.  The last character must not be
    a minus sign or period.  A host which serves as a GATEWAY should have
    "-GATEWAY" or "-GW" as part of its name.  Hosts which do not serve as
    Internet gateways should not use "-GATEWAY" and "-GW" as part of
    their names. A host which is a TAC should have "-TAC" as the last
    part of its host name, if it is a DoD host.  Single character names
    or nicknames are not allowed.
 
From RFC 1123:
    2.1  Host Names and Numbers
 
       The syntax of a legal Internet host name was specified in RFC-952
       {DNS:4}.  One aspect of host name syntax is hereby changed: the
       restriction on the first character is relaxed to allow either a
       letter or a digit.  Host software MUST support this more liberal
       syntax.
 
       Host software MUST handle host names of up to 63 characters and
       SHOULD handle host names of up to 255 characters.