Counting Water Cells in Bargraphs of Compositions and Set Partitions

If G is a graph and n a positive integer, then the generalized Sierpi´nski graph Sⁿ_G is a fractal-like graph that uses G as a building block. The construction of Sⁿ_G generalizes the classical Sierpi´nski graphs Sⁿ_p , where the role of G is layed by the complete graph K_p. An explicit formula for the number of connected components in Sⁿ_G is given and it is proved that the (edge-)connectivity of Sⁿ_G equals the (edge-)connectivity of G. It is demonstrated that SnG contains a 1-factor if and only if G contains a 1-factor. Hamiltonicity of generalized Sierpi´nski graphs is also discussed.