связные помеченные графы

[rishelie]

Пусть $B_{n,k}$ - количество связных помеченных графов с $n$ вершинами и $k$ ребрами.
Существуют ли какие-нибудь утверждения о монотонности по $n$ и $k$ для этих чисел?
Всегда ли, например, $B_{n+1,k}<B_{n,k-1}$ или что-то подобное?

[Хорхе]

Неравенство все же Вы имели в виду в другую сторону, так?

Ну как бы каждому помеченному графу на $n\ge 2$ вершинах с $k-1$ ребрами отвечают как минимум $n$ помеченных на $n+1$ вершине с $k$ ребрами -- тот, где $n+1$-я вершина соединена с 1, тот, где $n+1$-я вершина соединена с 2... Так?
То есть даже так, что ли: $B_{n+1,k}\ge n B_{n,k-1}$.

[rishelie]

Хорхе в сообщении #308884 писал(а):

Неравенство все же Вы имели в виду в другую сторону, так?

Ну как бы каждому помеченному графу на $n\ge 2$ вершинах с $k-1$ ребрами отвечают как минимум $n$ помеченных на $n+1$ вершине с $k$ ребрами -- тот, где $n+1$-я вершина соединена с 1, тот, где $n+1$-я вершина соединена с 2... Так?
То есть даже так, что ли: $B_{n+1,k}\ge n B_{n,k-1}$.

ну да, вроде так... что же меня смутило тогда? :))) вроде полученные графы каждый раз разные, и два разных $n$-вершинных графа порождают разные $n+1$-вершинные.