Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSpectra of three-peg Hanoi towers graphs
64
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We consider the relationship between the Laplacians on two sequences of planar graphs, one from the theory of self-similar groups and one from analysis on fractals. By establishing a spectral decimation map between these sequences we give an elementary calculation of the spectrum of the former, which was first computed by Grigorchuk and v{S}uni{c}. Our method also gives a full description of the eigenfunctions.
rate research
Read More
The objective of the well-known Towers of Hanoi puzzle is to move a set of disks one at a time from one of a set of pegs to another, while keeping the disks 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.
We first enumerate a generalization of domino towers that was proposed by Tricia M. Brown (J. Integer Seq. 20 (2017)), which we call S-omino towers. We establish equations that the generating function must satisfy and then apply the Lagrange inversion formula to find a closed formula for the number of towers. We also show a connection to generalized Dyck paths and provide an explicit bijection. Finally, we consider the set of row-convex k-omino towers, introduced by Brown, and calculate an exact generating function.
Given two graphs, a backbone and a finger, a comb product is a new graph obtained by grafting a copy of the finger into each vertex of the backbone. We study the comb graphs in the case when both components are the paths of order $n$ and $k$, respectively, as well as the above comb graphs with an infinite ray attached to some of their vertices. A detailed spectral analysis is carried out in both situations.
The emph{simplicial rook graph} SR(d,n) is the graph whose vertices are the lattice points in the $n$th dilate of the standard simplex in $mathbb{R}^d$, with two vertices adjacent if they differ in exactly two coordinates. We prove that the adjacency and Laplacian matrices of SR(3,n) have integral spectrum for every $n$. The proof proceeds by calculating an explicit eigenbasis. We conjecture that SR(d,n) is integral for all $d$ and $n$, and present evidence in support of this conjecture. For $n<binom{d}{2}$, the evidence indicates that the smallest eigenvalue of the adjacency matrix is $-n$, and that the corresponding eigenspace has dimension given by the Mahonian numbers, which enumerate permutations by number of
We study the Laplacian spectrum of token graphs, also called symmetric powers of graphs. The $k$-token graph $F_k(G)$ of a graph $G$ is the graph whose vertices are the $k$-subsets of vertices from $G$, two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in $G$. In this paper, we give a relationship between the Laplacian spectra of any two token graphs of a given graph. In particular, we show that, for any integers $h$ and $k$ such that $1le hle kle frac{n}{2}$, the Laplacian spectrum of $F_h(G)$ is contained in the Laplacian spectrum of $F_k(G)$. We also show that the double odd graphs and doubled Johnson graphs can be obtained as token graphs of the complete graph $K_n$ and the star $S_{n}=K_{1,n-1}$, respectively. Besides, we obtain a relationship between the spectra of the $k$-token graph of $G$ and the $k$-token graph of its complement $overline{G}$. This generalizes a well-known property for Laplacian eigenvalues of graphs to token graphs. Finally, the double odd graphs and doubled Johnson graphs provide two infinite families, together with some others, in which the algebraic connectivities of the original graph and its token graph coincide. Moreover, we conjecture that this is the case for any graph $G$ and its token graph.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
