Publications Repository - Gdańsk University of Technology

A graph G is a locally k-tree graph if for any vertex v the subgraph induced by the neighbours of v is a k-tree, k>=0, where 0-tree is an edgeless graph, 1-tree is a tree. We characterize the minimum-size locally k-trees with n vertices. The minimum-size connected locally k-trees are simply (k + 1)-trees. For k >= 1, we construct locally k-trees which are maximal with respect to the spanning subgraph relation. Consequently, the number of edges in an n-vertex locally k-tree graph is between $Omega(n)$ and $O(n^2)$, where both boundsare asymptotically tight. In contrast, the number of edges in an n-vertex k-tree is always linear in n.

Authors

• Mieczysław Borowiecki,
• dr hab. inż. Piotr Borowiecki link open in new tab ,
• Elżbieta Sidorowicz,
• Zdzisław Skupień