cp's OEIS Frontend

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).

%I A135610 #18 Jul 13 2022 11:06:05
%S A135610 1,3,6,6,10,30,15,90,60,21,210,420,28,420,1680,840,36,756,5040,7560,
%T A135610 45,1260,12600,37800,15120,55,1980,27720,138600,166320,66,2970,55440,
%U A135610 415800,997920,332640,78,4290,102960,1081080,4324320,4324320,91,6006
%N 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).
%C A135610 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).
%C A135610 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.
%C A135610 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.
%C A135610 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.
%D A135610 R. Diestel, Graph Theory, 3rd edition, Springer 2005 (Chapter 3.5).
%H A135610 Peter C. Heinig, <a href="/A135610/b135610.txt">Table of n, a(n) for n = 1..100</a>
%H A135610 D. Kuhn and D. Osthus, <a href="https://doi.org/10.1006/jctb.2002.2133">Topological minors in graphs of large girth</a>, J. Comb. Theory B 86 (2002), 364-380.
%H A135610 W. Mader, <a href="https://doi.org/10.1007/PL00009829">Topological subgraphs in graphs of large girth</a>, Combinatorica 18 (1998), 405-412.
%F A135610 T(n, k) = (1/2) * n!/(k!*(n-2*k)!).
%e A135610 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.
%e A135610 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.
%e A135610 Triangle begins:
%e A135610    1;
%e A135610    3;
%e A135610    6,    6;
%e A135610   10,   30;
%e A135610   15,   90,    60;
%e A135610   21,  210,   420;
%e A135610   28,  420,  1680,   840;
%e A135610   36,  756,  5040,  7560;
%e A135610   45, 1260, 12600, 37800, 15120;
%e A135610   ..
%p A135610 seq(seq(n!/(k!*(n-2*k)!)/2, k=1..floor(n/2)), n=1..20);
%Y A135610 This is A059344/2 without column k=0.
%Y A135610 Cf. A000407.
%K A135610 nonn,tabf
%O A135610 1,2
%A A135610 Peter C. Heinig (algorithms(AT)gmx.de), Feb 27 2008