
AbstractA k‐tree is defined recursively as follows: The complete graph Kk on k points is a k‐tree. Given a k‐tree G on n ≤ k points, a k‐tree on n + 1 points is obtained by adding a new point u and edges connecting u to every point of a Kk in G. A graph is a partial k‐tree if it is a subgraph of some k‐tree. In this paper, we establish some interesting properties of partial 3‐trees and show that a graph is a partial 3‐tree if and only if it has no subgraph contractible to K5, K2.2.2 C8(1, 4), or K2 ≤ C5. A graph G is said to be contractible to a graph H if H can be obtained from G by a sequence of edge contractions. hitherto, such a characterization of partial k‐trees was known only for the values of k ≤ 2.
k-trees, partial 3-tree, subgraphs, Programming involving graphs or networks, Trees
k-trees, partial 3-tree, subgraphs, Programming involving graphs or networks, Trees
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 29 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
