Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.06177 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913871535538176 |
|---|---|
| author | Cherkashin, Danila Prozorov, Pavel |
| author_facet | Cherkashin, Danila Prozorov, Pavel |
| contents | Counting the number of spanning trees in specific classes of graphs has attracted increasing attention in recent years. In this note, we present unified proofs and generalizations of several results obtained in the 2020s. The main method is to study the behavior of the vertex (degree) enumerator of a distance-hereditary graph under the operations of copying vertices.
Ehrenborg conjecture says that a Ferrer--Young graph maximizes the number of spanning trees among bipartite graphs with the same degree sequence. The second result of this paper is the equivalence of the Ehrenborg conjecture and its polynomial form. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_06177 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The number of trees in distance-hereditary graphs and their friends Cherkashin, Danila Prozorov, Pavel Combinatorics Counting the number of spanning trees in specific classes of graphs has attracted increasing attention in recent years. In this note, we present unified proofs and generalizations of several results obtained in the 2020s. The main method is to study the behavior of the vertex (degree) enumerator of a distance-hereditary graph under the operations of copying vertices. Ehrenborg conjecture says that a Ferrer--Young graph maximizes the number of spanning trees among bipartite graphs with the same degree sequence. The second result of this paper is the equivalence of the Ehrenborg conjecture and its polynomial form. |
| title | The number of trees in distance-hereditary graphs and their friends |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2411.06177 |