Arborescences of covering graphs

DOI10.5802/ALCO.212zbMATH Open1487.05204arXiv1912.01060OpenAlexW2993988735MaRDI QIDQ2136408FDOQ2136408

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

Publication date: 10 May 2022

Published in: Algebraic Combinatorics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Cluster algebras. I: Foundations
• Title not available (Why is that?)
• A Combinatorial Proof of the All Minors Matrix Tree Theorem
• Title not available (Why is that?)
• Generating all graph coverings by permutation voltage assignments
• Combinatorial optimization. Theory and applications.
• Title not available (Why is that?)
• Critical groups of covering, voltage and signed graphs
• A Greedoid Polynomial Which Distinguishes Rooted Arborescences
• \(R\)-systems

Cited In (7)

• Graph coverings and twisted operators
• On the tree cover number of a graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• Arboreal structure and regular graphs of median-like classes
• Vertex arboricity of cographs
• 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)