On the treewidth of Hanoi graphs Eppstein, David; Frishberg, Daniel; Maxwell, William
Theoretical computer science,
03/2022, Letnik:
906
Journal Article
Recenzirano
Odprti dostop
•Analysis of Hanoi graphs, which arise from the classic Tower of Hanoi puzzle.•Nearly tight upper and lower bounds on the treewidth of these graphs.•An extension of the Kneser graph and a proof that ...its treewidth is nearly linear.•A new proof of a known lower bound on the treewidth of tensor products of graphs.
The objective of the well-known Tower of Hanoi puzzle is to move a set of discs one at a time from one of a set of pegs to another, while keeping the discs sorted on each peg. We propose an adversarial variation in which the first player forbids a set of states in the puzzle, and the second player must then convert one randomly-selected state to another without passing through forbidden states. Analyzing this version raises the question of the treewidth of Hanoi graphs. We find this number exactly for three-peg puzzles and provide nearly-tight asymptotic bounds for larger numbers of pegs.
The Apollonian networks display the remarkable power-law and small-world properties as observed in most realistic networked systems. Their dual graphs are extended Tower of Hanoi graphs, which are ...obtained from the Tower of Hanoi graphs by adding a special vertex linked to all its three extreme vertices. In this paper, we study analytically maximum matchings and minimum dominating sets in Apollonian networks and their dual graphs, both of which have found vast applications in various fields, e.g. structural controllability of complex networks. For both networks, we determine their matching number, domination number, the number of maximum matchings, as well as the number of minimum dominating sets.
The resistance distance between two vertices of a simple connected graph
G
is equal to the resistance between two equivalent points on an electrical network, constructed to correspond to
G
, with ...each edge being replaced by a unit resistor. In this study, we apply the principle of substitution to three-towers Hanoi graph to procure an equivalent network that enables us to only use the series and parallel principles and the delta-wye transformation to acquire the some two-vertex resistance distances of three-towers Hanoi graph.
In this paper, we study the power domination problem in Knödel graphs
and Hanoi graphs
. We determine the power domination number of
and provide an upper bound for the power domination number of
for
...≥ 3. We also compute the
-power domination number and the
-propagation radius of
.
The number of spanning trees of a graph is an important invariant related to topological and dynamic properties of the graph, such as its reliability, communication aspects, synchronization, and so ...on. However, the practical enumeration of spanning trees and the study of their properties remain a challenge, particularly for large networks. In this paper, we study the number and degree distribution of the spanning trees in the Hanoi graph. We first establish recursion relations between the number of spanning trees and other spanning subgraphs of the Hanoi graph, from which we find an exact analytical expression for the number of spanning trees of the n-disc Hanoi graph. This result allows the calculation of the spanning tree entropy which is then compared with those for other graphs with the same average degree. Then, we introduce a vertex labeling which allows to find, for each vertex of the graph, its degree distribution among all possible spanning trees.
Anti-Ramsey Number of Hanoi Graphs Gorgol, Izolda; Lechowska, Anna
Discussiones Mathematicae. Graph Theory,
01/2019, Letnik:
39, Številka:
1
Journal Article
Recenzirano
Odprti dostop
Let ar(G,H) be the largest number of colors such that there exists an edge coloring of G with ar(G,H) colors such that each subgraph isomorphic to H has at least two edges in the same color. We call ...ar(G,H) the anti- Ramsey number for a pair of graphs (G,H). This notion was introduced by Erdős, Simonovits and Sόs in 1973 and studied in numerous papers. Hanoi graphs were introduced by Scorer, Grundy and Smith in 1944 as the model of the well known Tower of Hanoi puzzle. In the paper we study the anti-Ramsey number of Hanoi graphs and consider them both as the graph G and H. Among others we present the exact value of the anti-Ramsey number in case when both graphs are constructed for the same number of pegs.
Detour Number of 1-Fault Connected Graphs Raghu, T. Venkata; Sundara Rajan, R.; Ramesh Babu, A. ...
Fundamenta informaticae,
01/2020, Letnik:
172, Številka:
1
Journal Article
Recenzirano
A subset S of a connected graph G of order n is called a detour set of G if for every vertex x in G there exist vertices u; v in S such that x lie on a u – v detour path. The detour number dn(G) of a ...graph G is the minimum cardinality of a detour set. In this paper we compute the detour number of certain 1-fault connected planar graphs.
We study the number of dimer–monomers
M
d
(
n
)
on the Hanoi graphs
H
d
(
n
)
at stage
n
with dimension
d
equal to 3 and 4. The entropy per site is defined as
z
H
d
=
lim
v
→
∞
ln
M
d
(
n
)
/
v
, ...where
v
is the number of vertices on
H
d
(
n
)
. We obtain the lower and upper bounds of the entropy per site, and the convergence of these bounds approaches to zero rapidly when the calculated stage increases. The numerical values of
z
H
d
for
d
=
3
,
4
are evaluated to more than a hundred digits correct. Using the results with
d
less than or equal to 4, we predict the general form of the lower and upper bounds for
z
H
d
with arbitrary
d
.
Hanoi graphs
H
p
n
model the Tower of Hanoi game with
p
pegs and
n
discs. Sierpinski graphs
S
p
n
arose in investigations of universal topological spaces and have meanwhile been studied extensively. ...It is proved that
S
p
n
embeds as a spanning subgraph into
H
p
n
if and only if
p
is odd or, trivially, if
n
= 1.
PDF
