2

Efficiently sampling the realizations of bounded, irregular degree sequences of bipartite and directed graphs

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 …

Mobile vs. point guards

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 …

Oral administration of pyrophosphate inhibits connective tissue calcification

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 …

Terminal-Pairability in Complete Bipartite Graphs

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 …

Note on Terminal-Pairability in Complete Grid Graphs

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 …

Terminal-Pairability in Complete Graphs

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 …

Partitioning orthogonal polygons into at most 8-vertex pieces, with application to an art gallery theorem

We prove that every simply connected orthogonal polygon of $n$ vertices can be partitioned into $\lfloor\frac{3n+4}{16}\rfloor$ (simply connected) orthogonal polygons of at most 8 vertices. It yields a new and shorter proof of the theorem of A. …