×

Forbidden minors characterization of partial 3-trees. (English) Zbl 0701.05016

A partial k-tree is a subgraph of a graph that can be reduced to the complete graph of order k by a sequence of operations each being a removal of a degree k vertex with completely connected neighbours. In the paper the class of partial 3-trees is characterized by its set of four minimal forbidden minors.
Reviewer: P.Kirschenhofer

MSC:

05C05 Trees

Keywords:

graph minors; trees
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arnborg, S., Reduced state enumeration—another algorithm for reliability evaluation, IEEE Trans. Reliability, R-27, 101-105 (1978) · Zbl 0436.60062
[2] Arnborg, S., Efficient algorithms for combinatorial problems on graphs with bounded decomposability—a survey, BIT, 25, 2-33 (1985) · Zbl 0573.68018
[3] Arnborg, S.; Corneil, D. G.; Proskurowski, A., Complexity of finding embeddings in a \(k\)-tree, SIAM J. Alg. and Discr. Methods, 8, 277-284 (1987) · Zbl 0611.05022
[4] Arnborg, S.; Proskurowski, A., Characterization and recognition of partial 3-trees, SIAM J. Alg. and Discr. Methods, 7, 305-314 (1986) · Zbl 0597.05027
[5] Arnborg, S.; Proskurowski, A., Linear Time Algorithms for NP-hard Problems on Graphs Embedded in \(k\)-trees, (TRITA-NA-8404. TRITA-NA-8404, Linear Time Algorithm for NP-hard Problems on Graphs Embedded in \(k\)-trees (1984), The Royal Institute of Technology), (to appear in Discr. Appl. Math., 1989) · Zbl 0527.68049
[6] Colbourn, C. J.; Proskurowski, A., Concurrent transmissions in broadcast networks, (Proc. Int. Conf. Automata, Languages, Programming, 172 (1984), Springer-Verlag), 128-136, LNCS · Zbl 0554.94021
[7] Farley, A. M., Networks, immune to isolated failures, Networks, 11, 255-268 (1981) · Zbl 0459.94036
[8] Farley, A. M.; Proskurowski, A., Networks immune to isolated line failures, Networks, 12, 393-403 (1982) · Zbl 0493.94020
[9] Neufeld, E. M.; Colbourn, C. J., The Most Reliable Series-Parallel Networks, TR 83-7 (1983), Dept. of Computing Science, University of Saskatchewan
[10] Proskurowski, A., Separating subgraphs in \(k\)-trees: cables and caterpillars, Discr. Math., 49, 275-285 (1984) · Zbl 0543.05041
[11] Robertson, N.; Seymour, P. D., Disjoint paths—a survey, SIAM J. Alg. Discr. Meth., 6, 300-305 (1985) · Zbl 0565.05045
[12] Wald, A.; Colbourn, C. J., Steiner trees, partial 2-trees, and minimum IFI networks, Networks, 13, 159-167 (1983) · Zbl 0529.68036
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.