Bell and Stirling numbers for graphs

Duncan, Bryce ; Peele, Rhodes

Journal of integer sequences, Tome 12 (2009) no. 7

Résumé

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(P_{n}) = B(E_{n-1})$ for path and edgeless graphs, one-parameter graph families whose Bell number sequences are quasigeometric, and relations among the polynomial $A(G,\alpha ) = \Sigma S(G,k) \alpha ^{k}$, the chromatic polynomial and the Tutte polynomial, and some implications of these relations.

Détail

Classification : 05A18, 05A15, 05B35, 05C05, 05C50, 05C85
Keywords: simple graph, stable partition, graphical Bell number, graphical Stirling number, chromatic polynomial, matroid, tutte polynomial