zbMATH — the first resource for mathematics

A characterization of partial 3-trees. (English) Zbl 0701.90092
The paper is concerned with a class of subgraphs called k-trees and their subgraphs. A k-tree is defined recursively as follows. The complete graph \(K_ k\) on k points is a k-tree. Given a k-tree G on \(n\geq 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 \(K_ k\) in G. A partial k-tree is a subgraph of some k-tree. The authors establish 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 \(K_ 5\), \(K_{2,2,2}\), \(C_ 8(1,4)\&K_ 2\times C_ 5\). Hitherto, such a characterization of partial k-trees was known only for the values of \(k\leq 2\).
Reviewer: M.Savelsbergh

90C35 Programming involving graphs or networks
05C05 Trees
Full Text: DOI
[1] Arnborg, SIAM J. Alg. Discr. Math. 7 pp 305– (1986)
[2] Arnborg, SIAM J. Alg. Discr. Math. 8 pp 277– (1987)
[3] Beineke, Mathematika 18 pp 141– (1971)
[4] Dirac, Abh. Math. Sem. Univ. Hamburg 25 pp 71– (1961)
[5] Duffin, J. Math. Appl. 10 pp 302– (1965)
[6] Graph Theory, Addison-Wesley, Reading, MA (1972).
[7] , and , A characterization of the partial 3-tree in terms of certain structures. In Proceedings of ISCAS 1985, IEEE.
[8] Rose, J. Math. Anal. Appl. 32 pp 597– (1970)
[9] Rose, Discre. Math. 7 pp 317– (1974) · Zbl 0285.05128 · doi:10.1016/0012-365X(74)90042-9
[10] Connectivity in Graphs, Toronto University Press, Toronto (1966).
[11] Wald, Networks 13 pp 159– (1983)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.