¿Gráfico de expansión no-regular?

Question

La respuesta a la siguiente pregunta podría ser trivial.

Expansor gráfico es dispersa gráfico que tiene fuertes propiedades de conectividad.

En "Expander las Familias y los Grafos de Cayley" Libro o aquí usted encontrará la siguiente definición de expansor gráfico:

Mi pregunta:

Podemos definir el expansor de la gráfica para los gráficos?

Que es, en lugar de d-regular, (X_n) será la secuencia de gráfico donde $\forall n$ tenemos $\Delta(X_n)\leq c$, para algunas de las $c\in \mathbb{N}^+$ ( tenga en cuenta que $\Delta(X_n)$ es el grado máximo de la gráfica de $(X_n)$).

Cualquier ayuda será muy útil!

Answer 1

Por fin he llegado a una respuesta para mi pregunta.

Y la respuesta es ¡sí! Podemos definir el expansor de la familia de los no-regular el caso.

La definición más común de los extensores de es $d$-regular los gráficos, que es tal vez porque una de las dos razones siguientes:

1-la Mayoría de las construyeron los gráficos de expansión son grafos de Cayley( regular)

2-ser capaz de utilizar Cheeger de las desigualdades.

La definición original de expansores se indica en los Recientes Progresos En la Topología General III (definición 9.2).

Definición 9.2

Un finito gráfico de $G$ $(k, ε)$-expansor si cada vértice de $G$ tiene valencia en la mayoría de las $k$, e $h(G) \geq ε > 0$.

Una secuencia de grafos finitos $\{G_i\}$ se denomina extensor de la secuencia si $|G_i| \rightarrow \infty$ y existe $k, ε$ de manera tal que cada una de las $G_i$ $(k, ε)$- expansor.