A relation between the generating function of k-partite graphs and the generating function of the number of k-partite representations of graphs is obtained. A correlation between the relation's coefficients and chromatic polynomial coefficients is shown. An application of the results to calculation of weighted sums is demonstrated. Special cases of sums and some applications of the relations in physics and mathematics are considered.
Download file
Counter downloads: 347
- Title Generating function for representations of graphs by k-partite graphs
- Headline Generating function for representations of graphs by k-partite graphs
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 1(31)
- Date:
- DOI
Keywords
weighted sum, chromatic polynomial, generating functions, multigraph, hypergraph, k-partite graph, graph, взвешенная сумма, хроматический полином, производящие функции, мультиграф, гиперграф, k-дольный граф, графAuthors
References
Лифшиц Е. М., Питаевский Л. П. Статистическая физика. Ч. 2. М.: Наука, 1978.
Фомичев В. М. Методы дискретной математики в криптологии. М.: Диалог-МИФИ, 2010.
Харари Ф. Теория графов. М.: УРСС, 2003.
Каку М. Введение в теорию суперструн. М.: Мир, 1999.
Фейнман Р. Статистическая механика: Курс лекций. М.: Мир, 1975.
Абрикосов А. А., Горьков Л.П., Дзялошинский И. Е. Методы квантовой теории поля в статистической физике. М.: Физматгиз, 1962.
Кнут Д., Грэхем Ф., Паташник О. Конкретная математика. Основание информатики. М.: Мир, 2006.
Ганопольский Р. М. Производящие функции последовательности чисел покрытий конечного множества // Прикладная дискретная математика. 2011. №1(11). С. 5-13.
Ганопольский Р. М. Производящие функции последовательности чисел связных покрытий // Прикладная дискретная математика. 2013. №3(21). С. 5-10.
Ганопольский Р. М. Число неупорядоченных покрытий конечного множества подмножествами фиксированного размера // Прикладная дискретная математика. 2010. №4(10). С. 5-17.
Стенли Р. Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции. М.: Мир, 2005.
Ганопольский Р. М. Экспоненциальные производящие функции последовательности чисел k-дольных графов // Прикладная дискретная математика. 2015. №1(27). С. 84-91.
Generating function for representations of graphs by k-partite graphs | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2016. № 1(31).