RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika // Archive

Prikl. Diskr. Mat., 2011 Number 2(12), Pages 96–100 (Mi pdm277)

This article is cited in 4 papers

Applied Graph Theory

On congruences of paths

E. O. Karmanova

Saratov State University named after N. G. Chernyshevsky, Saratov, Russia

Abstract: A congruence of a path is an equivalence relation on the set of path's vertices all of whose classes are independent subsets. It is shown that each connected graph is a quotient-graph of a suitable path. Valuations are established for the minimal length of a chain whose quotient-graph is a given graph.

Keywords: path, congruence, quotient-graph, tree, star.

UDC: 512.2



© Steklov Math. Inst. of RAS, 2024