Образец для цитирования:
Салий В. Н. Упорядоченное множество связных частей многоугольного графа // Изв. Сарат. ун-та. Нов. сер. Сер. Математика. Механика. Информатика. 2013. Т. 13, вып. 2. С. 44-51. DOI: https://doi.org/10.18500/1816-9791-2013-13-2-2-44-51
Упорядоченное множество связных частей многоугольного графа
Под многоугольным графом понимается ориентированный граф, полученный из цикла путем некоторой ориентации его ребер. Множество абстрактных (т.е. рассматриваемых с точностью до изоморфизма) связных частей многоугольного графа упорядочивается отношением вложимости графов. Получено описание многоугольных графов, для которых это упорядоченное множество является решеткой.
[1]Салий В. Н., “Минимальные примитивные расширения ориентированных графов”, Прикладная дискретная математика, 2008, № 1(1), 116–119 [Salii V. N., “Minimal primitive extensions of oriented graphs”, Prikladnaya diskretnaya matematika, 2008, no. 1(1), 116–119][2]Trotter W. T., Moore J. I., “Some theorems on graphs and posets”, Discrete Math., 15:1 (1976), 79–84 [3]Jacobson M. S., Kézdy F. E., Seif S., “The poset of connected induced subgraphs of a graph need not be Sperner”, Order, 12:3 (1995), 315–318 [4]Kézdy A. E., Seif S., “When is a poset isomorphic to the poset of connected induced subgraphs of a graph?”, Southwest J. Pure Appl. Math., 1 (1996), 42–50, (Accessed 28, September, 2012), (Electronic), Available at: http://rattler.cameron.edu/swjpam.html [5]Nieminen J., “The lattice of connected subgraphs of a connected graph”, Comment. Math. Prace Mat., 21:1 (1980), 187–193 [6]Adams P., Eggleton R. B., MacDougall J. A., “Degree sequences and poset structure of order 9 graphs”, Proc. XXXV Southeast Conf. Comb., Graph Theory and Computing, Congr. Numer., 166, Boca Raton, FL, USA, 2004, 83–95 [7]Leach D., Walsh M., “A characterization of lattice-ordered graphs”, Proc. Integers Conf., Gruyter, N.Y., 2005, 327–332 [8]Салий В. Н., “Система абстрактных связных подграфов линейного графа”, Прикладная дискретная математика, 2012, № 2(16), 90–94 [Salii V. N., “The system of abstract connected subgraphs of a linear graph”, Prikladnaya diskretnaya matematika, 2012, no. 2(16), 90–94]
