Tree-decompositions of graphs. I

DOI10.1007/BF02882459MaRDI QIDQ1370176zbMATH OpenOpenAlexFDO

Publication date 16 February 1998

Published in Chinese Science Bulletin (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02882459

Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

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.

Recommendations

Cites work

Two trees in maximal planar bipartite graphs

Cited in

(18)

This page was built for publication: Tree-decompositions of graphs. I

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