# Vertex ordering of an graph such that neighbourhood of each vertex occurs as bounded sequences

Given an Graph $G(V,E)$ with $|V|=n$ and $|E|=m$.

The goal is to find a vertex ordereing $\sigma$ of V such that for each vertex $v\in V$, all neighbours of $v$ occur in $O(\sqrt{m})$ sequences in $\sigma$. That is if I locate all neighbours of $v$ in $\sigma$ I find all the neighbours present in chunks in $\sigma$, where number of such chunks is $O(\sqrt{m})$.

Clearly any vertex with degree $<\sqrt{m}$ does not voilate any vertex ordering as even if all its neighbours are separated in $\sigma$ the number of sequences/chunks cannot exceed $degree$ of the vertex.

Does such an ordering always exists?Can I find such an ordering efficiently?

Best case would be to find such an ordering in $O(m)$ time. Also is it possible for find such an ordering for smaller number of chunks/sequences?

So if I understand it correctly you want the neighbors of each vertex to form a small number of contiguous blocks of the ordering? Then no, you need a larger number of blocks than that.

Let's suppose we have a bipartite graph with a small number $k$ of (labeled) vertices on one side and $n$ on the other. Each edge from one side to the other can be present or absent independently of the others, so there are $kn$ bits of information required to specify the whole graph.

On the other hand, suppose you could find an ordering with the neighbors of each vertex forming at most $b$ blocks. Then you could specify the same graph by listing the ordering of the big side of the bipartition (representable in $\le n\log_2 n$ bits of information) and the positions and lengths of the blocks for each of the $k$ vertices on the small side of the bipartition ($\le 2bk\log_2 n$ bits). So to have enough information to specify the whole graph we need $$n\log_2 n+2bk\log_2 n\ge kn$$ or equivalently $$b\ge\frac{kn-n\log_2 n}{2k\log_2 n}$$ Setting $k=2\log_2 n$ gives $b=\Omega(n/\log n)$, significantly greater than $\sqrt m=\Theta((n\log n)^{1/2})$.

• Thanks a lot. I had my doubts on whether the solution exists. This was great help.
– sbzk
Sep 10, 2015 at 8:15
• Is this kind of information-theoretic argument used often in graph theory? (I don't recall seeing anything similar in standard undergrad textbooks.) Sep 15, 2015 at 15:38
• I'm not sure. A more sophisticated information theory argument is used in entropy compression (en.wikipedia.org/wiki/Entropy_compression) which has some graph-theoretic applications (e.g. to nonrepetitive coloring). Sep 15, 2015 at 16:17
• @DavidEppstein What if I want such a bound on number of such sequences with high probability and not exactly?. Does this example have some information theoretic aspects to restrict that as well?
– sbzk
Jan 26, 2016 at 12:07