Coloring Hanoi and Sierpiński graphs

It is shown that all Hanoi and Sierpiński graphs are in edge- and total coloring class 1, except those isomorphic to a complete graph of odd or even order, respectively. New proofs for their classification with respect to planarity are also given.     

Packing coloring of Sierpiński-type graphs

The packing chromatic number \(\chi _{\rho }(G)\) of a graph G is the smallest integer k such that the vertex set of G can be partitioned into sets \(V_i\), \(i\in \{1,\ldots ,k\}\), where each \(V_i\) is an i-packing. In this paper, we consider the packing chromatic number of several families of Sierpiński-type graphs. While it is known that this number is bounded from above by 8 in the family of Sierpiński graphs with base 3, we prove that it is unbounded in the families of Sierpiński graphs with bases greater than 3. On the other hand, we prove that the packing chromatic number in the family of Sierpiński triangle graphs \(ST^n_3\) is bounded from above by 31. Furthermore, we establish or provide bounds for the packing chromatic numbers of generalized Sierpiński graphs \(S^n_G\) with respect to all connected graphs G of order 4.     

Distances in Sierpiński graphs and on the Sierpiński gasket

The well known planar fractal called the Sierpiński gasket can be defined with the help of a related sequence of graphs {G _n } _{n ≥ 0}, where G _n is the n-th Sierpiński graph, embedded in the Euclidean plane. In the present paper we prove geometric criteria that allow us to decide, whether a shortest path between two distinct vertices x and y in G _n , that lie in two neighbouring elementary triangles (of the same level), goes through the common vertex of the triangles or through two distinct vertices (both distinct from the common vertex) of those triangles. We also show criteria for the analogous problem on the planar Sierpiński gasket and in the 3-dimensional Euclidean space.     

Sierpiński graphs as spanning subgraphs of Hanoi graphs

Hanoi graphs H _p ⁿ model the Tower of Hanoi game with p pegs and n discs. Sierpinski graphs S _p ⁿ arose in investigations of universal topological spaces and have meanwhile been studied extensively. It is proved that S _p ⁿ embeds as a spanning subgraph into H _p ⁿ if and only if p is odd or, trivially, if n = 1.     

New results on variants of covering codes in Sierpiński graphs

In this paper we study identifying codes, locating-dominating codes, and total-dominating codes in Sierpiński graphs. We compute the minimum size of such codes in Sierpiński graphs.     

On a problem of Sierpiński,Ⅱ

For any integer s≥ 2, let μsbe the least integer so that every integer l μs is the sum of exactly s integers which are pairwise relatively prime. In 1964, Sierpi′nski asked for the determination of μs. Let pibe the i-th prime and let μs= p2 + p3 + + ps+1+ cs. Recently, the authors solved this problem. In particular,we have(1) cs=-2 if and only if s = 2;(2) the set of integers s with cs= 1100 has asymptotic density one;(3) cs∈ A for all s ≥ 3, where A is an explicit set with A ■[2, 1100] and |A| = 125. In this paper, we prove that,(1) for every a ∈ A, there exists an index s with cs= a;(2) under Dickson's conjecture, for every a ∈ A,there are infinitely many s with cs= a. We also point out that recent progress on small gaps between primes can be applied to this problem.     

On two theorems of Sierpiński

A theorem of Sierpiński says that every infinite set Q of reals contains an infinite number of disjoint subsets whose outer Lebesgue measure is the same as that of Q. He also has a similar theorem involving Baire property. We give a general theorem of this type and its corollaries, strengthening classical results.     

The Linear t-Colorings of Sierpiński-Like Graphs

A proper t-coloring of a graph G is a mapping ${\varphi: V(G) \rightarrow [1, t]}$ such that ${\varphi(u) \neq \varphi(v)}$ if u and v are adjacent vertices, where t is a positive integer. The chromatic number of a graph G, denoted by ${\chi(G)}$ , is the minimum number of colors required in any proper coloring of G. A linear t-coloring of a graph is a proper t-coloring such that the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number of a graph G, denoted by ${lc(G)}$ , is the minimum t such that G has a linear t-coloring. In this paper, the linear t-colorings of Sierpiński-like graphs S(n, k), ${S^+(n, k)}$ and ${S^{++}(n, k)}$ are studied. It is obtained that ${lc(S(n, k))= \chi (S(n, k)) = k}$ for any positive integers n and k, ${lc(S^+(n, k)) = \chi(S^+(n, k)) = k}$ and ${lc(S^{++}(n, k)) = \chi(S^{++}(n, k)) = k}$ for any positive integers ${n \geq 2}$ and ${k \geq 3}$ . Furthermore, we have determined the number of paths and the length of each path in the subgraph induced by the union of any two color classes completely.     

The Average Eccentricity of Sierpiński Graphs

We determine the eccentricity of an arbitrary vertex, the average eccentricity and its standard deviation for all Sierpiński graphs ${S_p^n}$ . Special cases are the graphs ${S_2^{n}}$ , which are isomorphic to the state graphs of the Chinese Rings puzzle with n rings and the graphs ${S_3^{n}}$ isomorphic to the Hanoi graphs ${H_3^{n}}$ representing the Tower of Hanoi puzzle with 3 pegs and n discs.     

On dynamics of the Sierpiński carpet

We prove that the Sierpiński curve admits a homeomorphism with strong mixing properties. We also prove that the constructed example does not have Bowen's specification property.     

A geometric property of the Sierpiński carpet

The main aim of this paper is to find formulae for the computation of the geodesic metric on the Sierpí nski carpet. This is accomplished by introducing carpet coordinates. Subsequently we show the equivalence of the Euclidean and the geodesic metric on this fractal.     

Uniformization of Sierpiński carpets in the plane

Let S _i , i∈I, be a countable collection of Jordan curves in the extended complex plane \(\widehat{\mathbb{C}}\) that bound pairwise disjoint closed Jordan regions. If the Jordan curves are uniform quasicircles and are uniformly relatively separated, then there exists a quasiconformal map \(f\colon\widehat{\mathbb{C}}\rightarrow\widehat{\mathbb{C}}\) such that f(S _i ) is a round circle for all i∈I. This implies that every Sierpiński carpet in \(\widehat{\mathbb{C}}\) whose peripheral circles are uniformly relatively separated uniform quasicircles can be mapped to a round Sierpiński carpet by a quasisymmetric map.     

A topological characterization of the Sierpiński triangle

We present a topological characterization of the Sierpiński triangle. This answers question 58 from the Problem book of the Open Problem Seminar held at Charles University. In fact we give a characterization of the Apollonian gasket first. Consequently we show that any subcontinuum of the Apollonian gasket, whose boundary consists of three points, is homeomorphic to the Sierpiński triangle.     

Connected generalised Sierpiński carpets

Generalised Sierpiński carpets are planar sets that generalise the well-known Sierpiński carpet and are defined by means of sequences of patterns. We present necessary and sufficient conditions, under which generalised Sierpiński carpets are connected, with respect to Euclidean topology.     

Equidistribution and Brownian motion on the Sierpiński gasket

We introduce several concepts of discrepancy for sequences on the Sierpiski gasket. Furthermore a law of iterated logarithm for the discrepancy of trajectories of Brownian motion is proved. The main tools for this result are regularity properties of the heat kernel on the Sierpiski gasket. Some of the results can be generalized to arbitrary nested fractals in the sense of T. Lindstrøm.With 2 FiguresDedicated to Prof. Edmund Hlawka on the occasion of his 80^th birthdayThe authors are supported by the Austrian Science Foundation project Nr. P10223-PHY and by the Austrian-Italian scientific cooperation program project Nr. 39     

Packing Chromatic Number of Base-3 Sierpiński Graphs

The packing chromatic number \(\chi _{\rho }(G)\) of a graph G is the smallest integer k such that there exists a k-vertex coloring of G in which any two vertices receiving color i are at distance at least \(i+1\). Let \(S^n\) be the base-3 Sierpiński graph of dimension n. It is proved that \(\chi _{\rho }(S^1) = 3\), \(\chi _{\rho }(S^2) = 5\), \(\chi _{\rho }(S^3) = \chi _{\rho }(S^4) = 7\), and that \(8\le \chi _\rho (S^n) \le 9\) holds for any \(n\ge 5\).