Geodesic
Congruence relations of paths: some combinatorial properties
Prikladnaâ diskretnaâ matematika, no. 2 (2012), pp. 86-89.

Voir la notice de l'article provenant de la source Math-Net.Ru

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, Bell number.
Mots-clés : congruence relation, equivalence relation, quotient-graph 
@article{PDM_2012_2_a6,
     author = {E. O. Karmanova},
     title = {Congruence relations of paths: some combinatorial properties},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {86--89},
     publisher = {mathdoc},
     number = {2},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2012_2_a6/}
}
TY  - JOUR
AU  - E. O. Karmanova
TI  - Congruence relations of paths: some combinatorial properties
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2012
SP  - 86
EP  - 89
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2012_2_a6/
LA  - ru
ID  - PDM_2012_2_a6
ER  - 
%0 Journal Article
%A E. O. Karmanova
%T Congruence relations of paths: some combinatorial properties
%J Prikladnaâ diskretnaâ matematika
%D 2012
%P 86-89
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2012_2_a6/
%G ru
%F PDM_2012_2_a6
E. O. Karmanova. Congruence relations of paths: some combinatorial properties. Prikladnaâ diskretnaâ matematika, no. 2 (2012), pp. 86-89. http://geodesic.mathdoc.fr/item/PDM_2012_2_a6/

[1] Bogomolov A. M., Salii V. N., Algebraicheskie osnovy teorii diskretnykh sistem, Nauka, M., 1997, 367 pp. | MR | Zbl

[2] Mirzayanov M. R., “Silno svyaznye kongruentsii orientirovannykh grafov”, Teoreticheskie problemy informatiki i ee prilozhenii, 7, Izd-vo Sarat. un-ta, Saratov, 2006, 104–114

[3] Mirzayanov M. R., “O minimalnykh silno svyaznykh kongruentsiyakh orientirovannykh tsepei”, Izv. Sarat. un-ta. Ser. Matematika. Mekhanika. Informatika, 6:1–2 (2006), 91–95

[4] Karmanova E. O., “O kongruentsiyakh tsepei”, Prikladnaya diskretnaya matematika, 2011, no. 2(12), 96–100

[5] Duncan B., Peele R., “Bell and Stirling numbers for Graphs”, J. Integ. Sequenc., 12 (2009), Article 09.7.1 | MR | Zbl

[6] Kristofides N., Teoriya grafov. Algoritmicheskii podkhod, Mir, M., 1978, 227–239 | MR

[7] Bellman R., Cooke K. L., “The Konigsberg bridges problem generalized”, J. Math. Anal. Appl., 25 (1969), 1–7 | DOI | MR | Zbl