A135610 Triangle read by rows: the k-th entry of row n is the number of particular connectivity requirements that a k-linked graph with n >= 2k vertices has to satisfy T(n,k) = (1/2) * n!/(k!*(n-2*k)!) where k runs from 1 to floor(n/2).

1, 3, 6, 6, 10, 30, 15, 90, 60, 21, 210, 420, 28, 420, 1680, 840, 36, 756, 5040, 7560, 45, 1260, 12600, 37800, 15120, 55, 1980, 27720, 138600, 166320, 66, 2970, 55440, 415800, 997920, 332640, 78, 4290, 102960, 1081080, 4324320, 4324320, 91, 6006

Offset: 1

Author

Peter C. Heinig (algorithms(AT)gmx.de), Feb 27 2008

Keywords

• nonn
• tabf

Comments

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) * C(n,k) * C(n-k, k) * k! = (1/2) * n!/(k!*(n-2*k)!) particular connectivity requirements.

Examples

			If n=4 and k=1, then (1/2)*C(4,1)*C(4-1,1)*1! = 6, so there are 6 particular connectivity requirements that a 1-linked graph with 4 vertices has to satisfy.
If n=4 and k=2, then (1/2)*C(4,2)*C(4-2,2)*2! = 6, so there are again 6 particular connectivity requirements that a 2-linked graph with 4 vertices has to satisfy.
Triangle begins:
   1;
   3;
   6,    6;
  10,   30;
  15,   90,    60;
  21,  210,   420;
  28,  420,  1680,   840;
  36,  756,  5040,  7560;
  45, 1260, 12600, 37800, 15120;
  ..
		

References

• R. Diestel, Graph Theory, 3rd edition, Springer 2005 (Chapter 3.5).

Links

• Peter C. Heinig, Table of n, a(n) for n = 1..100
• D. Kuhn and D. Osthus, Topological minors in graphs of large girth, J. Comb. Theory B 86 (2002), 364-380.
• W. Mader, Topological subgraphs in graphs of large girth, Combinatorica 18 (1998), 405-412.

Crossrefs

This is A059344/2 without column k=0.

Cf. A000407.

Programs

Maple

seq(seq(n!/(k!*(n-2*k)!)/2, k=1..floor(n/2)), n=1..20);

Formula

T(n, k) = (1/2) * n!/(k!*(n-2*k)!).