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

Prikl. Diskr. Mat., 2011 supplement № 4, Pages 91–92 (Mi pdm297)

Applied Graph Theory

On congruences of paths

E. O. Karmanova

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

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 a minimal length of a chain whose quotient-graph is a given graph.

UDC: 512.2



© Steklov Math. Inst. of RAS, 2024