HomeIssuesOn congruences of paths

On congruences of paths | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2011. № 2(12).

A congruence of a path is anequivalence 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. Valuationsare established for the minimal length of a chain whose quotient-graph is a given graph.
Download file
Counter downloads: 64
  • Title On congruences of paths
  • Headline On congruences of paths
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 2(12)
  • Date:
  • DOI
Keywords
звезда, дерево, фактор-граф, конгруэнция, цепь, обход, path, congruence, quotient-graph, tree, star
Authors
References
Prodinger H. and Tichy R. F. Fibonacci numbers of graphs // Fibon. Quart. 1982. V. 20. No. 1. P. 16-21.
Карманова Е. О. О конгруэнциях цепей и циклов // Компьютерные науки и информационные технологии. Саратов: Изд-во Сарат. ун-та, 2009. С. 238.
Мирзаянов М. Р. О минимальных сильно связных конгруэнциях ориентированных цепей // Изв. Сарат. ун-та. Сер. Математика. Механика. Информатика. 2006. Т. 6. Вып. 1/2. С.91-95.
Мирзаянов М. Р. Сильно связные конгруэнции ориентированных графов // Теоретические проблемы информатики и ее приложений. Саратов: Изд-во Сарат. ун-та, 2006. Вып. 7. С.104-114.
Верзаков Г. Ф., Киншт Н. В., Рабинович В. И., Тимонен Л. С. Введение в техническую диагностику. М.: Энергия, 1968.
Оре О. Теория графов. 2-е изд. М.: Наука, 1980. 336 с.
Hayes J. P. A graph model for fault-tolerant computing systems // IEEE Trans. Comput. 1976. No. 9. P. 25.
Абросимов М. Б. Некоторые вопросы о минимальных расширениях графов // Изв. Сарат. ун-та. Сер. Математика. Механика. Информатика. 2005. Т. 5. Вып. 1. С. 86-91.
Салий В. Н. Оптимальные реконструкции графов // Современные проблемы дифференциальной геометрии и общей алгебры. Саратов: Изд-во Сарат. ун-та, 2008. С. 59-65.
Богомолов А. М., Салий В. Н. Алгебраические основы теории дискретных систем. М.: Наука, Физматлит, 1997. 367 с.
On congruences of paths | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2011. № 2(12).
On congruences of paths | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2011. № 2(12).
Download full-text version
Counter downloads: 195
Download file