A congruence relation of a path is an equivalence relationon the set of its vertices all of whose classes are independent subsets. It is proved (theorem1) that the number of all congruence relations of a path with m edges equals to thenumber of all equivalence relations on a m-element set. For a given connected graph Gtheorem 2 determines the length of the shortest path whose quotient-graph is G.
Download file
Counter downloads: 70
- Title Congruence relations of paths: some combinatorial properties
- Headline Congruence relations of paths: some combinatorial properties
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 2(16)
- Date:
- DOI
Keywords
quotient-graph, Bell number, equivalence relation, congruence relation, path, число Белла, фактор- граф, отношение эквивалентности, конгруэнция, цепьAuthors
References
Bellman R. and Cooke K. L. The Konigsberg bridges problem generalized // J. Math. Anal. Appl. 1969. No. 25. P. 1-7.
Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. С. 227-239.
Duncan B. and Peele R. Bell and Stirling numbers for Graphs // J. Integ. Sequenc. 2009. V. 12. Article 09.7.1.
Карманова Е. О. О конгруэнциях цепей // Прикладная дискретная математика. 2011. № 2(12). С. 96-100.
Мирзаянов М. Р. О минимальных сильно связных конгруэнциях ориентированных цепей // Изв. Сарат. ун-та. Сер. Математика. Механика. Информатика. 2006. Т. 6. Вып. 1/2. С.91-95.
Мирзаянов М. Р. Сильно связные конгруэнции ориентированных графов // Теоретические проблемы информатики и ее приложений. Вып. 7. Саратов: Изд-во Сарат. ун-та, 2006. С.104-114.
Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М.: Наука, 1997. 367 с.
Congruence relations of paths: some combinatorial properties | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2012. № 2(16).
Download full-text version
Download fileCounter downloads: 211