Combinatorial explanation of the weighted Laplacian characteristic polynomial of a graph and applications

Linghai Liu and Weigen Yan

Applied Mathematics and Computation, 2023, vol. 457, issue C

Abstract: Assume that G is a graph with n vertices v1,v2,…,vn. Given a rooted spanning forest F of G, which has s components and roots vk1,vk2,…,vks, define the weight ω(F) of F to be ∏i=1sxki, where x1,x2,…,xn are n independent commuting variables. In this paper, we give combinatorial explanations of the weighted enumeration of rooted spanning forests of G, the Laplacian characteristic polynomial of G, and the weighted Laplacian det[L+diag(x1,x2,…,xn)], where L is the Laplacian matrix of G and diag(x1,x2,…,xn) is a diagonal matrix. As applications, we count rooted spanning forests in the almost complete bipartite graph, and we also give a new proof of a formula on the number of rooted spanning forests in a complete multipartite graph Ka1,a2,…,as each of which has bi roots in the i-th part for i=1,2,…,s.

Keywords: Rooted spanning forest; Spanning tree; Laplacian matrix; Generating function; Almost complete bipartite graph (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300323003569
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:457:y:2023:i:c:s0096300323003569

DOI: 10.1016/j.amc.2023.128187

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().