Journal of Integer Sequences, Vol. 12 (2009), Article 09.7.1

Bell and Stirling Numbers for Graphs

Bryce Duncan
Department of Mathematics
Auburn University
221 Parker Hall
Auburn University, AL 36849

Rhodes Peele
Department of Mathematics
Auburn University Montgomery
P. O. Box 244023
Montgomery, AL 36124-4023


The Bell number B(G) of a simple graph G is the number of partitions of its vertex set whose blocks are independent sets of G. The number of these partitions with k blocks is the (graphical) Stirling number S(G,k) of G. We explore integer sequences of Bell numbers for various one-parameter families of graphs, generalizations of the relation B(Pn) = B(En-1) for path and edgeless graphs, one-parameter graph families whose Bell number sequences are quasigeometric, and relations among the polynomial A(G,α) = Σ S(G,k) αk, the chromatic polynomial and the Tutte polynomial, and some implications of these relations.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000032 A000045 A000110 A000296 A129847.)

Received April 28 2009; revised version received October 8 2009. Published in Journal of Integer Sequences, October 13 2009.

Return to Journal of Integer Sequences home page