By a result of McKenzie [4] finite directed graphs that satisfy certain connectivity and thinness conditions have the unique prime factorization property with respect to the cardinal product. We show that this property still holds under weaker connectivity and stronger thinness conditions. Furthermore, for such graphs the factorization can be determined in polynomial time.
By a result of McKenzie [7] all finite directed graphs that satisfy certain connectivity conditions have unique prime factorizations with respect to the cardinal product. McKenzie does not provide an algorithm, and even up to now no polynomial algorithm that factors all graphs satisfying McKenzie's conditions is known. Only partial results [1,3,5] have been published, all of which depend on certain thinness conditions of the graphs to be factored. In this paper we weaken the...
In this paper we present factorization theorems for strong maps between matroids of arbitrary cardinality. Moreover, we present a new way to prove the factorization theorem for strong maps between finite matroids.
We study the concept of an -partition of the vertex set of a graph , which includes all vertex partitioning problems into four parts which we require to be nonempty with only external constraints according to the structure of a model graph , with the exception of two cases, one that has already been classified as polynomial, and the other one remains unclassified. In the context of more general vertex-partition problems, the problems addressed in this paper have these properties: non-list, -part,...
We study the concept of an H-partition of the vertex set of a graph G, which includes all vertex partitioning problems into four parts which we require to be nonempty with only external constraints according to the structure of a model graph H, with the exception of two cases, one that has already been classified as polynomial, and the other one remains unclassified. In the context of more general vertex-partition problems, the problems addressed in this paper have these properties: non-list, 4-part, external...
A form-finding problem for tensegrity structures is studied; given an abstract graph, we show an algorithm to provide a necessary condition for it to be the underlying graph of a tensegrity in Rd (typically d=2,3) with vertices in general position. Furthermore, for a certain class of graphs our algorithm allows to obtain necessary and sufficient conditions on the relative position of the vertices in order to underlie a tensegrity, for what we propose both a geometric and a symbolic approach.