ON SOME PROPERTIES OF N-SEQUENTIALLY CONNECTED CHAIN
DOI:
https://doi.org/10.14529/cmse130111Abstract
It is introduced the class of the nonorientedn-sequentially connected chain. It is considered the applicationfields of then-sequentially connected chains, in particular the problems of optimal location in discrete formulations, and the problems of selection the optimal conduct in systems, described by Markov controllable processes. The main characteristics ofn-sequentially connected chains, such as the number of edges, the size of the maximum clique, the chromatic and the cyclomatic numbers, etc. are given. The relations of the classn-sequentially connected chains to perfect, triangulated, composite and splittable classes of graphs are determined.
References
Panyukov, A.V. Polynomial Algorithms to Finite Veber Problem for a Tree Network / A. V. Panyukov, B.V. Pelzwerger // Journal of Computational and Applied Mathematics. – 1991. – Vol. 35. – P. 291–296.
Шангин, Р.Э. Детерминированный алгоритм для решения задачи Вебера для n-последовательносвязной цепи / Р.Э. Шангин // XIII Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям: Труды Всероссийской конференции (Новосибирск, 15–17 октября 2012 г.). URL: http://conf.nsc.ru/ym2012/ru/reportview/137128 (дата обращения: 15.10.2012).
Bender, E.A. Almost All Chordal Graphs Split / E.A. Bender, L.B. Richmond, N. C. Wormald // Journal of the Australian Mathematical Society. – 1985. – Vol. 38. – P. 214–221.
McKee, T.A. On the Chordality of a Graph / T.A. McKee, E.R. Scheinerman // Journal of Graph Theory. – 1993. – Vol. 17. – P. 221–232.
McKee, T.A. Beyond Chordal Graphs / T.A. McKee // Journal of Combinatorial Mathematics and Combinatorial Computing. – 1997. – Vol. 23. – P. 21–31.
Dirac, G.A. On Rigid Circuit Graphs / G.A. Dirac // Abhandlungen aus dem Mathematischen Seminar der Universit¨at Hamburg. – 1961. – Vol. 25. – P. 71–76.
