Линейным графом называется граф, полученный из некоторой цепи путём какойлибо ориентации её рёбер. Множество всех графов, изоморфных связным подграфам заданного линейного графа L, упорядочивается отношением вложимости. Выясняется, для каких L это упорядоченное множество будет решёткой.
Скачать электронную версию публикации
Загружен, раз: 68
- Title Система абстрактных связных подграфов линейного графа
- Headline Система абстрактных связных подграфов линейного графа
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 2(16)
- Date:
- DOI
Ключевые слова
линейный граф, абстрактный подграф, упорядоченное множество, решётка, двоичный вектор, двойственность, path, linear graph, abstract subgraph of a graph, ordered set, lattice, binary vector, dualityАвторы
Ссылки
Leach D. and Walsh M. A characterization of lattice-ordered graphs // Proc. Integers Conf. 2005. N.Y.: Gruyter, 2007. P. 327-332.
Adams P., Eggleton R. B., and MacDougall J. A. Degree sequences and poset structure of order 9 graphs // Proc. XXXV Southeast. Conf. Comb., Graph Theory and Computing. Boca Raton, FL, USA. 2004. V. 166. P. 83-95.
Nieminen J. The lattice of connected subgraphs of a connected graph // Comment. Math. Prace Mat. 1980. V.21. No. 1. P. 187-193.
Kezdy A. E. and Seif S. When is a poset isomorphic to the poset of connected induced subgraphs of a graph? // Southwest J. Pure Appl. Math. 1996. V. 1. P. 42-50. (Electronic.)
Trotter W. T. and Moore J. I. Some theorems on graphs and posets // Discr. Math. 1976. V. 15. No. 1. P. 79-84.
Jacobson M. S., Kezdy F. E., and Seif S. The poset of connected induced subgraphs of a graph need not be Sperner // Order. 1995. V. 12. No.3. P. 315-318.
Салий В. Н. Минимальные примитивные расширения ориентированных графов // Прикладная дискретная математика. 2008. №1(1). С. 116-119.
Система абстрактных связных подграфов линейного графа | Прикладная дискретная математика. 2012. № 2(16).
Скачать полнотекстовую версию
Полнотекстовая версияЗагружен, раз: 214