On stability of weighted spanning tree degree enumerators
- Authors: Prozorov P.K.1, Cherkashin D.D.2
-
Affiliations:
- Saint Petersburg State University
- Institute of Mathematics and Informatics, Bulgarian Academy of Sciences
- Issue: Vol 89, No 1 (2025)
- Pages: 115-134
- Section: Articles
- URL: https://journal-vniispk.ru/1607-0046/article/view/303938
- DOI: https://doi.org/10.4213/im9556
- ID: 303938
Cite item
Open Access
Access granted
Subscription Access
Abstract
In [1] it was shown that the degree (vertex) spanning tree enumerator polynomialof a connected graph $G$ is a real stable polynomial (that is, it does not vanish if all thevariables have positive imaginary parts) if and only if $G$ is a distance-hereditary graph.We prove a similar characterization for weighted graphs.With the help of this generalization, define the class of weighted distance-hereditary graphs.
About the authors
Pavel Konstantinovich Prozorov
Saint Petersburg State University
Author for correspondence.
Email: pasha07082005@gmail.com
Danila Dmitrievich Cherkashin
Institute of Mathematics and Informatics, Bulgarian Academy of Sciences
Email: jiocb.orlangyr@gmail.com
Candidate of physico-mathematical sciences, Associate professor
References
- D. Cherkashin, F. Petrov, P. Prozorov, “On stability of spanning tree degree enumerators”, Discrete Math., 346:12 (2023), 113629, 7 pp.
- D. G. Wagner, “Multivariate stable polynomials: theory and applications”, Bull. Amer. Math. Soc. (N.S.), 48:1 (2011), 53–84
- P. Csikvari, A. Schweitzer, “A short survey on stable polynomials, orientations and matchings”, Acta Math. Hungar., 166:1 (2022), 1–16
- Young-Bin Choe, J. G. Oxley, A. D. Sokal, D. G. Wagner, “Homogeneous multivariate polynomials with the half-plane property”, Adv. in Appl. Math., 32:1-2 (2004), 88–187
- H.-J. Bandelt, H. M. Mulder, “Distance-hereditary graphs”, J. Combin. Theory Ser. B, 41:2 (1986), 182–208
- A. Brandstädt, Van Bang Le, J. P. Spinrad, Graph classes: a survey, SIAM Monogr. Discrete Math. Appl., SIAM, Philadelphia, PA, 1999, xii+304 pp.
- Sang-il Oum, “Rank-width and vertex-minors”, J. Combin. Theory Ser. B, 95:1 (2005), 79–100
- P. Bränden, J. Huh, “Lorentzian polynomials”, Ann. of Math. (2), 192:3 (2020), 821–891
Supplementary files
