Yali Harrary - cp's OEIS frontend

User: Yali Harrary

Yali Harrary has authored 2 sequences.

A359686 Triangle read by rows: T(n,k) is the minimum number of connected endofunctions that are spanning subgraphs of a semi-regular loopless digraph on n vertices each with out-degree k.

1, 1, 8, 0, 14, 78, 0, 22, 213, 944, 0, 0, 529, 3400, 13800, 0, 0

Offset: 2

Yali Harrary, Jan 11 2023

An endofunction represented as a digraph is one in which every vertex has out-degree 1. Loopless means that there are no fixed points in the function. The digraph of a connected endofunction is unicyclic (contains exactly one cycle).
In the case k = 1, the graphs considered have vertices with out-degree 1 and the entire graph is the only spanning subgraph that is an endofunction. Hence T(n,1) = 0. (n > 3 because when n = 2, 3 it still will be unicyclic.)
In the case k = n-1, the graphs considered are the complete digraphs and every connected endofunction on the vertex set is a subgraph. Hence T(n, n-1) = A000435(n), which gives the total number of connected endofunctions without fixed points.

			Triangle begins:
  2 | 1;
  3 | 1,  8;
  4 | 0, 14,  78;
  5 | 0, 22, 213,  944;
  6 | 0,  0, 529, 3400, 13800;
  ...
In the following examples, the notation 1->{2,3} is shorthand for the set of arcs {(1,2), (1,3)}.
T(5,2) = 22 is attained with the digraph described by: 1->{4,5}, 2->{3,5}, 3->{2,4}, 4->{1,3}, 5->{1,2}.

Cf. A000435, A359628.

T(n,1) = 0 for n > 3, otherwise 1.
T(n,n-1) = A000435(n).
T(n,k) = 0 for 2*k + 2 < n.

A359628 Triangle read by rows: T(n,k) is the maximum number of connected endofunctions that are spanning subgraphs of a semi-regular loopless digraph on n vertices each with out-degree k.

Original entry on oeis.org

1, 1, 8, 1, 16, 78, 1, 32, 234, 944, 1, 64, 710, 3776, 13800, 1, 128

Offset: 2

Yali Harrary, Jan 08 2023

An endofunction represented as a digraph is one in which every vertex has out-degree 1. Loopless means that there are no fixed points in the function. The digraph of a connected endofunction is unicyclic (contains exactly one cycle).
In the case k = 1, the graphs considered have vertices with out-degree 1 and the entire graph is the only spanning subgraph that is an endofunction. Hence T(n,1) = 1.
In the case k = n-1, the graphs considered are the complete digraphs and every connected endofunction on the vertex set is a subgraph. Hence T(n, n-1) = A000435(n), which gives the total number of connected endofunctions without fixed points.

			Triangle begins:
  2 | 1;
  3 | 1,  8;
  4 | 1, 16,  78;
  5 | 1, 32, 234,  944;
  6 | 1, 64, 710, 3776, 13800;
  ...
In the following examples, the notation 1->{2,3} is shorthand for the set of arcs {(1,2), (1,3)}.
T(5,2) = 32 is attained with the digraph described by: 1->{2,3}, 2->{1,3}, 3->{1,2}, 4->{1,2}, 5->{1,2}. Regardless of the endofunction chosen, it will contain exactly one cycle and will therefore be connected, so T(5,2) = 2^5 = 32. One such endofunction is 1->2, 2->1, 3->1, 4->1, 5->1 which has the cycle between nodes 1 and 2.
T(5,3) = 234 is attained with the digraph constructed from the complete graph on 4 vertices plus a 5th vertex described by 5->{1,2,3}. The number of endofunctions which are spanning subgraphs is A000435(4)*3 = 78 * 3, since any of the 3 choices for the 5th vertex will not create a new cycle.
T(6,3) = 710 is attained with the digraph described by 1->{2,3,4}, 2->{1,3,4}, 3->{1,2,5}, 4->{3,5,6}, 5->{1,2,6}, 6->{1,2,3}. Up to isomorphism this is the only graph. Just 19 of the possible 3^6 = 729 endofunctions that are subgraphs of this digraph are disconnected. They have cycles described by one of the following permutations written in cycle notation: (13)(2456), (1456)(23), (135)(246), (146)(235), (12)(356), (13)(245), (13)(246), (145)(23), (146)(23). The last 5 of these omit one vertex which does not appear in a cycle.

Yali Harrary, Python Program for generating triangle

Cf. A000435 (connected endofunctions without fixed points).

T(n,1) = 1.
T(n,2) = 2^n.
T(n,n-1) = A000435(n).
Conjecture: T(n,n-2) = A000435(n-1)*(n-2) for n > 2.
From Andrew Howroyd, Jan 08 2023: (Start)
T(n,k) >= k*T(n-1, k) for n >= k + 2.
k^(n-k-1)*A000435(k+1) <= T(n,k) <= k^n for k < n.
(End)

cp's OEIS Frontend

User: Yali Harrary

A359686 Triangle read by rows: T(n,k) is the minimum number of connected endofunctions that are spanning subgraphs of a semi-regular loopless digraph on n vertices each with out-degree k.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula