Motivated by the recent experiments indicating superconductivity in metal-decorated graphene sheets, we investigate their quasi-particle structure within the framework of an effective tight-binding Hamiltonian augmented by appropriate BCS-like pairing terms for p-type order parameter. The normal state band structure of graphene is modified not only through interaction with adsorbed metal atoms, but also due to the folding of bands at Brillouin zone boundaries resulting from a [Formula: see text] reconstruction. Several different types of pairing symmetries are analyzed utilizing Nambu-Gorkov Green's function techniques to show that [Formula: see text]-symmetric nearest-neighbor pairing yields the most enhanced superconducting gap. The character of the order parameter depends on the nature of the atomic orbitals involved in the pairing process and exhibits interesting angular and radial asymmetries. Finally, we suggest a method to distinguish between singlet and triplet type superconductivity in the presence of magnetic substitutional impurities using scanning tunneling spectroscopy.