15
$\begingroup$

Motivation. As I was travelling in the UK, I used a physical copy of the "A-Z Road Atlas BRITAIN" for getting around. I was impressed that whenever I wanted to go from the map segment shown on page 23, say (showing a part of the West Midlands), to the segment east of the one I was looking at, I only had to turn unexpectedly few pages. (For every page, the page showing the next part of the country South, East, West, or North, was indicated.) Which motivated the following concept.

Formalization. We regard any non-negative integer $n$ as an ordinal, so $n$ is the set of all its predecessors, i.e. $0 = \emptyset$, and $n = \{0,\ldots,n-1\}$ for any positive integer $n$.

Let $n$ be a positive integer, and let $G = (V,E)$ be a finite, simple, undirected graph with $|V| = n$. We define the "page-turning number" of $G$ by $$\pi(G) = \min\big\{\max\{|\varphi(v) - \varphi(w)|: \{v,w\}\in E\} \; : \; \varphi: V \to n \text{ is bijective}\}.$$ The intuition behind this is the following: we regard $\varphi\in S_n$ as a "page-number assignment" to the vertices of the graph and the $\max$ part denotes the largest number of pages we have to turn to get from one vertex to any adjacent one. We want to minimize on this $\max$ part.

Note that for the complete graph $K_n$ we have $\pi(K_n) = n-1$. It seems that the page-turning number might be loosely related to coloring, but it is certainly not the same. I would be grateful for hints to an official name for $\pi(G)$.

Question. For any positive integer $n$, let the $n\times n$-grid graph be given by $G_n = (n\times n, E)$ where $$E = \big\{\{(a,b), (c,d)\}: a,b,c,d \in n \text{ and } |a-c| + |b-d| = 1\big\}.$$ In terms of $n$, what is the value of $\pi(G_n)$?

$\endgroup$
1
  • 2
    $\begingroup$ Interesting question. We have an easy upper bound $\pi(G_n)\le n$, and I checked by brute force that equality holds for $2\le n \le 5$, so I suspect I always hold. $\endgroup$ Jul 30, 2022 at 23:20

1 Answer 1

17
$\begingroup$

The page-turning number of a graph $G$ is also known as the bandwidth of $G$ (https://en.wikipedia.org/wiki/Graph_bandwidth). The Wikipedia page also contains values of the bandwidth for some special graphs, including the $m\times n$ grid graph, in which case it is equal to $\min\{m,n\}$. This was proved by Jarmila Chvátalová: https://doi.org/10.1016/0012-365X(75)90039-4.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.