This study presents a theoretical analysis of partitional clustering on networks. Different versions of the problem are studied considering different assignment schemes (hard and soft) and different objective functions. Cluster centers are not restricted to only the set of nodes, it is assumed that centers can also be at the edges of the network. Four clustering problems are investigated namely P-Median (PMP), Sum of Squares Clustering (SSCS) under hard assignment, as well as the Probabilistic Distance Clustering (PDP) and Fuzzy C-Means Clustering (FCM) problems under soft assignment. Through mathematical analysis, we establish new structural properties of these problems, such as the significance of assignment bottleneck points and the role of vertex-restricted solutions in determining optimal cluster centers. Our findings demonstrate that, while SSC and FCM problems allow optimal centers to be positioned along edges, PMP and PDC inherently favor vertex placement, leading to insights into clustering behavior on networks. These results open avenues for the development of efficient heuristics and metaheuristics that leverage these properties, with potential applications in facility location, network design, and data clustering on networks.