Arborescences of covering graphs

Chepuri, Sunita; Dowd, CJ; Hardt, Andrew; Michel, Gregory; Zhang, Sylvester W.; Zhang, Valerie

doi:10.5802/alco.212

Chepuri, Sunita ¹; Dowd, CJ ²; Hardt, Andrew ³; Michel, Gregory ³; Zhang, Sylvester W.³; Zhang, Valerie ²

¹ University of Michigan Department of Mathematics 2074 East Hall 530 Church St. Ann Arbor MI 48109, USA
² Harvard University Department of Mathematics Science Center Room 325 1 Oxford Street Cambridge MA 02138, USA
³ University of Minnesota School of Mathematics 127 Vincent Hall 206 Church St. SE Minneapolis MN 55414, USA

Algebraic Combinatorics, Volume 5 (2022) no. 2, pp. 319-346.

Abstract

An arborescence of a directed graph $Γ$ 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} (Γ)$ representing the sum of the weights of all such arborescences. The arborescences of a graph and the arborescences of a covering graph $\tilde{Γ}$ are closely related. Using voltage graphs to construct arbitrary regular covers, we derive a novel explicit formula for the ratio of $A_{v} (Γ)$ to the sum of arborescences in the lift $A_{\tilde{v}} (\tilde{Γ})$ 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 $Γ$ are reviewed, and we provide a new proof of Chaiken’s results via a deletion-contraction argument.

Received: 2020-06-05
Revised: 2021-12-04
Accepted: 2021-12-19
Published online: 2022-05-05

DOI: 10.5802/alco.212

Classification: 05C50, 05E18, 05C20, 05C05, 05C22
Keywords: Arborescence, covering graph, voltage graph.

Author's affiliations:

Chepuri, Sunita ¹; Dowd, CJ ²; Hardt, Andrew ³; Michel, Gregory ³; Zhang, Sylvester W. ³; Zhang, Valerie ²

¹ University of Michigan Department of Mathematics 2074 East Hall 530 Church St. Ann Arbor MI 48109, USA
² Harvard University Department of Mathematics Science Center Room 325 1 Oxford Street Cambridge MA 02138, USA
³ University of Minnesota School of Mathematics 127 Vincent Hall 206 Church St. SE Minneapolis MN 55414, USA

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@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
AU  - Chepuri, Sunita
AU  - Dowd, CJ
AU  - Hardt, Andrew
AU  - Michel, Gregory
AU  - Zhang, Sylvester W.
AU  - Zhang, Valerie
TI  - Arborescences of covering graphs
JO  - Algebraic Combinatorics
PY  - 2022
SP  - 319
EP  - 346
VL  - 5
IS  - 2
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.212/
DO  - 10.5802/alco.212
LA  - en
ID  - ALCO_2022__5_2_319_0
ER  -

%0 Journal Article
%A Chepuri, Sunita
%A Dowd, CJ
%A Hardt, Andrew
%A Michel, Gregory
%A Zhang, Sylvester W.
%A Zhang, Valerie
%T Arborescences of covering graphs
%J Algebraic Combinatorics
%D 2022
%P 319-346
%V 5
%N 2
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.212/
%R 10.5802/alco.212
%G en
%F ALCO_2022__5_2_319_0

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/

References
Cited by

[1] Chaiken, Seth 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] Fomin, Sergey; Zelevinsky, Andrei Cluster algebras. I. Foundations, J. Amer. Math. Soc., Volume 15 (2002) no. 2, pp. 497-529 | DOI | MR | Zbl

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

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

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

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

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

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

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

[10] Stanley, Richard P. 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] Stanton, Dennis; White, Dennis Constructive combinatorics, Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1986, x+183 pages | DOI | MR | Zbl

[12] van Aardenne-Ehrenfest, Tatyana; de Bruijn, Nicolaas G. Circuits and trees in oriented linear graphs, Simon Stevin, Volume 28 (1951), pp. 203-217 | MR | Zbl

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

Cited by Sources: