Recently, Ma et al. introduced the notion of $C^{*}$ -valued metric spaces and extended the Banach contraction principle for self-mappings on $C^{*}$ -valued metric spaces. Motivated by the work of Jachymski, in this paper we extend and improve the result of Ma et al. by proving a fixed point theorem for self-mappings on $C^{*}$ -valued metric spaces satisfying the contractive condition for those pairs of elements from the metric space which form edges of a graph in the metric space. Our result generalizes and extends the main result of Jachymski and Ma et al. We also establish some examples to elaborate our new notions and to substantiate our result.