In this paper we give a non-trivial family of degree sequences that are not $P$-stable and the switch Markov chain is still rapidly mixing on them. This family has an intimate connection to Tyshkevich-decompositions and strong stability as well.
We show that the space of rooted tree-based phylogenetic networks is connected under rooted nearest-neighbour interchange (rNNI) moves and distance-1 tail moves.
Bootstrap percolation is a class of cellular automata with random initial state. Two-dimensional bootstrap percolation models have three universality classes, the most studied being the 'critical' one. For this class the scaling of the quantity of …
Since 1997 a considerable effort has been spent on the study of the **swap** (switch) Markov chains on graphic degree sequences. All of these results assume some kind of regularity in the corresponding degree sequences. Recently, Greenhill and …
We study the problem of guarding orthogonal art galleries with horizontal mobile guards (alternatively, vertical) and point guards, using "rectangular vision". We prove a sharp bound on the minimum number of point guards required to cover the gallery …
Various disorders including pseudoxanthoma elasticum (PXE) and generalized arterial calcification of infancy (GACI), which are caused by inactivating mutations in *ABCC6* and *ENPP1*, respectively, present with extensive tissue calcification due to …
We investigate the terminal-pairability problem in the case when the base graph is a complete bipartite graph, and the demand graph is a (not necessarily bipartite) multigraph on the same vertex set. In computer science, this problem is known as the …
We investigate the terminal-pairability problem in the case when the base graph is a complete bipartite graph, and the demand graph is also bipartite with the same color classes. We improve the lower bound on maximum value of $\Delta(D)$ which still …
We affirmatively answer and generalize the question of Kubicka, Kubicki and Lehel (1999) concerning the path-pairability of high-dimensional complete grid graphs. As an intriguing by-product of our result we significantly improve the estimate of the …
We investigate terminal-pairability properties of complete graphs and improve the known bounds in two open problems. We prove that the complete graph $K_n$ on $n$ vertices is terminal-pairable if the maximum degree $\Delta$ of the corresponding …