
doi: 10.1007/bf02882459
The author proves the following two theorems: Theorem 1. Let \(G\) be a connected graph with order \(n\geq 3\) and size \(2n-4\) and \(u\) and \(v\) be two given vertices of \(G\) with \(uv\in E(G)\). Then \(G\) has an \(\{n,n-2\}\)-tree-decomposition with \(u\) and \(v\) as the two singular vertices if and only if the number of edges \(\varepsilon(H)\leq 2(|H|-1)-|H\cap\{u,v\}|\) for any induced subgraph \(H\) of \(G\) with order at least 3. Theorem 2. Let \(G\) be a connected graph with order \(n\geq 3\) and size \(2n-4\) and \(u\) and \(v\) be two given vertices of \(G\). Then \(G\) has an \(\{n-1,n-1\}\)-tree-decomposition with \(u\) and \(v\) as the two singular vertices if and only if \(uv\notin E(G)\) and the number of edges \(\varepsilon(H)\leq 2(|H|- 1)-|H\cap\{u,v\}|\) for any induced subgraph \(H\) of \(G\) with order at least 3.
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), tree-decomposition, connected graph, Trees
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), tree-decomposition, connected graph, 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). | 2 | |
| 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). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
