Exploring structural properties of k-trees and block graphs

MaRDI QIDQ6424405zbMATH OpenFDO

Authors Lilian Markenzon, Allana S. S. Oliveira, Cybele T. M. Vinagre

Publication date 25 January 2023

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Enumeration in graph theory (05C30) Structural characterization of families of graphs (05C75)

Abstract: 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.

This page was built for publication: Exploring structural properties of $k$-trees and block graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6424405)