Journal of Integer Sequences, Vol. 18 (2015), Article 15.1.7

Enumerating Families of Labeled Graphs

Christian Barrientos and Sarah Minion
Department of Mathematics
Clayton State University
Morrow, GA 30260


In 1966, Rosa introduced, among others, α- and β-labelings as tools to solve the isomorphic decomposition problem of the complete graph. Ten years later, Sheppard calculated the number of α- and β-labeled graphs with n edges. In this paper we use an extended version of the adjacency matrix of a graph to determine the number of gracefully labeled graphs with n edges; furthermore, we also calculate the number of them with m vertices for every suitable value of m. In addition, we use this technique to determine the number of labeled graphs for other types of labelings as the harmonious, felicitous, and elegant.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A005193 A241094.)

Received July 22 2014; revised versions received November 16 2014; December 5 2014. Published in Journal of Integer Sequences, January 12 2015.

Return to Journal of Integer Sequences home page