Sierpiński Gasket Graphs

The Sierpiński gasket graphs form one of the most studied examples of self-similar structures in graph theory [1]. They provide a discrete analogue of the classical Sierpiński triangle fractal, preserving both its recursive construction and its combinatorial richness.

The sequence begins with the complete graph on three vertices, $S_{1}$, and at each subsequent step, $S_{n+1}$ is obtained from $S_{n}$ by subdividing every triangular face.

New vertices are placed at the midpoints of its edges, and these are joined to form a smaller triangle inside. Repeating this process yields a hierarchy of graphs whose geometry captures the recursive pattern of the underlying fractal.


  Figure 1. The first 4 Sierpiński gasket graphs. Taken from Bunimovich et. al (2016) [2]

Given this sequence, what is the Global Clustering coefficient of $S_n$, for $n\geq2$ and its limit when $n \to \infty$?

$$\textbf{a)}\quad \frac{3^n}{3^{n}-2}, \quad 1$$
$$\textbf{b)}\quad \frac{4\cdot 3^{n-1}}{3^{n}-2}, \quad \frac{4}{3}$$
$$\textbf{c)}\quad \frac{4\cdot 3^{n-2}}{3^{n}-2}, \quad \frac{4}{9}$$
$$\textbf{d)}\quad \frac{4\cdot 3^{n-1}}{3^{n+1}-2}, \quad \frac{4}{9}$$
$$\textbf{e)} \quad \text{None of the above}$$

[1] Teguia, A. M., & Godbole, A. P. (2005). Sierpiński Gasket Graphs and Some of Their Properties. arXiv preprint math/0509259.
[2] Bunimovich, L., & Skums, P. (2016). Graph Hausdorff dimension, Kolmogorov complexity and construction of fractal graphs. arXiv preprint arXiv:1607.04703.

Original idea: Daniel Gardin

Comments

Post a Comment

Popular posts from this blog

Random Isolated Vertex

Consider a graph consisting of $n$ vertices in which each possible edge is included with probability $p = p(n)$ (a probability that explicitly depends on the size of the graph). This construction provides a probabilistic framework, as described by Gilbert [1], to study typical properties of graphs as $n$ increases. Denote this graph by $G(n, p)$, and consider $p(n) = \frac{1}{\sqrt{n}}$. What is the probability of finding an isolated vertex ( i.e.,  a vertex with no neighbours) in $G(n, p)$ as $n$ increases? Hint: Consider that the probability of finding an isolated vertex in a random graph with $n$ vertices is $P_\mathrm{isolated}(n) = (1-p)^{n-1}$. a) It increases with $n$, approaching $P_\mathrm{isolated}(n) = 1 - \frac{1}{n}$, converging to 1. b)  It increases with $n$, approaching $P_\mathrm{isolated}(n) = 1 - \frac{1}{\sqrt{n}}$, converging to 1. c) It decreases with $n$, approaching $P_\mathrm{isolated}(n) = \frac{\log n}{n}$, converging to 0. d)  It decr...
Read more