Exploring structural properties of $k$-trees and block graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915798627385344 |
|---|---|
| author | Markenzon, Lilian Oliveira, Allana S. S. Vinagre, Cybele T. M. |
| author_facet | Markenzon, Lilian Oliveira, Allana S. S. Vinagre, Cybele T. M. |
| contents | We present a new characterization of $k$-trees based on their reduced clique graphs and $(k+1)$-line graphs, which are block graphs. We explore structural properties of these two classes, showing that the number of clique-trees of a $k$-tree $G$ equals the number of spanning trees of the $(k+1)$-line graph of $G$. This relationship allows to present a new approach for determining the number of spanning trees of any connected block graph. We show that these results can be accomplished in linear time complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_10805 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Exploring structural properties of $k$-trees and block graphs Markenzon, Lilian Oliveira, Allana S. S. Vinagre, Cybele T. M. Combinatorics 05C75, 05C50, 05C30 We present a new characterization of $k$-trees based on their reduced clique graphs and $(k+1)$-line graphs, which are block graphs. We explore structural properties of these two classes, showing that the number of clique-trees of a $k$-tree $G$ equals the number of spanning trees of the $(k+1)$-line graph of $G$. This relationship allows to present a new approach for determining the number of spanning trees of any connected block graph. We show that these results can be accomplished in linear time complexity. |
| title | Exploring structural properties of $k$-trees and block graphs |
| topic | Combinatorics 05C75, 05C50, 05C30 |
| url | https://arxiv.org/abs/2301.10805 |