цепь

On Minimal Strongly Connected Congruences of a Directed Path

Authors: Mirzayanov M. R.

Let G = (V, α) be a directed graph. An equivalence relation θ ⊆ V × V is called a strongly connected congruence of G if the quotient graph  G/θ is strongly connected. Minimal (under inclusion) strongly connected congruences of a directed  path are described and the total amount of them is found.

The Sperner Property for Polygonal Graphs Considered as Partially Ordered Sets

Authors: Salii V. N.

A finite poset is said to have the Sperner property if at least one of its maximum antichains is formed from elements of the same height. A polygonal graph is a directed acyclic graph derived from a circuit by some orientation of its edges. The reachability relation of a polygonal graph is a partial order. A criterion is presented for posets associated with polygonal graphs to have the Sperner property.

Principal Ideals in the Congruence Semilattice of a Path

Authors: Fomina E. O.

It is proven that principal ideals generated by congruences of a path having the same type are isomorphic lattices. The number of elements, atoms and coatoms is found for the principal ideal generated by a given congruence of a path.