|
A graph G with n>=2k vertices is k-linked if and only if for every
choice of two disjoint sets of vertices, each having cardinality k,
and for every numbering {s_1,..,s_k} and {t_1,..,t_k} of the vertices
in the respective sets, there exist k disjoint paths P_1,..,P_k in G
such that P_j starts at s_j and ends at t_j. Note that k is at most
floor(n/2).
Being k-linked is a considerably stronger property of graph than being merely
k-connected and this sequence is a superficial quantitative answer to the
question of how much stronger a property it is. For graph-theoretical answers
to how connectedness and linkedness are related, see the references.
The sequence arises as follows. Let a particular connectivity requirement
consist of a choice of two vertex sets as described above, together with a
particular numbering of the respective elements in the sets, i.e. together
with a prescription which vertex has to be linked to which. The set of all
such particular connectivity requirements can be constructed as follows.
First pick a set of k vertices, then pick another set of vertices among the
remaining n-k vertices of G and then, going along the vertices in the first
set in an arbitrary order, successively prescribe what vertex it is to be
linked to. For the first prescription there are k possibilities, for the
next k-1, etc., so clearly, since there are no dependencies, for a fixed
choice of two vertex sets there are k! prescriptions. It is clear that in
this process every possible particular connectivity requirement arises
exactly twice, since there are two possibilities to choose the first of
the two k-element sets. Thus there are
1/2 * (n choose k) * (n-k choose k) * k! = 1/2 * n!/(k!*(n-2*k)!)
particular connectivity requirements.
| 