|
Prikladnaya Diskretnaya Matematika, 2012, Number 2(16), Pages 86–89
(Mi pdm363)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Applied Graph Theory
Congruence relations of paths: some combinatorial properties
E. O. Karmanova Saratov State University named after N. G. Chernyshevsky, Saratov, Russia
Abstract:
A congruence relation of a path is an equivalence relation on the set of its vertices all of whose classes are independent subsets. It is proved (theorem 1) that the number of all congruence relations of a path with $m$ edges equals to the number of all equivalence relations on a $m$-element set. For a given connected graph $G$ theorem 2 determines the length of the shortest path whose quotient-graph is $G$.
Keywords:
path, congruence relation, equivalence relation, quotient-graph, Bell number.
Citation:
E. O. Karmanova, “Congruence relations of paths: some combinatorial properties”, Prikl. Diskr. Mat., 2012, no. 2(16), 86–89
Linking options:
https://www.mathnet.ru/eng/pdm363 https://www.mathnet.ru/eng/pdm/y2012/i2/p86
|
Statistics & downloads: |
Abstract page: | 197 | Full-text PDF : | 92 | References: | 29 | First page: | 1 |
|