Arborescences of covering graphs

DOI10.5802/ALCO.212MaRDI QIDQ2136408zbMATH OpenOpenAlexFDO

Authors Sunita Chepuri, C. J. Dowd, Andrew Hardt, Gregory Michel, Sylvester W. Zhang, Valerie Zhang

Publication date 10 May 2022

Published in Algebraic Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1912.01060

zbMATH Keywords

arborescencevoltage graphcovering graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Group actions on combinatorial structures (05E18)

Abstract: An arborescence of a directed graph $Gamma$ is a spanning tree directed toward a particular vertex $v$. The arborescences of a graph rooted at a particular vertex may be encoded as a polynomial $A_v(Gamma)$ representing the sum of the weights of all such arborescences. The arborescences of a graph and the arborescences of a covering graph $ildeGamma$ are closely related. Using voltage graphs as means to construct arbitrary regular covers, we derive a novel explicit formula for the ratio of $A_v(Gamma)$ to the sum of arborescences in the lift $A_{ildev}(ildeGamma)$ in terms of the determinant of Chaiken's voltage Laplacian matrix, a generalization of the Laplacian matrix. Chaiken's results on the relationship between the voltage Laplacian and vector fields on $Gamma$ are reviewed, and we provide a new proof of Chaiken's results via a deletion-contraction argument.

Recommendations

• Balanced vertex weightings and arborescences
• scientific article; zbMATH DE number 4212101
• Prime Factorization of the Kirchhoff Polynomial: Compact Enumeration of Arborescences
• A contribution to the theory of voltage graphs
• Coverings of graphs and maps, orthogonality, and eigenvectors

Cites work

• scientific article; zbMATH DE number 3137403 (Why is no real title available?)
• scientific article; zbMATH DE number 3957110 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 3068971 (Why is no real title available?)
• A Combinatorial Proof of the All Minors Matrix Tree Theorem
• A Greedoid Polynomial Which Distinguishes Rooted Arborescences
• Cluster algebras. I: Foundations
• Combinatorial optimization. Theory and applications.
• Critical groups of covering, voltage and signed graphs
• Generating all graph coverings by permutation voltage assignments
• \(R\)-systems

Cited in

(7)

• Vertex arboricity of cographs
• scientific article; zbMATH DE number 3959491 (Why is no real title available?)
• scientific article; zbMATH DE number 5775505 (Why is no real title available?)
• On the tree cover number of a graph
• Arboreal structure and regular graphs of median-like classes
• Graph coverings and twisted operators
• Iwasawa theory of Jacobians of graphs

This page was built for publication: Arborescences of covering graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2136408)