Small nanoparticles of III-V compound semiconductors have often been considered to have open-cage structures. However, using first-principles calculations, we report the finding of a structural transition from empty-cage structures for (AlN) n and (GaN) n nanoparticles up to n = 34 that we studied, to a filled-cage structure for (InN) 32. Further, phosphides and arsenides of Al and In have an early transition to three-dimensional (3D) filled-cage structures. Our results show that a 3D (AlP) 13 is strongly magic with high binding energy and large highest occupied-lowest unoccupied molecular orbital gap. But nanoparticles of GaP show a transition from an empty cage for n = 13 to a strongly magic 3D filled cage for n = 32. The latter has a cage of (GaP) 28 and a (GaP) 4 squashed cube inside, the atoms on which are well connected with the cage. The bonding characteristics and the reason for structural transition are discussed. {\textcopyright} 2012 American Physical Society.