On dispersability of some circulant graphs

arXiv2109.10163MaRDI QIDQ6505186FDOQ6505186

Authors: Paul C. Kainen, Samuel S. Joslin, Shannon Overbay 

Abstract: The {it matching book thickness} $mbt(G)$ of a graph $G$ is the least number of pages in a book embedding such that each page is a matching; $G$ is {it dispersable} if $mbt(G)=Delta(G)$, where $Delta$ is the maximum degree. A graph $G$ is {it nearly dispersable} if $mbt(G)=1+Delta(G)$. Recently, Alam et al disproved the 40-year-old Bernhart-Kainen conjecture that all regular bipartite graphs are dispersable, motivating further work on dispersability. We show that most circulant graphs $G$ with jump lengths not exceeding $3$ are dispersable or nearly dispersable. Similar results are obtained for arbitrarily large jump lengths, obtained by rearranging repeated copies of a complete or bipartite complete graph.

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

This page was built for publication: On dispersability of some circulant graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6505186)