We have investigated the correlation between the variation in the melting temperature and the growth pattern of small positively charged gallium clusters. Significant shift in the melting temperatures was observed for a change of only few atoms in the size of the cluster. Clusters with size between 31-42 atoms melt between 500-600 K whereas those with 46-48 atoms melt around 800 K. Density functional theory based first principles simulations have been carried out on Ga-n(+) clusters with n = 31, ... , 48. At least 150 geometry optimizations have been performed towards the search for the global minima for each size resulting in about 3000 geometry optimizations. For gallium clusters in this size range, the emergence of spherical structures as the ground state leads to higher melting temperature. The well-separated core and surface shells in these clusters delay isomerization, which results in the enhanced stability of these clusters at elevated temperatures. The observed variation in the melting temperature of these clusters therefore has a structural origin. (C) 2013 American Institute of Physics. [http://dx.doi.org/10.1063/1.4772470]