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}\left(\Gamma \right)$ representing the sum of the weights of all such arborescences. The arborescences of a graph and the arborescences of a covering graph $\tilde{\Gamma}$ are closely related. Using voltage graphs to construct arbitrary regular covers, we derive a novel explicit formula for the ratio of ${A}_{v}\left(\Gamma \right)$ to the sum of arborescences in the lift ${A}_{\tilde{v}}\left(\tilde{\Gamma}\right)$ 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.

Revised:

Accepted:

Published online:

Keywords: Arborescence, covering graph, voltage graph.

^{1}; Dowd, CJ

^{2}; Hardt, Andrew

^{3}; Michel, Gregory

^{3}; Zhang, Sylvester W.

^{3}; Zhang, Valerie

^{2}

@article{ALCO_2022__5_2_319_0, author = {Chepuri, Sunita and Dowd, CJ and Hardt, Andrew and Michel, Gregory and Zhang, Sylvester W. and Zhang, Valerie}, title = {Arborescences of covering graphs}, journal = {Algebraic Combinatorics}, pages = {319--346}, publisher = {The Combinatorics Consortium}, volume = {5}, number = {2}, year = {2022}, doi = {10.5802/alco.212}, language = {en}, url = {https://alco.centre-mersenne.org/articles/10.5802/alco.212/} }

TY - JOUR TI - Arborescences of covering graphs JO - Algebraic Combinatorics PY - 2022 DA - 2022/// SP - 319 EP - 346 VL - 5 IS - 2 PB - The Combinatorics Consortium UR - https://alco.centre-mersenne.org/articles/10.5802/alco.212/ UR - https://doi.org/10.5802/alco.212 DO - 10.5802/alco.212 LA - en ID - ALCO_2022__5_2_319_0 ER -

Chepuri, Sunita; Dowd, CJ; Hardt, Andrew; Michel, Gregory; Zhang, Sylvester W.; Zhang, Valerie. Arborescences of covering graphs. Algebraic Combinatorics, Volume 5 (2022) no. 2, pp. 319-346. doi : 10.5802/alco.212. https://alco.centre-mersenne.org/articles/10.5802/alco.212/

[1] A combinatorial proof of the all minors matrix tree theorem, SIAM J. Algebraic Discrete Methods, Volume 3 (1982) no. 3, pp. 319-329 | DOI | MR | Zbl

[2] Cluster algebras. I. Foundations, J. Amer. Math. Soc., Volume 15 (2002) no. 2, pp. 497-529 | DOI | MR | Zbl

[3] $R$-systems, Selecta Math. (N.S.), Volume 25 (2019) no. 2, Paper no. 22, 63 pages | DOI | MR | Zbl

[4] A greedoid polynomial which distinguishes rooted arborescences, Proc. Amer. Math. Soc., Volume 107 (1989) no. 2, pp. 287-298 | DOI | MR | Zbl

[5] Generating all graph coverings by permutation voltage assignments, Discrete Math., Volume 18 (1977) no. 3, pp. 273-283 | DOI | MR | Zbl

[6] The theory of groups, The Macmillan Company, New York, N.Y., 1959, xiii+434 pages | MR | Zbl

[7] Combinatorial optimization: Theory and algorithms, Algorithms and Combinatorics, 21, Springer-Verlag, Berlin, 2006, xvi+597 pages | DOI | MR | Zbl

[8] Critical groups of covering, voltage and signed graphs, Discrete Math., Volume 318 (2014), pp. 10-40 | DOI | MR | Zbl

[9] Determinants of block matrices, The Mathematical Gazette, Volume 84 (2000) no. 501, p. 460â467 | DOI

[10] Enumerative combinatorics. Vol. 2. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin, Cambridge Studies in Advanced Mathematics, 62, Cambridge University Press, Cambridge, 1999, xii+581 pages | DOI | MR | Zbl

[11] Constructive combinatorics, Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1986, x+183 pages | DOI | MR | Zbl

[12] Circuits and trees in oriented linear graphs, Simon Stevin, Volume 28 (1951), pp. 203-217 | MR | Zbl

[13] Double Covers of Flower Graphs and Tutte Polynomials, Minnesota Journal of Undergraduate Mathematics, Volume 6 (2021) no. 1

*Cited by Sources: *