Proper Partitions, Graphical Stirling Numbers, and Bell Numbers for Multipartite and Mycielskian Graphs

Explicit formulas for graphical Stirling and Bell numbers are known for relatively few graph families. We derive exact expressions for three classes whose independence structure admits a complete combinatorial description: complete multipartite graphs, the graph obtained from a balanced complete bipartite graph by deleting a perfect matching, and the Mycielskian of a star. For complete multipartite graphs we express the graphical Stirling number as a convolution of classical Stirling numbers across the partite classes, and we recover the known factorization of the graphical Bell number as a product of classical Bell numbers. For the matching-deleted graph we show that its graphical Bell number is a binomial convolution of squared Bell numbers, which we identify as a moment of a product of two independent Poisson random variables with unit mean. This representation yields log-convexity of the sequence, a sharp exponential lower bound, a two-sided estimate, and a Laplace-transform identity. For the Mycielskian of a star, a decomposition according to the block containing the original center vertex, together with Vandermonde’s convolution and a Stirling recurrence, gives a single-sum closed form for the graphical Stirling numbers, from which two explicit evaluations follow. Several resulting integer sequences appear in the OEIS, and one Bell-number sequence appears not to be currently recorded there.