|
Ученые записки Казанского университета. Серия Физико-математические науки, 2018, том 160, книга 2, страницы 339–349
(Mi uzku1459)
|
|
|
|
Explicit formulas for chromatic polynomials of some series-parallel graphs
[Нахождение хроматических многочленов некоторых параллельно-последовательных графов]
E. Yu. Lerner, S. A. Mukhamedjanova Kazan Federal University, Kazan, 420008 Russia
Аннотация:
Основная цель работы — представить явные формулы для вычисления хроматических многочленов
некоторых параллельно-последовательных графов (sp-графов). Граф
колье, рассматриваемый в данной работе, это простейший нетривиальный
sp-граф. Мы дадим явную формулу для вычисления графа-колье общего
вида. Кроме того, будут даны явные формулы для вычисления
хроматических многочленов графов кольцо из колье и колье из колье
произвольного вида.
Хроматические многочлены графов колье и кольцо из колье изначально
получены нами при помощи перехода к двойственному графу и
дальнейшему использованию потокового многочлена. Кроме того, мы
использовали технику конечного преобразования Фурье.
Более универсальным способом подсчета хроматических многочленов
является использование статистической суммы модели Поттса. Идея
используемых здесь тождеств параллельного и последовательного
сокращения была предложена Аланом Сокалом. Мы разовьем эту идею и
введем преобразование сокращения графа колье. Использование этого
преобразования позволяет упростить вычисление хроматических
многочленов графов колье, кольцо из колье и вычислить хроматический
многочлен графа колье из колье.
Ключевые слова:
хроматические многочлены, статистическая сумма модели Поттса, полином Татта, преобразование Фурье, параллельно-последовательный граф, граф колье.
Поступила в редакцию: 27.11.2017
Образец цитирования:
E. Yu. Lerner, S. A. Mukhamedjanova, “Explicit formulas for chromatic polynomials of some series-parallel graphs”, Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки, 160, no. 2, Изд-во Казанского ун-та, Казань, 2018, 339–349
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/uzku1459 https://www.mathnet.ru/rus/uzku/v160/i2/p339
|
Статистика просмотров: |
Страница аннотации: | 130 | PDF полного текста: | 101 | Список литературы: | 33 |
|