Structure of spanning trees on the two-dimensional Sierpinski gasket

Shu-Chiuan Chang, Lung Chi Chen

Research output: Contribution to journalArticle

4 Citations (Scopus)

Abstract

Consider spanning trees on the two-dimensional Sierpinski gasket SG(n) where stage n is a non-negative integer. For any given vertex x of SG(n), we derive rigorously the probability distribution of the degree j ε f1; 2; 3; 4g at the vertex and its value in the infinite n limit. Adding up such probabilities of all the vertices divided by the number of vertices, we obtain the average probability distribution of the degree j. The corresponding limiting distribution Φj gives the average probability that a vertex is connected by 1, 2, 3 or 4 bond(s) among all the spanning tree configurations. They are rational numbers given as Φ1 = 10957=40464, Φ2 = 6626035=13636368, Φ3 = 2943139=13636368, Φ4 = 124895=4545456.

Original language English 151-176 26 Discrete Mathematics and Theoretical Computer Science 12 3 Published - 2010 Dec 6

Fingerprint

Spanning tree
Probability distributions
Probability Distribution
Vertex of a graph
Limiting Distribution
Non-negative
Configuration
Integer

All Science Journal Classification (ASJC) codes

• Theoretical Computer Science
• Computer Science(all)
• Discrete Mathematics and Combinatorics

Cite this

title = "Structure of spanning trees on the two-dimensional Sierpinski gasket",
abstract = "Consider spanning trees on the two-dimensional Sierpinski gasket SG(n) where stage n is a non-negative integer. For any given vertex x of SG(n), we derive rigorously the probability distribution of the degree j ε f1; 2; 3; 4g at the vertex and its value in the infinite n limit. Adding up such probabilities of all the vertices divided by the number of vertices, we obtain the average probability distribution of the degree j. The corresponding limiting distribution Φj gives the average probability that a vertex is connected by 1, 2, 3 or 4 bond(s) among all the spanning tree configurations. They are rational numbers given as Φ1 = 10957=40464, Φ2 = 6626035=13636368, Φ3 = 2943139=13636368, Φ4 = 124895=4545456.",
author = "Shu-Chiuan Chang and Chen, {Lung Chi}",
year = "2010",
month = "12",
day = "6",
language = "English",
volume = "12",
pages = "151--176",
journal = "Discrete Mathematics and Theoretical Computer Science",
issn = "1365-8050",
publisher = "Maison de l'informatique et des mathematiques discretes",
number = "3",

}

In: Discrete Mathematics and Theoretical Computer Science, Vol. 12, No. 3, 06.12.2010, p. 151-176.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Structure of spanning trees on the two-dimensional Sierpinski gasket

AU - Chang, Shu-Chiuan

AU - Chen, Lung Chi

PY - 2010/12/6

Y1 - 2010/12/6

N2 - Consider spanning trees on the two-dimensional Sierpinski gasket SG(n) where stage n is a non-negative integer. For any given vertex x of SG(n), we derive rigorously the probability distribution of the degree j ε f1; 2; 3; 4g at the vertex and its value in the infinite n limit. Adding up such probabilities of all the vertices divided by the number of vertices, we obtain the average probability distribution of the degree j. The corresponding limiting distribution Φj gives the average probability that a vertex is connected by 1, 2, 3 or 4 bond(s) among all the spanning tree configurations. They are rational numbers given as Φ1 = 10957=40464, Φ2 = 6626035=13636368, Φ3 = 2943139=13636368, Φ4 = 124895=4545456.

AB - Consider spanning trees on the two-dimensional Sierpinski gasket SG(n) where stage n is a non-negative integer. For any given vertex x of SG(n), we derive rigorously the probability distribution of the degree j ε f1; 2; 3; 4g at the vertex and its value in the infinite n limit. Adding up such probabilities of all the vertices divided by the number of vertices, we obtain the average probability distribution of the degree j. The corresponding limiting distribution Φj gives the average probability that a vertex is connected by 1, 2, 3 or 4 bond(s) among all the spanning tree configurations. They are rational numbers given as Φ1 = 10957=40464, Φ2 = 6626035=13636368, Φ3 = 2943139=13636368, Φ4 = 124895=4545456.

UR - http://www.scopus.com/inward/record.url?scp=78649625030&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78649625030&partnerID=8YFLogxK

M3 - Article

VL - 12

SP - 151

EP - 176

JO - Discrete Mathematics and Theoretical Computer Science

JF - Discrete Mathematics and Theoretical Computer Science

SN - 1365-8050

IS - 3

ER -