Monotone Neighborhoods

Why

Definition

The higher adjacency set or higher neighborhood of a vertex $v$ in an ordered undirected graph is all vertices in the neighborhood of $v$ whose index is greater the $v$. Similarly, the lower adjacency set or lower neighborhood of $v$ is all vertices in the neighborhood of $v$ whose index is less the $v$. We call these monotone neighborhoods.

The higher degree of a vertex is the size of the higher adjacency set and the lower degree of a vertex is the size of its lower adjacency set.

The closed monotone neighborhoods are the closed higher adjacency set, the higher adjacency set of $v$ union with the singleton $\set{v}$ and the closed lower adjacency set, the lower adjacency set of $v$ union with the singleton $\set{v}$.

Notation

We denote the higher neighborhood of $v$ by $\adjh(v)$ and the lower neighborhood by $\adjl(v)$.

Visualization

To help think about the monotone neighborhoods of the graph we visualize ordered graphs as triangular arrays with vertices along the diagonal and a bullet in row $i$ and column $j$ of the array if $i > j$ and the vertices $\sigma (i)$ and $\sigma (j)$ are adjacent.

An example is shown below for the ordered undirected graph in the figure (to understand this visualization, see Ordered Undirected Graphs) we use the

\[ \barray{ a & & & & \\ \bullet & c & & & \\ & \bullet & d & & \\ \bullet & & \bullet & b & \\ \bullet & \bullet & \bullet & \bullet & e } \]

In this array representation the higher and lower neighborhoods are easily identified. The indices of the elements of $\adjh(v)$ are the column indices of the entries in row $\inv{\sigma }(v)$ of the array. For example, $\inv{\sigma }(d) = 3$, and the only bullet entry in row three is $c$ so $\adjn(d) = \set{c}$. Likewise, $\adjn(c) = \set{a}$. And so on. Similalry, the indices of $\adjp(v)$ are the row indices of the entries in column $\inv{\sigma }(v)$. For example, $\inv{\sigma }(d)$ is $3$, and there are indices 4 and 5 corresponding to $b$ and $e$ so $\adjp(d) = \set{b, e}$. Likewise, $\adjp(c) = \set{d, e}$.

For this reason, we use the notation $\col(v)$ and $\row(v)$ for the closed upper and lower neighborhoods. So $\col(v) = \adjp(v) \union \set{v}$ and $\row(v) = \adjn(v) \union \set{v}$.

1. Future editions will include. This sheet is needed, for example, in discussing perfect elimination orderings. ↩︎