<p>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.</p>

<p>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.</p>

<p>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})$.</p>

CC BY-SA 3.0
2015-09-10T08:15:50.950Z
Thanks a lot. I had my doubts on whether the solution exists. This was great help.
sbzk
CC BY-SA 3.0
2015-09-15T15:38:13.267Z
Is this kind of information-theoretic argument used often in graph theory? (I don't recall seeing anything similar in standard undergrad textbooks.)
Radu GRIGore
CC BY-SA 3.0
2015-09-15T16:17:08.003Z
I'm not sure. A more sophisticated information theory argument is used in entropy compression (https://en.wikipedia.org/wiki/Entropy_compression) which has some graph-theoretic applications (e.g. to nonrepetitive coloring).
David Eppstein
CC BY-SA 3.0
2016-01-26T12:07:10.630Z
@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
CC BY-SA 3.0
2015-09-09T06:05:45.030Z
2015-09-09T15:54:45.527Z
2015-09-09T15:54:45.527Z
David Eppstein
<p>Given an Graph $G(V,E)$ with $|V|=n$ and $|E|=m$.</p>

<p>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})$. </p>

<p>Clearly any vertex with degree $&lt;\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.</p>

<p>Does such an ordering always exists?Can I find such an ordering efficiently?</p>

<p>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? </p>

<graph-theory><graph-algorithms>
Vertex ordering of an graph such that neighbourhood of each vertex occurs as bounded sequences
sbzk
# Vertex ordering of an graph such that neighbourhood of each vertex occurs as bounded sequences

(Asked by: username_0 on 2015-09-09)

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?

**Tags:** graph-theory, graph-algorithms

---

## 1 answers

### Answer by username_1 on 2015-09-09. Score: 6 | Accepted answer

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})$.

> **Comments:**
> **username_0**: Thanks a lot. I had my doubts on whether the solution exists. This was great help.  
> **username_2**: Is this kind of information-theoretic argument used often in graph theory? (I don't recall seeing anything similar in standard undergrad textbooks.)  
> **username_1**: I'm not sure. A more sophisticated information theory argument is used in entropy compression (https://en.wikipedia.org/wiki/Entropy_compression) which has some graph-theoretic applications (e.g. to nonrepetitive coloring).  
> **username_0**: @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?  

---

