Number of connected spanning subgraphs on the Sierpiński gasket. (English) Zbl 1196.05040

Chang, Shu-Chiuan; Chen, Lung-Chi

Discrete Math. Theor. Comput. Sci. 11, No. 1, 55-78 (2009).

Summary: We study the number of connected spanning subgraphs \(f_{d,b}(n)\) on the generalized Sierpinski gasket \(SG_{d,b}(n)\) at stage n with dimension d equal to two, three and four for \(b=2\), and layer \(b\) equal to three and four for \(d=2\). The upper and lower bounds for the asymptotic growth constant, defined as \(zSG_{d,b}=lim_{v \to \infty } \ln f_{d,b}(n)/v\) where v is the number of vertices, on \(SG_{2,b}(n)\) with \(b=2,3,4\) are derived in terms of the results at a certain stage. The numerical values of \(zSG_{d,b}\) are obtained.

MSC:

05C30

Enumeration in graph theory

Keywords:

connected spanning subgraphs; Sierpiński gasket; recursion relations; asymptotic growth constant