RUS  ENG
Full version
JOURNALS // Izvestiya of Saratov University. Mathematics. Mechanics. Informatics // Archive

Izv. Saratov Univ. Math. Mech. Inform., 2006 Volume 6, Issue 1-2, Pages 91–95 (Mi isu666)

This article is cited in 2 papers

Informatics

On minimal strongly connected congruences of a directed path

M. R. Mirzayanov

Saratov State University

Abstract: Let $G = (V, \alpha)$ be a directed graph. An equivalence relation $\theta\subseteq V\times V$ is called a strongly connected congruence of $G$ if the quotient graph $G/\theta$ is strongly connected. Minimal (under inclusion) strongly connected congruences of a directed path are described and the total amount of them is found ($2^{n-3}$ if the path has $n$ vertices).

UDC: 512.5

DOI: 10.18500/1816-9791-2006-6-1-2-91-95



© Steklov Math. Inst. of RAS, 2024