Перевод названия: Перечисление остовных деревьев кобордизма двух циркулянтных графов
Тип публикации: статья из журнала
Год издания: 2018
Идентификатор DOI: 10.17377/semi.2018.15.093
Ключевые слова: Circulant graph, igraph, Petersen graph, spanning tree, Chebyshev polynomial, Mahler measure, циркулянтный граф, I-граф, граф Петерсена, остовное дерево, полином Чебышева, мера Малера
Аннотация: We consider a family of graphs Hn(si,..., sk; ti,...,tl) that is a generalisation of the family of I -graphs, which, in turn, includes the generalized Petersen graphs. We present an explicit formula for the number t (n) of spanning trees in these graphs in terms of the Chebyshev polynomials and find its asymptotics. Also, we show that the number of spanning trees can be represented in the form t(n) = pna(n)2, where a(n) is an integer sequence and p is a prescribed integer depending on the number of even elements in the sequence si,..., sk,ti,...,ti and the parity of n. Мы рассматриваем семейство графов Hn(si,...,sk; ti,...,te), обобщающее семейство I-графов, которое, в свою очередь, содержит обобщенные графы Петерсена. Нами предложена явная формула для числа т (n) остовных деревьев в указанных графах в терминах полиномов Чебышева и найдена ее асимптотика. Также в работе показано, что число остовных деревьев можно представить в виде т(n) = pna(n)2, где a(n) - целочисленная последовательность и p - некоторое целое число, зависящее от количества четных элементов среди параметров si,..., sk,ti,...,te и от четности n.
Журнал: Сибирские электронные математические известия
Выпуск журнала: Т. 15
Номера страниц: 1145-1157
ISSN журнала: 18133304
Место издания: Новосибирск
Издатель: Федеральное государственное бюджетное учреждение науки Институт математики им. С.Л. Соболева Сибирского отделения Российской академии наук