Let $G$ be a connected graph embedded in the plane with all edges straight segments. For $\alpha \in (0,\pi)$, define an $\alpha$-path as a path in $G$ with all turns at vertices within $[-\alpha,\alpha]$. That is, if you walked along the path, you would twist no more than $\pm \alpha$ at each vertex of the path. Define an $\alpha$-kernel as a set of vertices of $G$ from which every other vertex of $G$ is reachable by an $\alpha$-path. In a sense, $G$ can be "seen" from the kernel, with "lines of sight" crooked $\alpha$-paths. Finally, define $\mbox{ker}(\overline{G},\alpha)$ as the cardinality of the smallest $\alpha$-kernel for a particular embedding $\overline{G}$ of $G$. I'll give some examples before asking a question.

  • For $G=K_n$ the complete graph on $n$ vertices, $\mbox{ker}(\overline{K_n},\alpha)=1$.

  • For $G=P_n$ the path on $n$ vertices, for any $\alpha < \pi$, there is a "squashed" zigzag embedding $\overline{P_n}$ with $\mbox{ker}(\overline{P_n},\alpha)=\lfloor n/2 \rfloor$.

  • For $G=K_{n,n}$ the complete bipartite graph, for any $\alpha < \pi$, there is an embedding $\overline{K_{n,n}}$ with $\mbox{ker}(\overline{K_{n,n}},\alpha)=2$.

My question is, roughly, are there small-diameter $G$ with embeddings that force large $\alpha$-kernels? Note above that the diameters of $K_n$ and $K_{n,n}$ are $1$ and $2$ respectively, and the diameter of $P_n$ is $n-1$. Here is an attempt to phrase the question more formally:

Is there a class of graphs $G_n$ on $n$ vertices, each of diameter $\le d$, such that, for any $\alpha < \pi$, there are embeddings $\overline{G_n}$ with $\mbox{ker}(\overline{G_n},\alpha)$ growing monotonically with $n$?

Here $d$ is a constant independent of $n$. Again, informally: Can a large kernel be forced without concomitant increase in diameter?


Consider the $n$-dimensional affine space over a finite field with $q$ elements ($n\geq 2$ for connectivity reasons). Let $P$ be the set of points in it, $L$ be the set of lines, and $G_n$ be the bipartite graph of incidence of $P$ and $L$. Then any two points are connected with a path of length 2, so the diameter of the graph is 4, and it has $q^n+\frac{q^{n-1}(q^n-1)}{q-1}$ vertices.

On the other hand, if you embed this graph in a way you did with the complete bipartite graph, then $\mathop{ker}$ will be the smallest size of the dominating set $D$ which should have at least $\frac{q^n-1}{q-1}$ elements (this estimate is not sharp). Indeed, if $D$ contains all the points then it contains even at least $q^n$ vertices. Otherwise, take any point $p$ which is not in $D$ and consider all the $\frac{q^n-1}{q-1}$ lines passing through it. Each of them should either be in $D$, or contain a point from $D$, and all these points should be distinct.

  • $\begingroup$ Thank you, Ilya! I will have to construct one of these graphs (with which I am unfamiliar) to more fully understand your idea... $\endgroup$ – Joseph O'Rourke Oct 26 '14 at 13:25

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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