Degree of quotient graph of a regular graph

130 Views Asked by At

What can we say about the degree of a quotient of a regular graph? Intuitively, I think the situation may get arbitrarily bad. Specifically, I am looking for an example of an infinite family of $k$-regular graphs $(X_n)$, and a family $(Y_n)$ where $Y_n$ is a quotient of $X_n$, and the maximal degree $\Delta(Y_n)$ is unbounded.

The reason I am interested in this, is that I read in various references that quotients of expanding graphs are expanding graphs. Although it is easy to check that quotients of expanding graphs satisfy the expanding condition for the same constant, it is not clear to me why when taking quotients of an infinite family of expanders the degree should be bounded. In all instances where I have seen this fact to be applied, it turns out that it is, but I was wondering if this is a general fact or not.

Edit: I am especially interested in quotients where all the sets of the partition have the same size.

1

There are 1 best solutions below

0
On BEST ANSWER

If the partition of $X_n$ we use to get $Y_n$ has bounded parts - e.g., each part has size at most $t$ - then $\Delta(Y_n) \le t \cdot \Delta(X_n) = tk$, since each part can have at most $tk$ edges out of it.

If the sizes of the parts can be large, then this inequality is not helpful, and $\Delta(Y_n)$ may be unbounded. For an extreme example of this, let $X_n$ be an $n \times n$ grid graph, wrapping around at the sides: a $4$-regular graph with $n^2$ vertices. Put vertex $(i,j)$ with $0 \le i,j < n$ into part $(i + \frac{j(j+1)}{2} \bmod n)$ of the partition, and quotient by this partition to create $Y_n$.

This is an equitable partition into $n$ parts of size $n$, since for a fixed $j$, the vertices $(0,j), (1,j), \dots, (n-1,j)$ are in $n$ different parts. However, there are edges between any two parts of the partition: to find an edge between parts $p$ and $q$ with $p<q$, let $j = q-p-1 \bmod n$, and choose $i$ such that $i + \frac{j(j+1)}{2} \equiv p \pmod n$. Then $(i,j)$ is in part $p$ and $(i,j+1)$ is in part $q$.

So in this example, $Y_n$ is the complete graph $K_n$, and $\Delta(Y_n)$ is definitely unbounded.