Search

The median of a graph consists of those vertices which minimize the average distance to all other vertices. It plays an important role in optimization scenarios like facility location problems. Sierpinski graphs are the state graphs of the Switching Tower of Hanoi problem, a variant of the Tower of Hanoi game. They also provide optimum models for interconnection networks. In this study, we present our observations on the median of Sierpinski graphs. We conjecture that the number of median vertices in S 3 n is always 12, if n ≥ 3 , and that they lie around the inner ring of the standard drawing.

Sierpinski triangle graphs S n have often been mistaken for Sierpinski graphs S 3 n . Whereas the latter’s metric properties are by now well understood, the former graphs were mostly just considered as a pictorial representation of approximations to the Sierpinski triangle fractal. Therefore, we present here a new labeling for them which shows the relation, but also the differences to the more famous Sierpinski graphs proper. On the base of this labeling we describe an algorithm to obtain individual distances between vertices. This type of algorithm can then be extended to base- p Sierpinski triangle graphs S p n which are related to the class of classical Sierpinski graphs S p n , p ≥ 2 . Some of the metric properties of S p n can now be investigated for S p n as well; e.g., we characterize center and periphery of S p n .

Consider a variant of the famous Tower of Hanoi problem where moves of the discs are allowed along the edges of a connected simple graph D whose vertices represent the vertical pegs of the puzzle. The task is to transfer a tower of n ∈ N discs from one peg to another according to the well-known rules of the classical game corresponding to D ≅ K 3 . Apart from its recreational appeal, the problem brings about fascinating integer sequences engendered by the respective minimum number of moves, i.e. the distance in the canonical metric of the state graph H D n . We construct an algorithm which solves the task for all cases but the exceptional instance of the Linear Tower of Hanoi (i.e. where D is a path graph) in which the transfer is between the two end vertices of D . Optimality of this algorithm is claimed in our central conjecture which is supported by large-scale computational explorations.

This is the amazing story of an innocent looking mathematical puzzle turning into a serious research topic in graph theory, integer sequences, and algorithms. The Tower of Hanoi and The Reve's Puzzle of Lucas and Dudeney, respectively, induced a wealth of interesting mathematical and algorithmic challenges over more than a century. Although some part of the most intriguing question, the Frame-Stewart Conjecture, has recently been solved, several of the original tasks posed by Dudeney remained intractable. We present the history and theory of these questions and a computational approach which allowed us to solve a 104 years old problem of Dudeney, namely the proof of minimality of an algorithm producing paths between perfect states of the Tower of Hanoi with 5 pegs and 20 discs. Many questions about the metric properties of Hanoi graphs remain open, however, and have to be treated by analytical and computational methods in the future.

In Chapter 6 we have introduced the concept of a TH variant and presented several such puzzles: the Black and white TH, additional variants with colored discs, and the Bottleneck TH. We continued in Chapter 7 where the TL (and its variations) were treated in detail. In this chapter we turn our attention to the TH with resticted disc moves. These restrictions may consist of disallowing moves between certain pegs or either of imposing a direction of moves. (Note that Variants A, B and C of the Black and white TH introduced on p. 288ff are also defined prohibiting certain moves depending on disc colors.) The variants are pretty well understood if only three pegs are present as we will see in Section 8.2. It will turn out that for these, exactly five, puzzles a unified algorithm to generate their, respectively unique, optimal solutions can be constructed. To make things precise, we will discuss solvability of a variant in Section 8.1.

In his early descriptions of the TH (see, e.g., [83]), Lucas pointed out the possibility of starting with an arbitrary distribution of n discs among three pegs, i.e. allowing for discs lying on a smaller one. The task is again to arrive at a perfect state on a preassigned peg, while still obeying the divine rule. This, in Lucas’s opinion [82], will vary the conditions of the problem of the TH “to infinity”. We may even go beyond by prescribing an arbitrary, albeit regular, state as the goal. We will approach this problem in the next section and round this chapter off with a section on an algorithmic solution to Lucas’s second problem.

International audience; Providing the example of a disc whose number of moves performed in a minimal solution for the Tower of Hanoi problem is not a power of two, we show that the argument given in an article by R. Demontis in this journal is false and the method incapable to solve the Frame-Stewart Conjecture on the Tower of Hanoi with more than three pegs.

We determine the eccentricity of an arbitrary vertex, the average eccentricity and its standard deviation for all Sierpinski 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.

In this paper, we study the power domination problem in Knodel graphs W-Delta,W-2 nu and Hanoi graphs H-p(n). We determine the power domination number of W-3,W-2 nu and provide an upper bound for the power domination number of W-r+1,W-2r+1 for r >= 3. We also compute the k-power domination number and the k-propagation radius of H-p(2).

The “Tower of London” puzzle was adapted to tablet PCs to be used as a clinical bedside test. “Iso-problems”, a specific class of problems, require identical moves but ball colours are permuted. Thus difficulty is the same even if the appearance is different. We wanted to determine the impact of these as yet little-studied tasks and hypothesised that there may be a learning effect specific to them (the “iso-effect”). We interspersed a set of six iso-problems within one selection of 22 tasks and analysed problem solving by 81 healthy adults (mean age 41.6 years). Participants showed learning across iso-problems (less time, fewer moves, increasingly efficient solutions). This effect was distinct from general learning, as was obvious from comparison with a series of non-isomorphic tasks. However, participants seem not to be aware of solving such problems. This “iso-effect” may be related to implicit memory, a domain that so far has not been assessed using the Tower of London.

We propose a mathematical model for the Towers of Hanoi and London based on state graphs. The analysis of this model allows to address questions like equivalence of puzzles, difficulty of tasks and optimality of solutions using topological, metric and symmetry properties of the corresponding graphs. The mathematical model serves as a base for a computer program to administer tower puzzles in a variety of psychological test situations. It is suitable for bedside use and is equipped with numerous devices for post-processing of recorded data. Among these features is the graphical representation of the projection of the path taken by a test person onto the state graph.

In contrast to the widespread interest in the Frame-Stewart conjecture (FSC) about the optimal number of moves in the classical Tower of Hanoi task with more than three pegs, this is the first study of the question of investigating shortest paths in Hanoi graphs $H_p^n$ in a more general setting. Here $p$ stands for the number of pegs and $n$ for the number of discs in the Tower of Hanoi interpretation of these graphs. The analysis depends crucially on the number of largest disc moves (LDMs). The patterns of these LDMs will be coded as binary strings of length $p-1$ assigned to each pair of starting and goal states individually. This will be approached both analytically and numerically. The main theoretical achievement is the existence, at least for all $n\geqslant p(p-2)$, of optimal paths where $p-1$ LDMs are necessary. Numerical results, obtained by an algorithm based on a modified breadth-first search making use of symmetries of the graphs, lead to a couple of conjectures about some cases not covered by our ascertained results. These, in turn, may shed some light on the notoriously open FSC.

Since it became clear that the band structure of the spectrum of periodic Sturm-Liouville operatorst = - (d2/dr2) +q(r) does not survive a spherically symmetric extension to Schrodinger operatorsT =- Δ+ V with V(x) =q(¦x¦) for x ∈ ℝd,d ∈ ℕ 1, a wealth of detailed information about the spectrum of such operators has been acquired. The observation of eigenvalues embedded in the essential spectrum [μ0, ∞[ ofT with exponentially decaying eigenfunctions provided evidence for the existence of intervals of dense point spectrum, eventually proved by spherical separation into perturbed Sturm-Liouville operatorst c = t +(c/r 2). Subsequently, a numerical approach was employed to investigate the distribution of eigenvalues ofT more closely. An eigenvalue was discovered below the essential spectrum in the cased = 2, and it turned out that there are in fact infinitely many, accumulating at μ0. Moreover, a method based on oscillation theory made it possible to count eigenvalues oft c contributing to an interval of dense point spectrum ofT. We gained evidence that an asymptotic formula, valid forc → ∞, does in fact produce correct numbers even for small values of the coupling constant, such that a rather precise picture of the spectrum of radially periodic Schrodinger operators has now been obtained.

Hanoi graphs are the state graphs for Tower of Hanoi problems with three or more pegs. We prove hamiltonicity and present a complete analysis of planarity of these graphs.

Cantor’s proof of this result [2, §2] makes use of nested intervals, but today a proof based on another ingenious idea of Cantor is more popular, namely the diagonal method, which he introduced in 1891 to prove the uncountability of 2 [3]. However, Cantor himself did not employ diagonalization directly in the proof of uncountability of R, but gave a rather intricate derivation of ∣ ∣2 ∣ ∣ = |R| in [4, §4]. The origin of the now standard argument for

In Chapter 6 we have introduced the concept of a TH variant and presented several such puzzles: the BWTH, additional variants with colored discs, and the BTH. We continued in Chapter 7 where the TL (and its variations) were treated in detail. In this chapter we turn our attention to the TH with oriented disc moves.