Autor: |
Markenzon, Lilian, de Oliveira, Allana S. S., Vinagre, Cybele T. M. |
Zdroj: |
Computational & Applied Mathematics; Jun2024, Vol. 43 Issue 4, p1-10, 10p |
Abstrakt: |
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 allow us to present a new approach for determining the number of spanning trees of any connected block graph and to address a special case of a “reverse problem" raised in the literature. We show that these results can be accomplished in linear time complexity. [ABSTRACT FROM AUTHOR] |
Databáze: |
Complementary Index |
Externí odkaz: |
|