Число подключенных (!) Подграфов экспоненциально?

Question

Я хочу показать, что для примерного семейства графов число связных подграфов растет с n.

Это легко показать для полного графа, поскольку полный граф имеет

N (N-1)/2 = N 2 над

края. Одно ребро находится либо в подграфе, либо нет. Таким образом, каждый подграф может быть перечислен с двоичным числом длиной

2^(п над 2)

и потому, что его полный граф, каждый подграф соединен.

Но предположим, например, что мы хотим показать, что число связанных подграфов в 3- или 4-регулярном графе растет также экспоненциально. Мы можем перечислить подграфы таким же образом. Но мы должны их исключить, потому что они не связаны.

Как мы можем это сделать? Есть ли способ отличить все связанные подграфы от не связанных?

Привет и спасибо за ваши мысли

Answer 1

Эта идея легко доказать, для некоторых семейств графов, в частности семейств графов с высоким «Edge-Connectivity» (см https://en.wikipedia.org/wiki/K-edge-connected_graph).

Для краевой связи, большей k, вы всегда можете выбрать любые k вершин для удаления и создать подключенный граф. Следовательно, вы получаете по крайней мере суммы суммирования (j = 1 .. k; E-choose-k), где E - общее количество ребер. Пусть k> (E/m) для некоторой постоянной m.

Тогда действительно число подграфов будет экспоненциально расти.