scientific article; zbMATH DE number 19217

From MaRDI portal
Publication:3976648





[For the entire collection see Zbl 0734.00014.] Let \({\mathcal K}^{(m)}=\{K_ 1,K_ 2,\dots,K_ m\}\) be a collection of graphs \(K_ p\), with \(K_ p\), \(1\leq p\leq m\), being the complete graph with \(p\) vertices. Let \(G\) be a graph. A spanning subgraph \(S\) of \(G\) is called a \({\mathcal K}^{(m)}\)-factor of \(G\) if every component of \(S\) is isomorphic to some graph \(K_ p\in{\mathcal K}^{(m)}\). The authors pove that the number of \({\mathcal K}^{(m)}\)-factors of a complete graph \(K_ n\) is equal to \[ n!\sum_{b_ i\in\mathbb{N},\sum_ i ib_ i=n}{1\over b_ i!}\prod_{i\geq 2}{1\over(b_ i!)(i!)^{b_ i}}. \] Some results on the companion question about enumerating ideal subgraphs of \(G\) are presented and some applications to chromatic polynomials are indicated.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3976648)